#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int query(const vector<int> &c){
if (c.size() <= 1) return c.size();
cout << c.size() << "\n";
for (int i=0; i<c.size(); i++){
cout << c[i]+1 << " \n"[i == c.size()-1];
}
cout << flush;
int val; cin >> val;
return val;
}
struct dsu{
vector<int> p;
dsu(int n): p(n, -1) {}
int find(int v){
if (p[v] < 0) return v;
return p[v] = find(p[v]);
}
void merge(int a, int b){
a = find(a), b = find(b);
if (a == b) return;
if (-p[a] < -p[b]) swap(a, b);
p[a] += p[b];
p[b] = a;
}
vector<int> get_heads(){
vector<int> a;
for (int i=0; i<p.size(); i++){
if (p[i] < 0) a.push_back(i);
}
return a;
}
};
pair<int, int> search_edge(const vector<int> &a, const vector<int> &b){
if (a.size() == 1 && b.size() == 1) return {a[0], b[0]};
if (a.size() == 1) return search_edge(b, a);
vector<int> x(a.begin(), a.begin() + a.size()/2);
x.insert(x.end(), b.begin(), b.end());
if (query(x) != x.size())
return search_edge(vector<int> (a.begin(), a.begin() + a.size()/2), b);
else
return search_edge(vector<int> (a.begin() + a.size()/2, a.end()), b);
}
pair<int, int> search_edge(const vector<int> &s){
if (s.size() == 2) return {s[0], s[1]};
vector<int> a(s.begin(), s.begin() + s.size()/2);
vector<int> b(s.begin() + s.size()/2, s.end());
if (query(a) != a.size())
return search_edge(a);
if (query(b) != b.size())
return search_edge(b);
return search_edge(a, b);
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int n; cin >> n;
dsu g(n);
while (true){
vector<int> c = g.get_heads();
if (query(c) == c.size()) break;
pair<int, int> e = search_edge(c);
g.merge(e.first, e.second);
}
vector<int> a(n, -1);
int c = 0;
for (int i=0; i<n; i++){
if (g.find(i) == i) a[i] = c++;
}
cout << "0\n";
for (int i=0; i<n; i++){
cout << a[g.find(i)]+1 << " \n"[i == n-1];
}
}
Compilation message
carnival.cpp: In function 'int query(const std::vector<int>&)':
carnival.cpp:7:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
7 | for (int i=0; i<c.size(); i++){
| ~^~~~~~~~~
carnival.cpp:8:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
8 | cout << c[i]+1 << " \n"[i == c.size()-1];
| ~~^~~~~~~~~~~~~
carnival.cpp: In member function 'std::vector<int> dsu::get_heads()':
carnival.cpp:30:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int i=0; i<p.size(); i++){
| ~^~~~~~~~~
carnival.cpp: In function 'std::pair<int, int> search_edge(const std::vector<int>&, const std::vector<int>&)':
carnival.cpp:41:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | if (query(x) != x.size())
| ~~~~~~~~~^~~~~~~~~~~
carnival.cpp: In function 'std::pair<int, int> search_edge(const std::vector<int>&)':
carnival.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | if (query(a) != a.size())
| ~~~~~~~~~^~~~~~~~~~~
carnival.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | if (query(b) != b.size())
| ~~~~~~~~~^~~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | if (query(c) == c.size()) break;
| ~~~~~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
208 KB |
Output is correct |
| 2 |
Correct |
12 ms |
208 KB |
Output is correct |
| 3 |
Correct |
7 ms |
300 KB |
Output is correct |
| 4 |
Correct |
2 ms |
208 KB |
Output is correct |
| 5 |
Correct |
12 ms |
320 KB |
Output is correct |
| 6 |
Correct |
8 ms |
208 KB |
Output is correct |
| 7 |
Correct |
14 ms |
320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
208 KB |
Output is correct |
| 2 |
Correct |
16 ms |
208 KB |
Output is correct |
| 3 |
Correct |
3 ms |
208 KB |
Output is correct |
| 4 |
Correct |
3 ms |
208 KB |
Output is correct |
| 5 |
Correct |
9 ms |
208 KB |
Output is correct |
| 6 |
Correct |
10 ms |
328 KB |
Output is correct |
| 7 |
Correct |
15 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
208 KB |
Output is correct |
| 2 |
Correct |
11 ms |
208 KB |
Output is correct |
| 3 |
Correct |
11 ms |
324 KB |
Output is correct |
| 4 |
Correct |
2 ms |
208 KB |
Output is correct |
| 5 |
Correct |
14 ms |
256 KB |
Output is correct |
| 6 |
Correct |
12 ms |
208 KB |
Output is correct |
| 7 |
Correct |
13 ms |
320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
208 KB |
Output is correct |
| 2 |
Correct |
11 ms |
208 KB |
Output is correct |
| 3 |
Correct |
6 ms |
208 KB |
Output is correct |
| 4 |
Correct |
1 ms |
208 KB |
Output is correct |
| 5 |
Correct |
10 ms |
208 KB |
Output is correct |
| 6 |
Correct |
9 ms |
208 KB |
Output is correct |
| 7 |
Correct |
13 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
208 KB |
Output is correct |
| 2 |
Correct |
14 ms |
208 KB |
Output is correct |
| 3 |
Correct |
11 ms |
324 KB |
Output is correct |
| 4 |
Correct |
9 ms |
208 KB |
Output is correct |
| 5 |
Correct |
10 ms |
208 KB |
Output is correct |
| 6 |
Correct |
5 ms |
208 KB |
Output is correct |
| 7 |
Correct |
2 ms |
324 KB |
Output is correct |
