#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 half, vector& is_left) { int n = vals.size(); is_left.resize(n); // Phase 1: pair up values and do paired queries // Track same-half pairs for batched disambiguation vector determined; // indices into vals that are determined vector> same_half_pairs; // pairs of indices that are in the same half int vi = 0; while (vi < n) { if (vi + 1 >= n) { // Odd value out - query directly 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; is_left[vi] = (r == kc + 1); vi++; continue; } int v = vals[vi], w = vals[vi + 1]; // Paired query: left=v, right=w for (int i = 0; i < half; i++) q[pos[i]] = v; for (int i = half; i < (int)pos.size(); i++) q[pos[i]] = w; int r = ask(); for (int i = 0; i < half; i++) q[pos[i]] = 1; for (int i = half; i < (int)pos.size(); i++) q[pos[i]] = 1; if (r == kc + 2) { is_left[vi] = true; is_left[vi + 1] = false; } else if (r == kc) { is_left[vi] = false; is_left[vi + 1] = true; } else { // Same half - defer disambiguation same_half_pairs.push_back({vi, vi + 1}); } vi += 2; } // Phase 2: Batch disambiguation of same-half pairs. // Each pair (i,j) means vals[i] and vals[j] are in the same half. // We need to determine which half. // Strategy: pair up these pairs and use paired queries on representatives. while (!same_half_pairs.empty()) { vector> next_round; int si = 0; while (si < (int)same_half_pairs.size()) { if (si + 1 >= (int)same_half_pairs.size()) { // Odd pair - query directly auto [i, j] = same_half_pairs[si]; int v = vals[i]; 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; bool left = (r == kc + 1); is_left[i] = left; is_left[j] = left; si++; continue; } // Pair two same-half pairs and query auto [i1, j1] = same_half_pairs[si]; auto [i2, j2] = same_half_pairs[si + 1]; int v = vals[i1], w = vals[i2]; // Paired query: left=v, right=w for (int k = 0; k < half; k++) q[pos[k]] = v; for (int k = half; k < (int)pos.size(); k++) q[pos[k]] = w; int r = ask(); for (int k = 0; k < half; k++) q[pos[k]] = 1; for (int k = half; k < (int)pos.size(); k++) q[pos[k]] = 1; if (r == kc + 2) { // v in left, w in right is_left[i1] = true; is_left[j1] = true; is_left[i2] = false; is_left[j2] = false; } else if (r == kc) { // v in right, w in left is_left[i1] = false; is_left[j1] = false; is_left[i2] = true; is_left[j2] = true; } else { // Same half again! All 4 values in same half. // Group them: (i1,j1,i2,j2) all in same half. // For next round, treat as a single "super pair" with representative i1. // Actually, just pair them again: one representative per group. // We know i1,j1,i2,j2 all in same half. // Create a new pair entry for the next round. // Use i1 as representative for the group of 4. // Store all 4 indices somewhere. // Actually, let's just store one representative per group and a list of dependents. // For simplicity, just re-add (i1, i2) as a pair with j1,j2 as dependents. // When we determine i1's half, set j1,i2,j2 to the same. // Simple approach: mark j1 and j2 as depending on i1 and i2 respectively. // But they're already co-located. Let me just re-add as a single group. // For the next round, (i1, i2) is a same-half pair. // i1 carries j1 as a dependent. i2 carries j2. // When i1's half is determined, so is j1, i2, j2. // Simplest: just track that i1 and i2 are in the same half. // j1 and j2 are already known to be in the same half as i1 and i2 respectively. // So all 4 are in the same half. // Add (i1, i2) to next_round. When resolved, set all 4. // But we need to propagate: when i1 is determined, also set j1, i2, j2. // This requires tracking the groups. // Simplest implementation: use Union-Find to group all co-half values. // Then in each round, pick one representative per group and pair them. next_round.push_back({i1, i2}); // All 4 will be in the same half. When (i1,i2) is resolved in a future round, // we need is_left[i1]=is_left[j1]=is_left[i2]=is_left[j2]. // Since j1 is already linked to i1 and j2 to i2, we just need i1 and i2 to be resolved. // In the next round, (i1,i2) is a same-half pair. When it's determined, // is_left[i1] = is_left[i2] = some value. Then j1 and j2 also get that value. // But wait, is_left[j1] should already be set to the same as is_left[i1] from the original same_half_pairs entry. // Hmm, is_left[j1] hasn't been set yet (it's uninitialized for same_half entries). } si += 2; } same_half_pairs = next_round; } // Now propagate: for each original same-half pair (i,j), set is_left[j] = is_left[i]. // But the propagation is implicit in the batched resolution above. // Wait - I only set is_left for the FIRST index of each pair when resolving. // Need to also set the second index. // Actually, in the code above, when we resolve a pair (i1,i2) from the next_round, // we set is_left[i1] and is_left[i2] directly. And the j1,j2 from the original pairs // are NOT set. // BUG: I need to propagate is_left from representatives to all group members. // This requires a proper Union-Find or group tracking. } // Hmm, this is getting complicated. Let me use Union-Find. int parent[1001]; int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); } void unite(int a, int b) { parent[find(a)] = find(b); } void solve(vector& 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; } int half = n / 2; // Initialize Union-Find for this level for (int i = 0; i < n; i++) parent[i] = i; // Determine which half each value is in vector half_known(n, -1); // -1=unknown, 0=left, 1=right // Phase 1: pair values, do paired queries vector same_half_reps; // representatives of same-half groups // Initial pairing: consecutive pairs 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 { // Same half unite(vi, vi + 1); same_half_reps.push_back(find(vi)); } } // Handle odd value if (n % 2 == 1) { int vi = n - 1; 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 // Deduplicate same_half_reps 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()) { // Odd group - query directly int rep = same_half_reps[si]; // Find any value in this group 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) { // Group 1 in left, group 2 in right 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 { // Same half again - merge groups 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; } // Split into left and right 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