#include <bits/stdc++.h>
using namespace std;
int ask(vector<int>&v){
if(v.size()==1) return 1;
cout << v.size() << " ";
for(auto&x:v)
cout << x << " ";
cout << endl << flush;
int odg;cin >> odg;
return odg;
}
void deo1(int n,vector<vector<int>>&delovi,int tr_ind){
if(tr_ind==n+1) return;
int l=tr_ind,d=n,rez;
while(l<=d){
int s=(l+d)/2;
vector<int> pitaj(0);
for(int i=tr_ind; i<=s; i++)
pitaj.push_back(i);
if(ask(pitaj)==pitaj.size()){
rez=s;
l=s+1;
}
else
d=s-1;
}
vector<int> p(0);
for(int i=tr_ind; i<=rez; i++)
p.push_back(i);
delovi.push_back(p);
deo1(n,delovi,rez+1);
}
vector<int> par,rnk;
int ulp(int node){
if(par[node]==node) return node;
return par[node]=ulp(par[node]);
}
void spajaj(int a,int b){
a=ulp(a);b=ulp(b);
if(a==b) return;
if(rnk[b]>rnk[a])
swap(a,b);
par[b]=a;
if(rnk[b]==rnk[a])
rnk[a]++;
}
int main()
{
int n;
cin >> n;
vector<vector<int>> delovi(0);
deo1(n,delovi,1);
int tr_deo=0;
rnk.resize(n+1,0);
par.resize(n+1);
for(int i=1; i<=n; i++)
par[i]=i;
vector<bool> checked(n+1,0);
vector<int> pocetak_dela(delovi.size()+1);
pocetak_dela[0]=1;
for(int i=1; i<delovi.size(); i++)
pocetak_dela[i]=pocetak_dela[i-1]+delovi[i-1].size();
pocetak_dela[delovi.size()]=pocetak_dela[delovi.size()-1]+delovi[delovi.size()-1].size();
//cerr << "Zavrsio prvi deo" << endl;
while(tr_deo!=delovi.size()-1){
for(auto tr_element:delovi[tr_deo]){
if(checked[tr_element]) continue;
for(int i=tr_deo+1; i<delovi.size(); i++){
vector<int> pp(0);
pp.push_back(tr_element);
int l=pocetak_dela[i],d=pocetak_dela[i+1]-1;
for(int j=l; j<=d; j++)
pp.push_back(j);
if(ask(pp)==pp.size())
continue;
int rez=2e5;
while(l<=d){
int s=(l+d)/2;
vector<int> p(0);
p.push_back(tr_element);
for(int j=pocetak_dela[i]; j<=s; j++)
p.push_back(j);
int odg=ask(p);
if(odg>=p.size())
l=s+1;
else{
rez=min(rez,s);
d=s-1;
}
}
spajaj(tr_element,rez);
checked[rez]=true;
}
}
tr_deo++;
}
vector<int> rez(n),mapa(n+2,0);
int tr_boja=1;
for(int i=1; i<=n; i++){
if(mapa[ulp(i)]==0){
mapa[ulp(i)]=tr_boja;
tr_boja++;
}
}
for(int i=1; i<=n; i++)
rez[i-1]=mapa[ulp(i)];
cout << 0 << " ";
for(auto x:rez)
cout << x << " ";
cout << flush;
return 0;
}
Compilation message
carnival.cpp: In function 'void deo1(int, std::vector<std::vector<int> >&, int)':
carnival.cpp:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | if(ask(pitaj)==pitaj.size()){
| ~~~~~~~~~~^~~~~~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i=1; i<delovi.size(); i++)
| ~^~~~~~~~~~~~~~
carnival.cpp:69:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | while(tr_deo!=delovi.size()-1){
| ~~~~~~^~~~~~~~~~~~~~~~~
carnival.cpp:72:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int i=tr_deo+1; i<delovi.size(); i++){
| ~^~~~~~~~~~~~~~
carnival.cpp:78:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | if(ask(pp)==pp.size())
| ~~~~~~~^~~~~~~~~~~
carnival.cpp:88:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | if(odg>=p.size())
| ~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
688 KB |
Output is correct |
| 2 |
Correct |
5 ms |
436 KB |
Output is correct |
| 3 |
Correct |
4 ms |
428 KB |
Output is correct |
| 4 |
Correct |
2 ms |
436 KB |
Output is correct |
| 5 |
Correct |
4 ms |
432 KB |
Output is correct |
| 6 |
Correct |
4 ms |
688 KB |
Output is correct |
| 7 |
Correct |
4 ms |
688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
692 KB |
Output is correct |
| 2 |
Correct |
6 ms |
440 KB |
Output is correct |
| 3 |
Correct |
3 ms |
600 KB |
Output is correct |
| 4 |
Correct |
3 ms |
436 KB |
Output is correct |
| 5 |
Correct |
6 ms |
948 KB |
Output is correct |
| 6 |
Correct |
12 ms |
1460 KB |
Output is correct |
| 7 |
Correct |
6 ms |
692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
692 KB |
Output is correct |
| 2 |
Correct |
4 ms |
688 KB |
Output is correct |
| 3 |
Correct |
5 ms |
432 KB |
Output is correct |
| 4 |
Correct |
1 ms |
436 KB |
Output is correct |
| 5 |
Correct |
7 ms |
436 KB |
Output is correct |
| 6 |
Correct |
14 ms |
952 KB |
Output is correct |
| 7 |
Correct |
7 ms |
684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
692 KB |
Output is correct |
| 2 |
Correct |
4 ms |
436 KB |
Output is correct |
| 3 |
Correct |
4 ms |
436 KB |
Output is correct |
| 4 |
Correct |
1 ms |
432 KB |
Output is correct |
| 5 |
Correct |
11 ms |
436 KB |
Output is correct |
| 6 |
Correct |
17 ms |
700 KB |
Output is correct |
| 7 |
Correct |
5 ms |
436 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
948 KB |
Output is correct |
| 2 |
Correct |
4 ms |
440 KB |
Output is correct |
| 3 |
Correct |
7 ms |
436 KB |
Output is correct |
| 4 |
Correct |
4 ms |
432 KB |
Output is correct |
| 5 |
Correct |
10 ms |
692 KB |
Output is correct |
| 6 |
Correct |
11 ms |
436 KB |
Output is correct |
| 7 |
Correct |
4 ms |
432 KB |
Output is correct |
