File size: 5,113 Bytes
14c9c2b | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 | #include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <random>
using namespace std;
// Global variables
int n;
vector<int> p;
vector<int> pos_of_val;
// Helper to interact with the system
int query(const vector<int>& 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<int>& 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<int> 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<int> candidates = u;
while (candidates.size() > 1) {
int sz = candidates.size();
int mid = sz / 2;
vector<int> L, R;
L.reserve(mid);
R.reserve(sz - mid);
for(int i=0; i<mid; ++i) L.push_back(candidates[i]);
for(int i=mid; i<sz; ++i) R.push_back(candidates[i]);
bool found_split = false;
while (!found_split) {
// Pick random filler f from 2..n
int f = 2 + (rng() % (n - 1));
// Construct query:
// Fill L with 1
// Fill R with f
// Fill all other indices with 1
// Logic:
// Matches from 1: If pos[1] in L or Others, match=1. If pos[1] in R, match=0.
// Matches from f: If pos[f] in R, match=1. If pos[f] in L or Others, match=0.
// Possibilities:
// 1 in L/Others, f in L/Others: Score 1
// 1 in L/Others, f in R: Score 2
// 1 in R, f in L/Others: Score 0
// 1 in R, f in R: Score 1
// So Score 2 => 1 in L (candidates = L)
// Score 0 => 1 in R (candidates = R)
// Score 1 => Ambiguous, retry with different f
vector<int> 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<int> 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<int> cur_candidates = u;
while (cur_candidates.size() > 1) {
int sz = cur_candidates.size();
int mid = sz / 2;
vector<int> L, R;
L.reserve(mid);
for(int i=0; i<mid; ++i) L.push_back(cur_candidates[i]);
for(int i=mid; i<sz; ++i) R.push_back(cur_candidates[i]);
// Query construction:
// 1. Known positions 1..k-1 filled with correct values.
// 2. L filled with k.
// 3. R (and other unknowns) filled with 1.
// 4. Note: p array has 0 for unknowns. We construct q based on this.
vector<int> 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<int> 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;
} |