#include #include #include #include #include using namespace std; // Global variables int n; vector p; vector pos_of_val; // Helper to interact with the system int query(const vector& q) { cout << "0"; for (int x : q) { cout << " " << x; } cout << endl; int res; cin >> res; return res; } // Helper to output answer void answer(const vector& ans) { cout << "1"; for (int x : ans) { cout << " " << x; } cout << endl; exit(0); } int main() { // Optimization for faster I/O ios_base::sync_with_stdio(false); cin.tie(NULL); if (!(cin >> n)) return 0; p.assign(n, 0); pos_of_val.assign(n + 1, -1); // Initial unknown indices vector u(n); iota(u.begin(), u.end(), 0); // Trivial case n=1 if (n == 1) { answer({1}); } // Random number generator mt19937 rng(1337); // Step 1: Find position of 1 // We do binary search on the set of candidate indices. // Since we don't have a "safe" filler value yet (we don't know any positions), // we use a randomized strategy to distinguish which half 1 is in. vector candidates = u; while (candidates.size() > 1) { int sz = candidates.size(); int mid = sz / 2; vector L, R; L.reserve(mid); R.reserve(sz - mid); for(int i=0; i 1 in L (candidates = L) // Score 0 => 1 in R (candidates = R) // Score 1 => Ambiguous, retry with different f vector q(n, 1); for(int idx : R) q[idx] = f; int s = query(q); if (s == 2) { candidates = L; found_split = true; } else if (s == 0) { candidates = R; found_split = true; } } } int pos1 = candidates[0]; p[pos1] = 1; pos_of_val[1] = pos1; // Remove pos1 from unknown indices u vector next_u; next_u.reserve(n-1); for(int idx : u) { if(idx != pos1) next_u.push_back(idx); } u = next_u; // Step 2: Find positions of 2..n-1 // Now we have a safe filler: value 1. // Since we know where 1 is, and for all currently unknown indices the value is > 1, // putting 1 in unknown spots yields 0 matches. for (int k = 2; k < n; ++k) { vector cur_candidates = u; while (cur_candidates.size() > 1) { int sz = cur_candidates.size(); int mid = sz / 2; vector L, R; L.reserve(mid); for(int i=0; i q(n, 1); // Default filler 1 for (int v = 1; v < k; ++v) { q[pos_of_val[v]] = v; } for (int idx : L) { q[idx] = k; } // Expected matches: // From knowns: k - 1 matches. // From 1-filler in R/Others: 0 matches (since unknowns are >= k > 1). // From k in L: 1 match if pos[k] in L, else 0. int s = query(q); if (s == k) { // (k-1) + 1 match cur_candidates = L; } else { // (k-1) + 0 matches cur_candidates = R; } } int posk = cur_candidates[0]; p[posk] = k; pos_of_val[k] = posk; // Remove found index from u vector nu; nu.reserve(u.size()-1); for(int idx : u) { if(idx != posk) nu.push_back(idx); } u = nu; } // The last remaining position must be n if (!u.empty()) { p[u[0]] = n; } answer(p); return 0; }