File size: 3,883 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 | #include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> perm(n + 1, 0);
set<int> rem_val, rem_pos;
for (int i = 1; i <= n; i++) {
rem_val.insert(i);
rem_pos.insert(i);
}
auto find_pair_pos = [&](int u, int w) -> pair<int, int> {
vector<vector<char>> possible(n + 1, vector<char>(n + 1, 0));
int num_unk = rem_pos.size();
int known_cnt = n - num_unk;
for (int i = 1; i <= n; i++) {
if (perm[i] != 0) continue;
for (int j = 1; j <= n; j++) {
if (perm[j] != 0 || i == j) continue;
possible[i][j] = 1;
}
}
while (true) {
vector<vector<int>> cum(n + 2, vector<int>(n + 2, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int val = possible[i][j];
cum[i][j] = val + cum[i - 1][j] + cum[i][j - 1] - cum[i - 1][j - 1];
}
}
long long total = cum[n][n];
if (total <= 1) {
pair<int, int> res = {-1, -1};
if (total == 1) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (possible[i][j]) {
res = {i, j};
}
}
}
}
return res;
}
int best_t = 1;
long long best_max = LLONG_MAX;
for (int t = 1; t < n; t++) {
long long A = cum[t][t];
long long B = cum[t][n] - A;
long long C = cum[n][t] - A;
long long D = total - A - B - C;
long long n0 = C;
long long n1 = A + D;
long long n2 = B;
long long mx = max({n0, n1, n2});
if (mx < best_max) {
best_max = mx;
best_t = t;
}
}
vector<int> Q(n + 1);
for (int i = 1; i <= n; i++) {
if (perm[i] != 0) {
Q[i] = perm[i];
} else if (i <= best_t) {
Q[i] = u;
} else {
Q[i] = w;
}
}
cout << 0;
for (int i = 1; i <= n; i++) cout << " " << Q[i];
cout << endl;
cout.flush();
int x;
cin >> x;
int effective_x = x - known_cnt;
vector<vector<char>> new_p(n + 1, vector<char>(n + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (possible[i][j]) {
int i1 = (i <= best_t ? 1 : 0);
int i2 = (j > best_t ? 1 : 0);
int comp = i1 + i2;
if (comp == effective_x) {
new_p[i][j] = 1;
}
}
}
}
possible = std::move(new_p);
}
};
while (rem_val.size() > 1) {
auto it = rem_val.begin();
int u = *it;
rem_val.erase(it);
it = rem_val.begin();
int w = *it;
rem_val.erase(it);
pair<int, int> pr = find_pair_pos(u, w);
int pu = pr.first;
int pw = pr.second;
perm[pu] = u;
perm[pw] = w;
rem_pos.erase(pu);
rem_pos.erase(pw);
}
if (!rem_val.empty()) {
int u = *rem_val.begin();
int p = *rem_pos.begin();
perm[p] = u;
}
cout << 1;
for (int i = 1; i <= n; i++) cout << " " << perm[i];
cout << endl;
cout.flush();
return 0;
} |