#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; } if (n == 3) { // Special case: 3 values, 3 positions. // Query 1: assign v0,v1,v2 to pos[0],pos[1],pos[2] q[pos[0]] = vals[0]; q[pos[1]] = vals[1]; q[pos[2]] = vals[2]; int r1 = ask(); q[pos[0]] = 1; q[pos[1]] = 1; q[pos[2]] = 1; if (r1 == kc + 3) { perm[pos[0]]=vals[0]; q[pos[0]]=vals[0]; perm[pos[1]]=vals[1]; q[pos[1]]=vals[1]; perm[pos[2]]=vals[2]; q[pos[2]]=vals[2]; kc += 3; return; } // Query 2: assign v0,v2,v1 q[pos[0]] = vals[0]; q[pos[1]] = vals[2]; q[pos[2]] = vals[1]; int r2 = ask(); q[pos[0]] = 1; q[pos[1]] = 1; q[pos[2]] = 1; if (r2 == kc + 3) { perm[pos[0]]=vals[0]; q[pos[0]]=vals[0]; perm[pos[1]]=vals[2]; q[pos[1]]=vals[2]; perm[pos[2]]=vals[1]; q[pos[2]]=vals[1]; kc += 3; return; } // From the analysis: // (v0,v1,v2): r1=3, r2=1 -> handled above // (v0,v2,v1): r1=1, r2=3 -> handled above // (v1,v0,v2): r1=1, r2=0 // (v1,v2,v0): r1=0, r2=1 // (v2,v0,v1): r1=0, r2=1 // (v2,v1,v0): r1=1, r2=0 // Adjusted for kc offset: int s1 = r1 - kc, s2 = r2 - kc; if (s1 == 1 && s2 == 0) { // (v1,v0,v2) or (v2,v1,v0) // Query 3: test if pos[0] has v1 q[pos[0]] = vals[1]; int r3 = ask(); q[pos[0]] = 1; if (r3 == kc + 1) { // pos[0]=v1 perm[pos[0]]=vals[1]; q[pos[0]]=vals[1]; perm[pos[1]]=vals[0]; q[pos[1]]=vals[0]; perm[pos[2]]=vals[2]; q[pos[2]]=vals[2]; } else { perm[pos[0]]=vals[2]; q[pos[0]]=vals[2]; perm[pos[1]]=vals[1]; q[pos[1]]=vals[1]; perm[pos[2]]=vals[0]; q[pos[2]]=vals[0]; } kc += 3; return; } if (s1 == 0 && s2 == 1) { // (v1,v2,v0) or (v2,v0,v1) q[pos[0]] = vals[1]; int r3 = ask(); q[pos[0]] = 1; if (r3 == kc + 1) { perm[pos[0]]=vals[1]; q[pos[0]]=vals[1]; perm[pos[1]]=vals[2]; q[pos[1]]=vals[2]; perm[pos[2]]=vals[0]; q[pos[2]]=vals[0]; } else { perm[pos[0]]=vals[2]; q[pos[0]]=vals[2]; perm[pos[1]]=vals[0]; q[pos[1]]=vals[0]; perm[pos[2]]=vals[1]; q[pos[2]]=vals[1]; } kc += 3; return; } // Shouldn't reach here // Fallback perm[pos[0]]=vals[0]; q[pos[0]]=vals[0]; perm[pos[1]]=vals[1]; q[pos[1]]=vals[1]; perm[pos[2]]=vals[2]; q[pos[2]]=vals[2]; kc += 3; return; } int half = n / 2; // Initialize Union-Find for (int i = 0; i < n; i++) par[i] = i; vector half_known(n, -1); vector same_half_reps; // Phase 1: pair values for (int vi = 0; vi + 1 < n; vi += 2) { 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; } else if (r == kc) { half_known[vi] = 1; half_known[vi + 1] = 0; } else { Unite(vi, vi + 1); same_half_reps.push_back(Find(vi)); } } // Handle odd value: instead of standalone query, pair it with first same-half group if (n % 2 == 1) { int vi = n - 1; if (!same_half_reps.empty()) { // Pair odd value with a same-half representative int rep = same_half_reps.back(); same_half_reps.pop_back(); int v = vals[vi]; // odd value // Find a value from the same-half group 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) { // v (odd) in left, w (rep group) in right half_known[vi] = 0; for (int i = 0; i < n; i++) { if (Find(i) == Find(rep)) half_known[i] = 1; } } else if (r == kc) { half_known[vi] = 1; for (int i = 0; i < n; i++) { if (Find(i) == Find(rep)) half_known[i] = 0; } } else { // Same half: odd value and entire group are in same half Unite(vi, rep); same_half_reps.push_back(Find(vi)); } } else { // No same-half groups, query alone 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; } } // 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()) { vector next_reps; int si = 0; while (si < (int)same_half_reps.size()) { 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; for (int i = 0; i < n; i++) { if (Find(i) == Find(rep)) half_known[i] = 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) { for (int i = 0; i < n; i++) { if (Find(i) == Find(rep1)) half_known[i] = 0; if (Find(i) == Find(rep2)) half_known[i] = 1; } } else if (r == kc) { for (int i = 0; i < n; i++) { if (Find(i) == Find(rep1)) half_known[i] = 1; if (Find(i) == Find(rep2)) half_known[i] = 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; } 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