#include #include #include #include #include using namespace std; // Helper to interact with the judge int query(const vector& q) { cout << "0"; for (int x : q) cout << " " << x; cout << endl; int res; cin >> res; return res; } // Helper to output the answer void guess(const vector& p) { cout << "1"; for (int x : p) cout << " " << x; cout << endl; exit(0); } int main() { // Optimize I/O operations, though for interactive problems flushing is key ios_base::sync_with_stdio(false); cin.tie(NULL); int n; if (!(cin >> n)) return 0; if (n == 1) { guess({1}); return 0; } vector p(n + 1, 0); // We want to find one position with a known value to use as a pivot. // We look for pos[1] or pos[2]. // Query strategy: q[i] = 1, others = 2. // If res == 2: p[i] == 1 (since pos[1]=i and pos[2]!=i). // If res == 0: p[i] == 2 (since pos[1]!=i and pos[2]=i). // If res == 1: neither (pos[1]!=i and pos[2]!=i). // We scan indices in random order to avoid worst-case inputs. vector probe_order(n); iota(probe_order.begin(), probe_order.end(), 1); mt19937 rng(1337); shuffle(probe_order.begin(), probe_order.end(), rng); int base_idx = -1; int base_val = -1; // This loop takes at most N queries (guaranteed to find 0 or 2) for (int idx : probe_order) { vector q(n); for (int i = 0; i < n; ++i) { if (i + 1 == idx) q[i] = 1; else q[i] = 2; } int res = query(q); if (res == 2) { base_idx = idx; base_val = 1; break; } else if (res == 0) { base_idx = idx; base_val = 2; break; } } // We record the found value p[base_idx] = base_val; // available indices for the remaining values vector available; for (int i = 1; i <= n; ++i) { if (i != base_idx) available.push_back(i); } // values we still need to locate vector to_find; for (int v = 1; v <= n; ++v) { if (v != base_val) to_find.push_back(v); } int found_count = 1; // currently we know 1 position // For each remaining value, binary search its position among available indices // This takes Sum(log2(k)) queries, which is ~ N log N but specifically log(N!) < 8600 for N=1000 for (int val : to_find) { int l = 0; int r = available.size() - 1; while (l < r) { int mid = l + (r - l) / 2; // Construct query // Base: fill with base_val (known to be non-matching for unknown positions because base_val is unique at base_idx) // Known positions: fill with their correct values (contributes found_count matches) // Range [l, mid]: fill with target val (contributes +1 if pos[val] is here) vector q(n); for(int i=1; i<=n; ++i) { if(p[i] != 0) { q[i-1] = p[i]; } else { q[i-1] = base_val; } } // Overwrite probe range with candidate value for (int k = l; k <= mid; ++k) { int idx = available[k]; q[idx-1] = val; } int res = query(q); // If val is in the probed range, we get one extra match if (res == found_count + 1) { r = mid; } else { l = mid + 1; } } // available[l] is the position of val int pos = available[l]; p[pos] = val; found_count++; // Remove pos from available. erase is O(K), total loop is O(N^2) which is fine for N=1000 available.erase(available.begin() + l); } // Output result vector ans; for (int i = 1; i <= n; ++i) ans.push_back(p[i]); guess(ans); return 0; }