#include #include #include #include #include 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& vals, vector& 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; } // n=3 handled by general D&C below (2 queries: 1 split + 1 for n=2) int half = n / 2; int right_half = n - half; for (int i = 0; i < n; i++) par[i] = i; vector half_known(n, -1); int left_count = 0, right_count = 0; // Helper: assign a group (by representative) to a half 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++; } } }; // Helper: check if remaining undetermined values can be inferred auto check_early_termination = [&]() -> bool { if (left_count == half) { // All remaining go right 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 same_half_reps; // Phase 1: pair values 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)); } } // Handle odd value 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++; } } // Phase 2: Batch disambiguation 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 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 left_vals, right_vals; vector left_pos(pos.begin(), pos.begin() + half); vector 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();} // Phase 1: Find pos1 and pos3 int B=0;{int tmp=N-1;while(tmp>0){B++;tmp>>=1;}} int rb[12]; for(int b=0;b=N||p3<0||p3>=N||p1==p3){ p1=-1;p3=-1; for(int i=0;i=0&&p3>=0)break; for(int j=0;j vals,pos; vals.push_back(2); for(int v=4;v<=N;v++) vals.push_back(v); for(int i=0;i