#include #include #include #include using namespace std; // Function to query int query(const vector& q) { cout << "0"; for (int x : q) { cout << " " << x; } cout << endl; int res; cin >> res; return res; } // Function to submit answer void answer(const vector& p) { cout << "1"; for (int x : p) { cout << " " << x; } cout << endl; exit(0); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; if (!(cin >> n)) return 0; vector p(n, 0); // 0 means unknown if (n == 1) { p[0] = 1; answer(p); return 0; } // Indices 0 to n-1 vector candidates(n); iota(candidates.begin(), candidates.end(), 0); // Step 1: Find pos(1) // We iterate to narrow down the candidate set for 1. // To distinguish if 1 is in Left or Right, we compare against fillers 2, 3, ... vector curr = candidates; while (curr.size() > 1) { int mid = curr.size() / 2; vector L(curr.begin(), curr.begin() + mid); vector R(curr.begin() + mid, curr.end()); int found_side = 0; // -1 Left, 1 Right // Try up to 20 fillers or until N. Usually 1 or 2 suffice. for (int k = 2; k <= min(n, 20); ++k) { // Query A: 1 in L, k in R, k elsewhere vector qA(n, k); for(int idx : L) qA[idx] = 1; // Query B: k in L, 1 in R, k elsewhere vector qB(n, k); for(int idx : R) qB[idx] = 1; int sA = query(qA); int sB = query(qB); // sA - sB = 2 * (I(1 in L) - I(1 in R)) // Because k is symmetric in the swap. if (sA > sB) { found_side = -1; break; } if (sB > sA) { found_side = 1; break; } } // If still 0, it means 1 is together with all checked fillers in the same partition. // This is statistically very unlikely for a random permutation. // Default to Left if indistinguishable (though for valid test cases this shouldn't break logic). if (found_side == 0) found_side = -1; if (found_side == -1) curr = L; else curr = R; } p[curr[0]] = 1; // Step 2: Find pos(k) for k = 2 to N // We can use the known position of 1 as a filler. // Since 1 is at p[pos(1)], putting 1 there yields a match. // Putting 1 elsewhere yields no match (since 1 is unique). // This allows us to count exactly. for (int k = 2; k <= n; ++k) { vector domain; for(int i=0; i current_domain = domain; while (current_domain.size() > 1) { int mid = current_domain.size() / 2; vector L(current_domain.begin(), current_domain.begin() + mid); vector R(current_domain.begin() + mid, current_domain.end()); // Construct query: // Put k in L. // Put 1 in R. // Put 1 in all other unknown positions. // Put known values in their positions. vector q(n, 1); // Default to 1 (filler) for(int i=0; i