Submission #228239

#TimeUsernameProblemLanguageResultExecution timeMemory
228239VEGAnnTeoretičar (COCI18_teoreticar)C++14
0 / 130
12100 ms262144 KiB
#include <bits/stdc++.h> #define pii pair<int,int> #define ft first #define sd second #define MP make_pair #define sz(x) ((int)x.size()) using namespace std; typedef long long ll; const int N = 5010; const int M = 500100; const int oo = 2e9; int col[M], l, r, mrk[2][N][N], m, ans = oo, nm[M], mem[M], x[M], y[M]; mt19937 rnd(chrono::system_clock().now().time_since_epoch().count()); void potential(){ shuffle(nm, nm + m, rnd); int cur = 0; for (int i = 0; i < max(l, r); i++) for (int j = 0; j < max(l, r); j++) mrk[0][i][j] = mrk[1][i][j] = 0; for (int it = 0; it < m; it++){ int i = nm[it]; for (int c = 0; ; c++) if (!mrk[0][x[i]][c] && !mrk[1][y[i]][c]){ col[i] = c; cur = max(cur, c); mrk[0][x[i]][c] = mrk[1][y[i]][c] = 1; break; } } if (ans > cur){ ans = cur; for (int i = 0; i < m; i++) mem[i] = col[i]; } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> l >> r >> m; for (int i = 0; i < m; i++){ cin >> x[i] >> y[i]; x[i]--; y[i]--; nm[i] = i; } for (int it = 0; it < 500; it++) potential(); cout << ans + 1 << '\n'; for (int i = 0; i < m; i++) cout << mem[i] + 1 << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...