#include #include #include #include using namespace std; int N, perm[1001], unk[1001], us, kc; // Use a large output buffer static char obuf[1 << 22]; static int opos; inline void oflush() { fwrite_unlocked(obuf, 1, opos, stdout); opos = 0; fflush(stdout); } inline void ochar(char c) { obuf[opos++] = c; } inline 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); } // Pre-built query line. q[i] is the value for position i. int q[1001]; // Output query and read result inline 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; } inline void submit() { ochar('1'); for (int i = 0; i < N; i++) { ochar(' '); oint(perm[i]); } ochar('\n'); oflush(); exit(0); } int bsearch_range(int v, int lo, int hi) { while (lo < hi) { int mid = (lo + hi) / 2; for (int i = lo; i <= mid; i++) q[unk[i]] = v; int r = ask(); for (int i = lo; i <= mid; i++) q[unk[i]] = 1; if (r == kc + 1) hi = mid; else lo = mid + 1; } return lo; } 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 using bit queries 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; us = 0; for (int i = 0; i < N; i++) if (i != p1 && i != p3) unk[us++] = i; for (int i = 0; i < N; i++) q[i] = 1; q[p1] = 1; q[p3] = 3; // Phase 2: Paired binary search vector vals; vals.push_back(2); for (int v = 4; v <= N; v++) vals.push_back(v); int vi = 0; while (vi < (int)vals.size()) { if (us == 0) break; if (us == 1) { perm[unk[0]] = vals[vi]; q[unk[0]] = vals[vi]; us = 0; kc++; vi++; continue; } int v = vals[vi]; bool paired = (vi + 1 < (int)vals.size() && us >= 2); int w = paired ? vals[vi + 1] : -1; if (!paired) { int idx = bsearch_range(v, 0, us - 1); perm[unk[idx]] = v; q[unk[idx]] = v; for (int i = idx; i < us - 1; i++) unk[i] = unk[i + 1]; us--; kc++; vi++; continue; } // Paired binary search int lo = 0, hi = us - 1; int idx_v = -1, idx_w = -1; while (idx_v < 0 || idx_w < 0) { if (hi == lo) break; // shouldn't happen with 2 values if (hi - lo == 1) { q[unk[lo]] = v; int r = ask(); q[unk[lo]] = 1; if (r == kc + 1) { idx_v = lo; idx_w = hi; } else { idx_v = hi; idx_w = lo; } break; } int mid = (lo + hi) / 2; // Paired query: left=v, right=w for (int i = lo; i <= mid; i++) q[unk[i]] = v; for (int i = mid + 1; i <= hi; i++) q[unk[i]] = w; int r = ask(); for (int i = lo; i <= mid; i++) q[unk[i]] = 1; for (int i = mid + 1; i <= hi; i++) q[unk[i]] = 1; if (r == kc + 2) { // v left, w right idx_v = bsearch_range(v, lo, mid); idx_w = bsearch_range(w, mid + 1, hi); } else if (r == kc) { // v right, w left idx_v = bsearch_range(v, mid + 1, hi); idx_w = bsearch_range(w, lo, mid); } else { // Same half - disambiguate for (int i = lo; i <= mid; i++) q[unk[i]] = v; int r2 = ask(); for (int i = lo; i <= mid; i++) q[unk[i]] = 1; if (r2 == kc + 1) hi = mid; else lo = mid + 1; } } if (idx_v >= 0 && idx_w >= 0) { perm[unk[idx_v]] = v; q[unk[idx_v]] = v; perm[unk[idx_w]] = w; q[unk[idx_w]] = w; int r1 = idx_v, r2 = idx_w; if (r1 > r2) { int t = r1; r1 = r2; r2 = t; } for (int i = r2; i < us - 1; i++) unk[i] = unk[i + 1]; us--; for (int i = r1; i < us - 1; i++) unk[i] = unk[i + 1]; us--; kc += 2; vi += 2; } else { int idx = bsearch_range(v, 0, us - 1); perm[unk[idx]] = v; q[unk[idx]] = v; for (int i = idx; i < us - 1; i++) unk[i] = unk[i + 1]; us--; kc++; vi++; } } if (us > 0) { for (int v = 1; v <= N; v++) { bool f = false; for (int i = 0; i < N; i++) if (perm[i] == v) { f = true; break; } if (!f) { perm[unk[--us]] = v; if (!us) break; } } } submit(); }