#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 7;
int l, r, m;
vector<pair<int, int>> e;
map<pair<int, int>, int> cols;
bool check(int x)
{
map<int, int> chs[x + 1];
for (auto u : e)
{
bool ok = 0;
for (int j = 0; j < x; j++)
{
if (!(chs[j][u.first] | chs[j][u.second]))
{
ok = 1;
cols[u] = j + 1;
chs[j][u.first] = chs[j][u.second] = 1;
break;
}
}
if (!ok)
return 0;
}
return 1;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie();
//freopen("in.in", "r", stdin);
cin >> l >> r >> m;
for (int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
v += l;
e.push_back({u, v});
}
int lo = 1, hi = m;
int ans = 0;
for (; lo <= hi;)
{
int mid = (lo + hi) >> 1;
if (check(mid))
{
ans = mid;
hi = mid - 1;
}
else
{
lo = mid + 1;
}
}
cout << ans << '\n';
for (auto u : e)
{
cout << cols[u] << "\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
384 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
67 ms |
1480 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3432 ms |
13572 KB |
Output is correct |
2 |
Correct |
85 ms |
1528 KB |
Output is correct |
3 |
Correct |
59 ms |
1408 KB |
Output is correct |
4 |
Correct |
87 ms |
1316 KB |
Output is correct |
5 |
Correct |
65 ms |
1016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
12033 ms |
75716 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
12057 ms |
75664 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2755 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
12069 ms |
54796 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
12083 ms |
134148 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
12047 ms |
132132 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |