#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 ask(){ochar('0');for(int i=0;i& vals, vector& pos, int kc) { int n = vals.size(); if (n == 0) return; if (n == 1) { perm[pos[0]] = vals[0]; q[pos[0]] = vals[0]; return; } if (n == 2) { // Set pos[0] to vals[0], pos[1] to some background from vals // Background for pos[1]: vals[0] is being tested at pos[0]. // But what's at pos[1]? It's vals[0] or vals[1]. // Set pos[0] = vals[0], pos[1] = vals[1] (test both) // Wait, for n=2 with the standard approach: // Set pos[0] = vals[0]. Leave pos[1] = whatever it was (background). // The background for pos[1] should NOT match perm[pos[1]]. // perm[pos[1]] is either vals[0] or vals[1]. // If bg is some value NOT in {vals[0], vals[1]}, no match. // But we might not have such a value available... // // Alternative: set pos[0] = vals[0], pos[1] = vals[0] too (both same value). // matches from pos[]: [perm[pos[0]] == vals[0]] + [perm[pos[1]] == vals[0]] // Exactly one of perm[pos[0]], perm[pos[1]] equals vals[0]. // So internal matches = 1 always. No info! // // Better: set pos[0] = vals[0], pos[1] = vals[1]. // matches = [perm[pos[0]] == vals[0]] + [perm[pos[1]] == vals[1]] // If correct: 2. If swapped: 0. // r = kc + 0 or kc + 2. q[pos[0]] = vals[0]; q[pos[1]] = vals[1]; int r = ask(); if (r == kc + 2) { 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]; } return; } if (n == 3) { q[pos[0]] = vals[0]; q[pos[1]] = vals[1]; q[pos[2]] = vals[2]; int r1 = ask(); int s1 = r1 - kc; if (s1 == 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]; return; } q[pos[0]] = vals[0]; q[pos[1]] = vals[2]; q[pos[2]] = vals[1]; int r2 = ask(); int s2 = r2 - kc; if (s2 == 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]; return; } if (s1 == 1 && s2 == 0) { q[pos[0]] = vals[1]; q[pos[1]] = vals[0]; q[pos[2]] = vals[0]; // only care about pos[0] // Hmm, need to be careful with pos[1] and pos[2] // Set pos[0] = vals[1], others = some safe bg // Safe bg: use vals[0] (it's at pos[0] or pos[1] or pos[2]) // Actually for n=3, perm[pos[1]] and perm[pos[2]] are from {vals[0],vals[1],vals[2]} // If I set pos[1]=vals[0], it matches if perm[pos[1]]=vals[0]. // I don't want noise from pos[1] and pos[2]. // Set pos[1] and pos[2] to a value NOT in vals. But all values 1..N are possible. // The original approach (with kc from known positions outside) uses bg=1. // Here I don't have that luxury. // // BUT: at the top level, there are no external positions. At deeper levels, // external positions contribute to kc. The key is that pos[1] and pos[2]'s // q values should NOT match perm[pos[1]] and perm[pos[2]]. // // For the disambiguation query, I only need pos[0] to be meaningful. // Set pos[0] = vals[1]. // Set pos[1] = vals[2], pos[2] = vals[2]. // matches from pos[]: [perm[pos[0]]==vals[1]] + [perm[pos[1]]==vals[2]] + [perm[pos[2]]==vals[2]] // In case (v1,v0,v2): pos[0]=v1, pos[1]=v0, pos[2]=v2. // match pos[0]: v1==vals[1]? Yes! Match. // match pos[1]: v0==vals[2]? No. // match pos[2]: v2==vals[2]? Yes! // Total internal: 2. r = kc + 2. // In case (v2,v1,v0): pos[0]=v2, pos[1]=v1, pos[2]=v0. // match pos[0]: v2==vals[1]? No. // match pos[1]: v1==vals[2]? No. // match pos[2]: v0==vals[2]? No. // Total internal: 0. r = kc + 0. // Distinguished! r == kc+2 -> (v1,v0,v2), r == kc -> (v2,v1,v0). q[pos[0]] = vals[1]; q[pos[1]] = vals[2]; q[pos[2]] = vals[2]; int r3 = ask(); if (r3 >= kc + 2) { 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]; } return; } if (s1 == 0 && s2 == 1) { // (v1,v2,v0) or (v2,v0,v1) q[pos[0]] = vals[1]; q[pos[1]] = vals[0]; q[pos[2]] = vals[0]; int r3 = ask(); // (v1,v2,v0): pos[0]=v1. match pos[0]: vals[1]==v1? Yes. + pos[1]=v2, q=vals[0], no. + pos[2]=v0, q=vals[0], yes! // Total: kc + 2. // (v2,v0,v1): pos[0]=v2. match: vals[1]==v2? No. + pos[1]=v0, q=vals[0], yes! + pos[2]=v1, q=vals[0], no. // Total: kc + 1. // Hmm, both give 1-2 matches, not cleanly 0 vs 2. // Let me recalculate: // (v1,v2,v0): [vals[1]==vals[1]]=1, [vals[0]==vals[2]]=0, [vals[0]==vals[0]]=1 -> 2 // (v2,v0,v1): [vals[1]==vals[2]]=0, [vals[0]==vals[0]]=1, [vals[0]==vals[1]]=0 -> 1 // Distinguished: kc+2 vs kc+1. if (r3 >= kc + 2) { 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]; } return; } // Unreachable return; } 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; 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 = [&]() -> 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 same_half_reps; for (int vi = 0; vi + 1 < n; vi += 2) { if (check_early()) 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; int matches = r - kc; if (matches == 2) { half_known[vi] = 0; half_known[vi + 1] = 1; left_count++; right_count++; } else if (matches == 0) { 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 && !check_early()) { int vi = n - 1; if (!same_half_reps.empty()) { int rep = same_half_reps.back(); same_half_reps.pop_back(); int v = vals[vi], 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; int matches = r - kc; if (matches == 2) { half_known[vi] = 0; left_count++; assign_group(rep, 1); } else if (matches == 0) { 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; int h = (r - kc == 1) ? 0 : 1; half_known[vi] = h; if (h==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()) break; vector next_reps; int si = 0; while (si < (int)same_half_reps.size()) { if (check_early()) 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; assign_group(rep, (r - kc == 1) ? 0 : 1); 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; int matches = r - kc; if (matches == 2) { assign_group(rep1, 0); assign_group(rep2, 1); } else if (matches == 0) { 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; } 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]); } // Set right positions to a safe background (a left value) // Right positions have values from right_vals. left_vals values won't match. int bg = left_vals.empty() ? 1 : left_vals[0]; for (int i = 0; i < (int)right_pos.size(); i++) q[right_pos[i]] = bg; solve(left_vals, left_pos, kc); // After solving left, left positions are correctly set. // External kc for right = kc + left_vals.size() int new_kc = kc + left_vals.size(); solve(right_vals, right_pos, new_kc); } 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();} for(int i=0;i vals,pos; for(int v=1;v<=N;v++) vals.push_back(v); for(int i=0;i