提出 #7077552


ソースコード 拡げる

Copy
#include <bits/stdc++.h>

using namespace std;

using int64 = long long;
const int mod = 998244353;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

template< typename F >
struct FixPoint : F {
  FixPoint(F &&f) : F(forward< F >(f)) {}

  template< typename... Args >
  decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, forward< Args >(args)...);
  }
};

template< typename F >
inline decltype(auto) MFP(F &&f) {
  return FixPoint< F >{forward< F >(f)};
}

struct Bipartite_Matching {
  vector< vector< int > > graph;
  vector< int > match, alive, used;
  int timestamp;

  Bipartite_Matching(int n) {
    timestamp = 0;
    graph.resize(n);
    alive.assign(n, 1);
    used.assign(n, 0);
    match.assign(n, -1);
  }

  void add_edge(int u, int v) {
    graph[u].push_back(v);
    graph[v].push_back(u);
  }

  bool dfs(int v) {
    used[v] = timestamp;
    for(int i = 0; i < graph[v].size(); i++) {
      int u = graph[v][i], w = match[u];
      if(alive[u] == 0) continue;
      if(w == -1 || (used[w] != timestamp && dfs(w))) {
        match[v] = u;
        match[u] = v;
        return (true);
      }
    }
    return (false);
  }

  int bipartite_matching() {
    int ret = 0;
    for(int i = 0; i < graph.size(); i++) {
      if(alive[i] == 0) continue;
      if(match[i] == -1) {
        ++timestamp;
        ret += dfs(i);
      }
    }
    return (ret);
  }
};


int main() {
  int N, M;
  cin >> N >> M;
  auto A = make_v< int >(N, M);
  cin >> A;
  for(auto &vs : A) for(auto &p : vs) --p;
  auto B = make_v< int >(N, M);
  fill_v(B, -1);
  for(int i = 0; i < M; i++) {
    Bipartite_Matching bm(N + N);
    auto pre = make_v< int >(N, N);
    fill_v(pre, -1);
    for(int j = 0; j < N; j++) {
      for(int k = 0; k < M; k++) {
        if(A[j][k] == -1) continue;
        if(pre[j][A[j][k] / M] != -1) continue;
        bm.add_edge(j, N + A[j][k] / M);
        pre[j][A[j][k] / M] = k;
      }
    }
    bm.bipartite_matching();
    for(int j = 0; j < N; j++) {
      B[j][i] = A[j][pre[j][bm.match[j] - N]];
      A[j][pre[j][bm.match[j] - N]] = -1;
    }

  }

  for(auto &vs : B) {
    for(auto &p : vs) ++p;
    cout << vs << endl;
  }

  auto C = make_v< int >(N, M);
  for(int i = 0; i < M; i++) {
    vector< int > be;
    for(int j = 0; j < N; j++) {
      be.emplace_back(B[j][i]);
    }
    sort(begin(be), end(be));
    for(int j = 0; j < N; j++) {
      C[j][i] = be[j];
    }
  }

  for(auto &vs : C) {
    cout << vs << endl;
  }


}


提出情報

提出日時
問題 D - Sorting a Grid
ユーザ ei13333
言語 C++14 (GCC 5.4.1)
得点 1100
コード長 4208 Byte
結果
実行時間 25 ms
メモリ 616 KB

ジャッジ結果

セット名 得点 / 配点 テストケース
Sample 0 / 0 sample01.txt, sample02.txt
All 1100 / 1100 sample01.txt, sample02.txt, in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in20.txt, in21.txt, in22.txt, in23.txt, sample01.txt, sample02.txt
ケース名 結果 実行時間 メモリ
in01.txt 17 ms 512 KB
in02.txt 21 ms 512 KB
in03.txt 23 ms 512 KB
in04.txt 6 ms 384 KB
in05.txt 6 ms 384 KB
in06.txt 6 ms 384 KB
in07.txt 6 ms 384 KB
in08.txt 11 ms 384 KB
in09.txt 8 ms 384 KB
in10.txt 18 ms 512 KB
in11.txt 15 ms 512 KB
in12.txt 24 ms 596 KB
in13.txt 7 ms 384 KB
in14.txt 9 ms 512 KB
in15.txt 7 ms 384 KB
in16.txt 6 ms 384 KB
in17.txt 7 ms 384 KB
in18.txt 8 ms 384 KB
in19.txt 24 ms 592 KB
in20.txt 25 ms 608 KB
in21.txt 24 ms 600 KB
in22.txt 24 ms 616 KB
in23.txt 1 ms 256 KB
sample01.txt 1 ms 256 KB
sample02.txt 1 ms 256 KB