| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 37034 |
2017-12-20T15:00:52 Z |
aome |
Carnival (CEOI14_carnival) |
C++14 |
|
19 ms |
2016 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 155;
int par[N], color[N];
int find(int u) {
return (u == par[u]) ? u : par[u] = find(par[u]);
}
void join(int u, int v) {
par[find(u)] = find(v);
}
int get(vector<int> &go, int l, int r) {
cout << r - l + 1 << ' ';
for (int i = l; i <= r; ++i) cout << go[i] << ' '; cout << '\n';
int res; cin >> res; return res;
}
void solve(vector<int> &go) {
int sz = go.size();
int l = 0, r = sz - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (get(go, 0, mid) == mid + 1) l = mid + 1;
else r = mid;
}
if (get(go, 0, l) == l + 1) return;
int pos = l;
l = 0, r = pos - 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (get(go, mid, pos) == pos - mid + 1) r = mid - 1;
else l = mid;
}
join(go[pos], go[l]);
vector<int> tmp = go; go.clear();
for (int i = 0; i < sz; ++i) {
if (i != pos) go.push_back(tmp[i]);
}
solve(go);
}
int main() {
int n; cin >> n;
vector<int> go;
for (int i = 1; i <= n; ++i) par[i] = i, go.push_back(i);
solve(go);
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (find(i) == i) color[i] = ++cnt;
}
cout << "0 ";
for (int i = 1; i <= n; ++i) {
cout << color[find(i)] << ' ';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
2016 KB |
Output is correct |
| 2 |
Correct |
16 ms |
2016 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2016 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2016 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2016 KB |
Output is correct |
| 6 |
Correct |
3 ms |
2016 KB |
Output is correct |
| 7 |
Correct |
16 ms |
2016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
2016 KB |
Output is correct |
| 2 |
Correct |
13 ms |
2016 KB |
Output is correct |
| 3 |
Correct |
9 ms |
2016 KB |
Output is correct |
| 4 |
Correct |
3 ms |
2016 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2016 KB |
Output is correct |
| 6 |
Correct |
9 ms |
2016 KB |
Output is correct |
| 7 |
Correct |
16 ms |
2016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2016 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2016 KB |
Output is correct |
| 3 |
Correct |
9 ms |
2016 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2016 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2016 KB |
Output is correct |
| 6 |
Correct |
9 ms |
2016 KB |
Output is correct |
| 7 |
Correct |
13 ms |
2016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
2016 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2016 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2016 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2016 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2016 KB |
Output is correct |
| 6 |
Correct |
6 ms |
2016 KB |
Output is correct |
| 7 |
Correct |
13 ms |
2016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2016 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2016 KB |
Output is correct |
| 3 |
Correct |
9 ms |
2016 KB |
Output is correct |
| 4 |
Correct |
6 ms |
2016 KB |
Output is correct |
| 5 |
Correct |
9 ms |
2016 KB |
Output is correct |
| 6 |
Correct |
9 ms |
2016 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2016 KB |
Output is correct |
