Submission #228248

#TimeUsernameProblemLanguageResultExecution timeMemory
228248VEGAnnTeoretičar (COCI18_teoreticar)C++14
39 / 130
12095 ms89880 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], x[M], y[M], tt = 0, X, deg[2][N]; mt19937 rnd(chrono::system_clock().now().time_since_epoch().count()); void potential(){ int cur = 0; tt++; for (int it = 0; it < m; it++){ int i = nm[it]; for (int c = 0; ; c++) if (mrk[0][x[i]][c] < tt && mrk[1][y[i]][c] < tt){ col[i] = c; cur = max(cur, c); if (cur >= X) { shuffle(nm, nm + m, rnd); return; } mrk[0][x[i]][c] = mrk[1][y[i]][c] = tt; break; } } cout << cur + 1 << '\n'; for (int i = 0; i < m; i++) cout << col[i] + 1 << '\n'; exit(0); } 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]--; deg[0][x[i]]++; deg[1][y[i]]++; nm[i] = i; } int mex = 0; for (int i = 0; i < max(l, r); i++) { mex = max(mex, deg[0][i]); mex = max(mex, deg[1][i]); } X = 1; while (X < mex) X += X; for (;;) potential(); 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...