#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;
int query(vi &vec)
{
if(vec.empty()) return 0;
if(vec.size()==1) return 1;
cout<<vec.size()<<' ';
for(int i=0;i<vec.size();i++)
{
cout<<vec[i]+1;
if(i+1<vec.size()) cout<<' ';
}
cout<<'\n';
fflush(stdout);
int x; cin>>x; return x;
}
pair<vi,vi> solve2(vi &L, vi &R, vi &oril, vi &orir)
{
assert(L.size()==R.size());
if(L.empty()) return {{},{}};
if(L.size()==1) return {{0},{0}};
/*
cerr<<"SOLVE 2 :\n";
for(int i=0;i<L.size();i++) cerr<<L[i]<<' ';
cerr<<'\n';
for(int i=0;i<R.size();i++) cerr<<R[i]<<' ';
cerr<<'\n';
for(int i=0;i<oril.size();i++) cerr<<oril[i]<<' ';
cerr<<'\n';
for(int i=0;i<orir.size();i++) cerr<<orir[i]<<' ';
cerr<<'\n';
*/
int n = L.size();
int col = n/2;
vi vtmp;
for(int i = 0; i < n/2; i++)
{
vtmp.pb(oril[i]);
}
vi Lidx,Ridx;
for(int i = 0; i < orir.size(); i++)
{
vtmp.pb(orir[i]);
int col2 = query(vtmp);
if(col2>col)
{
Ridx.pb(i);
//cerr<<"R "<<i<<'\n';
}
else
{
Lidx.pb(i);
//cerr<<"L "<<i<<'\n';
}
vtmp.pop_back();
}
vi filler(n);
vi perm(n);
vi t1,t2;
{
vi l,r,ori1,ori2;
for(int i=0;i<Lidx.size();i++)
{
int idx = Lidx[i];
l.pb(L[idx]);
r.pb(R[idx]);
ori1.pb(oril[idx]);
ori2.pb(orir[idx]);
}
t1=solve2(l,r,ori1,ori2).se;
}
{
vi l,r,ori1,ori2;
for(int i=0;i<Ridx.size();i++)
{
int idx = Ridx[i];
l.pb(L[idx]);
r.pb(R[idx]);
ori1.pb(oril[idx]);
ori2.pb(orir[idx]);
}
t2=solve2(l,r,ori1,ori2).se;
}
for(int i = 0; i < Lidx.size(); i++)
{
filler[Lidx[i]] = i;
perm[Lidx[i]] = t1[i];
}
for(int i = 0; i < Ridx.size(); i++)
{
filler[Ridx[i]] = i+n/2;
perm[Ridx[i]] = t2[i]+n/2;
}
return mp(filler,perm);
}
vi solve(vi &vec)
{
if(vec.empty()) return vi();
if(vec.size()==1) return {0};
if(vec.size()==2)
{
int tmp = query(vec);
if(tmp==2) return {0,1};
else return {0,0};
}
/*
for(int i = 0; i < vec.size(); i++)
{
cerr<<vec[i]<<' ';
}
cerr<<'\n';
*/
//random_shuffle(vec.begin(),vec.end());
vi L,R;
int n=vec.size();
for(int i=0;i<n/2;i++)
{
L.pb(vec[i]);
}
for(int i=n/2;i<n;i++)
{
R.pb(vec[i]);
}
int col = query(vec);
//cerr<<"COL "<<col<<' '<<n<<'\n';
if(col==1)
{
vi ans;
for(int i=0;i<n;i++) ans.pb(0);
return ans;
}
if(col==int(vec.size()))
{
vi ans;
for(int i=0;i<n;i++) ans.pb(i);
return ans;
}
vi res1 = solve(L);
vi res2 = solve(R);
int mx=0;
int mx2=0;
for(int i=0;i<res1.size();i++) mx=max(mx,res1[i]);
for(int i=0;i<res2.size();i++) mx2=max(mx2,res2[i]);
mx++; mx2++;
int intersect = mx+mx2-col;
if(intersect==0)
{
vi ans;
for(int i=0;i<res1.size();i++) ans.pb(res1[i]);
for(int i=0;i<res2.size();i++) ans.pb(mx+res2[i]);
return ans;
}
//cerr<<"INTERSECT : "<<intersect<<'\n';
vi rep1(mx,-1);
vi rep2(mx2,-1);
for(int i = 0; i < res1.size(); i++)
{
if(rep1[res1[i]]==-1)
{
rep1[res1[i]]=i;
}
}
for(int i = 0; i < res2.size(); i++)
{
if(rep2[res2[i]]==-1)
{
rep2[res2[i]]=i;
}
}
int ptr=intersect;
int ptr2=mx;
vi V1,V2,ori1,ori2;
vi tp;
for(int i=0;i<mx2;i++) tp.pb(R[rep2[i]]);
int cur=mx2;
vi ans(mx+mx2);
for(int i = 0; i < mx; i++)
{
tp.pb(L[rep1[i]]);
int cur2 = col;
if(i+1<mx) cur2=query(tp);
if(cur2>cur)
{
ans[i] = ptr++;
}
else
{
ori1.pb(L[rep1[i]]);
V1.pb(i);
}
cur=cur2;
}
tp.clear();
for(int i=0;i<mx;i++) tp.pb(L[rep1[i]]);
cur=mx;
for(int i = 0; i < mx2; i++)
{
tp.pb(R[rep2[i]]);
int cur2 = col;
if(i+1<mx2) cur2=query(tp);
if(cur2>cur)
{
ans[i+mx] = ptr2++;
}
else
{
ori2.pb(R[rep2[i]]);
V2.pb(i+mx);
}
cur=cur2;
}
pair<vi,vi> tmp = solve2(V1,V2,ori1,ori2);
for(int i = 0; i < V1.size(); i++)
{
ans[V1[i]] = tmp.fi[i];
}
for(int i = 0; i < V2.size(); i++)
{
ans[V2[i]] = tmp.se[i];
}
vi ANS(n);
for(int i = 0; i < n; i++)
{
if(i<n/2)
{
int tmp = res1[i];
ANS[i] = ans[tmp];
}
else
{
int tmp = res2[i-n/2];
ANS[i] = ans[tmp+mx];
}
}
return ANS;
}
int main()
{
srand(147);
int n; cin>>n;
vi vec;
for(int i=0;i<n;i++) vec.pb(i);
vi tmp=solve(vec);
cout<<0<<' ';
for(int i=0;i<n;i++)
{
cout<<tmp[i]+1;
if(i+1<n) cout<<' ';
}
cout<<'\n';
fflush(stdout);
}
Compilation message
carnival.cpp: In function 'int query(vi&)':
carnival.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<vec.size();i++)
^
carnival.cpp:31:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i+1<vec.size()) cout<<' ';
^
carnival.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > solve2(vi&, vi&, vi&, vi&)':
carnival.cpp:62:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < orir.size(); i++)
^
carnival.cpp:83:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<Lidx.size();i++)
^
carnival.cpp:95:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<Ridx.size();i++)
^
carnival.cpp:105:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < Lidx.size(); i++)
^
carnival.cpp:110:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < Ridx.size(); i++)
^
carnival.cpp: In function 'vi solve(vi&)':
carnival.cpp:164:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<res1.size();i++) mx=max(mx,res1[i]);
^
carnival.cpp:165:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<res2.size();i++) mx2=max(mx2,res2[i]);
^
carnival.cpp:171:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<res1.size();i++) ans.pb(res1[i]);
^
carnival.cpp:172:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<res2.size();i++) ans.pb(mx+res2[i]);
^
carnival.cpp:178:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < res1.size(); i++)
^
carnival.cpp:185:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < res2.size(); i++)
^
carnival.cpp:235:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < V1.size(); i++)
^
carnival.cpp:239:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < V2.size(); i++)
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
106 ms |
15380 KB |
Execution timed out (wall clock limit exceeded) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
93 ms |
13300 KB |
Execution timed out (wall clock limit exceeded) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2028 KB |
Output is correct |
| 2 |
Runtime error |
129 ms |
18440 KB |
Execution timed out (wall clock limit exceeded) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
196 ms |
22908 KB |
Execution timed out (wall clock limit exceeded) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2028 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
