#include "chameleon.h" #include <bits/stdc++.h> using namespace std; const int maxn=1001; int n; vector<int> v[maxn]; vector<int> lf,rt; int e[maxn][maxn]; void connect(int ver,vector<int> f) { /*cout<<ver<<" > "; for(int i=0;i<f.size();i++) cout<<f[i]<<" "; cout<<endl;*/ int bg=0; while(1) { int id=-1; int l=bg,r=f.size()-1; while(l<=r) { int m=(l+r)/2; int k=m-bg+2; vector<int> q={ver}; for(int i=bg;i<=m;i++) q.push_back(f[i]); if(Query(q)!=k) { id=m; r=m-1; } else l=m+1; } if(id==-1)return; bg=id+1; id=f[id]; v[ver].push_back(id); v[id].push_back(ver); e[ver][id]=e[id][ver]=1; //cout<<ver<<" -- "<<id<<endl; } } int u[maxn]; void dfs(int i,int c) { if(c==1)lf.push_back(i); else rt.push_back(i); u[i]=1; for(int j=0;j<v[i].size();j++) { int nb=v[i][j]; if(u[nb])continue; dfs(nb,c^2); } } void build() { for(int i=1; i<=2*n; i++) { //cout<<"> "<<i<<endl; for(int j=1;j<i;j++) u[j]=0; for(int j=1; j<i;j++) if(!u[j])dfs(j,1); connect(i,lf); connect(i,rt); lf.clear(); rt.clear(); } } void Solve(int N) { n=N; build(); for(int i=1;i<=2*n;i++) { if(v[i].size()==1) { if(v[i][0]<i) { e[v[i][0]][i]=e[i][v[i][0]]=2; Answer(v[i][0],i); } continue; } int q2=Query({i,v[i][0],v[i][1]}); int q1=Query({i,v[i][0],v[i][2]}); if(q1==1)e[i][v[i][1]]=e[v[i][1]][i]=2; else if(q2==1)e[i][v[i][2]]=e[v[i][2]][i]=2; else e[i][v[i][0]]=e[v[i][0]][i]=2; } for(int i=1;i<=2*n;i++) { for(int j=1;j<i;j++) { if(e[i][j]==1) { Answer(j,i); } } } } /* 4 1 0 1 0 0 1 1 0 4 4 1 2 1 2 3 3 4 3 8 7 6 5 2 1 */