| #include <cstdio> |
| #include <cstdlib> |
| #include <cstring> |
| #include <vector> |
| #include <algorithm> |
| using namespace std; |
|
|
| static char obuf[1<<22]; static int opos; |
| void oflush(){fwrite(obuf,1,opos,stdout);opos=0;fflush(stdout);} |
| void ochar(char c){obuf[opos++]=c;} |
| void oint(int x){ |
| if(x>=1000){ochar('0'+x/1000);ochar('0'+(x/100)%10);ochar('0'+(x/10)%10);ochar('0'+x%10);} |
| else if(x>=100){ochar('0'+x/100);ochar('0'+(x/10)%10);ochar('0'+x%10);} |
| else if(x>=10){ochar('0'+x/10);ochar('0'+x%10);} |
| else ochar('0'+x); |
| } |
|
|
| int N,q[1001],perm[1001]; |
| int kc; |
|
|
| int ask(){ochar('0');for(int i=0;i<N;i++){ochar(' ');oint(q[i]);}ochar('\n');oflush();int x;scanf("%d",&x);return x;} |
| void submit(){ochar('1');for(int i=0;i<N;i++){ochar(' ');oint(perm[i]);}ochar('\n');oflush();exit(0);} |
|
|
| int par[1001]; |
| int Find(int x){return par[x]==x?x:par[x]=Find(par[x]);} |
| void Unite(int a,int b){par[Find(a)]=Find(b);} |
|
|
| void solve(vector<int>& vals, vector<int>& pos) { |
| int n = vals.size(); |
| if (n == 0) return; |
| if (n == 1) { |
| perm[pos[0]] = vals[0]; q[pos[0]] = vals[0]; kc++; |
| return; |
| } |
| if (n == 2) { |
| q[pos[0]] = vals[0]; |
| int r = ask(); |
| q[pos[0]] = 1; |
| if (r == kc + 1) { |
| perm[pos[0]] = vals[0]; q[pos[0]] = vals[0]; |
| perm[pos[1]] = vals[1]; q[pos[1]] = vals[1]; |
| } else { |
| perm[pos[0]] = vals[1]; q[pos[0]] = vals[1]; |
| perm[pos[1]] = vals[0]; q[pos[1]] = vals[0]; |
| } |
| kc += 2; |
| return; |
| } |
| |
|
|
| int half = n / 2; |
| int right_half = n - half; |
|
|
| for (int i = 0; i < n; i++) par[i] = i; |
|
|
| vector<int> half_known(n, -1); |
| int left_count = 0, right_count = 0; |
|
|
| |
| auto assign_group = [&](int rep, int h) { |
| for (int i = 0; i < n; i++) { |
| if (Find(i) == Find(rep)) { |
| half_known[i] = h; |
| if (h == 0) left_count++; |
| else right_count++; |
| } |
| } |
| }; |
|
|
| |
| auto check_early_termination = [&]() -> bool { |
| if (left_count == half) { |
| |
| for (int i = 0; i < n; i++) { |
| if (half_known[i] == -1) { half_known[i] = 1; right_count++; } |
| } |
| return true; |
| } |
| if (right_count == right_half) { |
| for (int i = 0; i < n; i++) { |
| if (half_known[i] == -1) { half_known[i] = 0; left_count++; } |
| } |
| return true; |
| } |
| return false; |
| }; |
|
|
| vector<int> same_half_reps; |
|
|
| |
| for (int vi = 0; vi + 1 < n; vi += 2) { |
| if (check_early_termination()) break; |
|
|
| int v = vals[vi], w = vals[vi + 1]; |
| for (int i = 0; i < half; i++) q[pos[i]] = v; |
| for (int i = half; i < n; i++) q[pos[i]] = w; |
| int r = ask(); |
| for (int i = 0; i < half; i++) q[pos[i]] = 1; |
| for (int i = half; i < n; i++) q[pos[i]] = 1; |
|
|
| if (r == kc + 2) { |
| half_known[vi] = 0; half_known[vi + 1] = 1; |
| left_count++; right_count++; |
| } else if (r == kc) { |
| half_known[vi] = 1; half_known[vi + 1] = 0; |
| left_count++; right_count++; |
| } else { |
| Unite(vi, vi + 1); |
| same_half_reps.push_back(Find(vi)); |
| } |
| } |
|
|
| |
| if (n % 2 == 1 && half_known[n-1] == -1) { |
| if (check_early_termination()) goto done_disambiguation; |
| int vi = n - 1; |
| if (!same_half_reps.empty()) { |
| int rep = same_half_reps.back(); |
| same_half_reps.pop_back(); |
| int v = vals[vi]; |
| int w = -1; |
| for (int i = 0; i < n; i++) { |
| if (Find(i) == Find(rep)) { w = vals[i]; break; } |
| } |
| for (int i = 0; i < half; i++) q[pos[i]] = v; |
| for (int i = half; i < n; i++) q[pos[i]] = w; |
| int r = ask(); |
| for (int i = 0; i < half; i++) q[pos[i]] = 1; |
| for (int i = half; i < n; i++) q[pos[i]] = 1; |
|
|
| if (r == kc + 2) { |
| half_known[vi] = 0; left_count++; |
| assign_group(rep, 1); |
| } else if (r == kc) { |
| half_known[vi] = 1; right_count++; |
| assign_group(rep, 0); |
| } else { |
| Unite(vi, rep); |
| same_half_reps.push_back(Find(vi)); |
| } |
| } else { |
| int v = vals[vi]; |
| for (int i = 0; i < half; i++) q[pos[i]] = v; |
| int r = ask(); |
| for (int i = 0; i < half; i++) q[pos[i]] = 1; |
| half_known[vi] = (r == kc + 1) ? 0 : 1; |
| if (half_known[vi] == 0) left_count++; else right_count++; |
| } |
| } |
|
|
| |
| sort(same_half_reps.begin(), same_half_reps.end()); |
| same_half_reps.erase(unique(same_half_reps.begin(), same_half_reps.end()), same_half_reps.end()); |
|
|
| while (!same_half_reps.empty()) { |
| if (check_early_termination()) break; |
|
|
| vector<int> next_reps; |
| int si = 0; |
| while (si < (int)same_half_reps.size()) { |
| if (check_early_termination()) break; |
|
|
| if (si + 1 >= (int)same_half_reps.size()) { |
| int rep = same_half_reps[si]; |
| int v = -1; |
| for (int i = 0; i < n; i++) { |
| if (Find(i) == Find(rep)) { v = vals[i]; break; } |
| } |
| for (int k = 0; k < half; k++) q[pos[k]] = v; |
| int r = ask(); |
| for (int k = 0; k < half; k++) q[pos[k]] = 1; |
| int h = (r == kc + 1) ? 0 : 1; |
| assign_group(rep, h); |
| si++; |
| continue; |
| } |
|
|
| int rep1 = same_half_reps[si], rep2 = same_half_reps[si + 1]; |
| int v = -1, w = -1; |
| for (int i = 0; i < n; i++) { |
| if (Find(i) == Find(rep1) && v == -1) v = vals[i]; |
| if (Find(i) == Find(rep2) && w == -1) w = vals[i]; |
| if (v != -1 && w != -1) break; |
| } |
|
|
| for (int k = 0; k < half; k++) q[pos[k]] = v; |
| for (int k = half; k < n; k++) q[pos[k]] = w; |
| int r = ask(); |
| for (int k = 0; k < half; k++) q[pos[k]] = 1; |
| for (int k = half; k < n; k++) q[pos[k]] = 1; |
|
|
| if (r == kc + 2) { |
| assign_group(rep1, 0); |
| assign_group(rep2, 1); |
| } else if (r == kc) { |
| assign_group(rep1, 1); |
| assign_group(rep2, 0); |
| } else { |
| Unite(rep1, rep2); |
| next_reps.push_back(Find(rep1)); |
| } |
| si += 2; |
| } |
|
|
| sort(next_reps.begin(), next_reps.end()); |
| next_reps.erase(unique(next_reps.begin(), next_reps.end()), next_reps.end()); |
| same_half_reps = next_reps; |
| } |
|
|
| done_disambiguation: |
|
|
| vector<int> left_vals, right_vals; |
| vector<int> left_pos(pos.begin(), pos.begin() + half); |
| vector<int> right_pos(pos.begin() + half, pos.end()); |
|
|
| for (int i = 0; i < n; i++) { |
| if (half_known[i] == 0) left_vals.push_back(vals[i]); |
| else right_vals.push_back(vals[i]); |
| } |
|
|
| solve(left_vals, left_pos); |
| solve(right_vals, right_pos); |
| } |
|
|
| int main(){ |
| scanf("%d",&N); |
| memset(perm,0,sizeof(perm)); |
| if(N==1){perm[0]=1;submit();} |
| if(N==2){q[0]=1;q[1]=2;if(ask()==2){perm[0]=1;perm[1]=2;}else{perm[0]=2;perm[1]=1;}submit();} |
|
|
| |
| int B=0;{int tmp=N-1;while(tmp>0){B++;tmp>>=1;}} |
| int rb[12]; |
| for(int b=0;b<B;b++){ |
| for(int i=0;i<N;i++) q[i]=(i&(1<<b))?1:3; |
| rb[b]=ask(); |
| } |
| int kb1=0,kb3=0,kmask=0; |
| for(int b=0;b<B;b++){ |
| if(rb[b]==0){kmask|=(1<<b);kb3|=(1<<b);} |
| else if(rb[b]==2){kmask|=(1<<b);kb1|=(1<<b);} |
| } |
| int amask=((1<<B)-1)&~kmask,P=0; |
| for(int b=0;b<B;b++){ |
| if(!(amask&(1<<b)))continue; |
| for(int i=0;i<N;i++){ |
| q[i]=((i&(1<<b))&&(i&kmask)==kb1)?1:3; |
| } |
| int r=ask(); |
| if(r==2) P|=(1<<b); |
| } |
| int p1=kb1|(P&amask); |
| int p3=kb3|(P&amask); |
| if(p1<0||p1>=N||p3<0||p3>=N||p1==p3){ |
| p1=-1;p3=-1; |
| for(int i=0;i<N;i++){ |
| if(p1>=0&&p3>=0)break; |
| for(int j=0;j<N;j++)q[j]=3;q[i]=1; |
| int r=ask(); |
| if(r==2)p1=i;else if(r==0)p3=i; |
| } |
| } |
| perm[p1]=1;perm[p3]=3; |
| kc=2; |
| for(int i=0;i<N;i++) q[i]=1; |
| q[p1]=1;q[p3]=3; |
|
|
| vector<int> vals,pos; |
| vals.push_back(2); |
| for(int v=4;v<=N;v++) vals.push_back(v); |
| for(int i=0;i<N;i++) if(i!=p1&&i!=p3) pos.push_back(i); |
|
|
| solve(vals,pos); |
| submit(); |
| } |
|
|
