#ifndef LOCAL
#include "cave.h"
#endif
#include <bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(), (a).end()
#define fi first
#define se second
using ll = long long;
const int N = 5000 + 24;
const int MAX_CALL = 70000;
mt19937_64 rng(36363636);
#ifdef LOCAL
int n, real_s[N], real_d[N];
int cnt_query;
int tryCombination(int S[]) {
cnt_query++;
if (cnt_query > MAX_CALL) {
cout << "CALL TOO MUCH" << endl;
exit(0);
}
for (int i = 0; i < n; i++) {
// cout << S[i] << ' ';
}
// cout << endl;
vector<int> state(n);
for (int i = 0; i < n; i++) {
int j = real_d[i];
state[j] = (S[i] == real_s[i]);
}
// cout << "STATE: ";
// for (int j = 0; j < n; j++) cout << state[j] << ' '; cout << endl;
for (int i = 0; i < n; i++) {
if (!state[i]) return i;
// if (!state[i]) return cout << i << endl, i;
}
return -1;
// return cout << -1 << endl, -1;
}
void answer(int S[], int D[]) {
bool valid = 1;
for (int i = 0; i < n; i++) {
if (S[i] != real_s[i]) {
valid = 0;
break;
}
}
for (int i = 0; i < n; i++) {
if (D[i] != real_d[i]) {
valid = 0;
break;
}
}
if (!valid) {
cout << "WRONG ANSWER" << endl;
cout << "EXPECTED OUTPUT" << endl;
for (int i = 0; i < n; i++) cout << real_s[i] << ' '; cout << endl;
for (int i = 0; i < n; i++) cout << real_d[i] << ' '; cout << endl;
cout << "YOUR OUTPUT" << endl;
for (int i = 0; i < n; i++) cout << S[i] << ' '; cout << endl;
for (int i = 0; i < n; i++) cout << D[i] << ' '; cout << endl;
}
else {
cout << "CORRECT" << endl;
}
}
#endif
void exploreCave(int N) {
int n = N;
int state[n], new_state[n];
int can[n], d[n];
for (int i = 0; i < n; i++) {
d[i] = -1;
}
for (int i = 0; i < n; i++) {
state[i] = new_state[i] = 0;
can[i] = 1;
}
for (int i = 0; i < n; i++) {
int k = tryCombination(state);
if (k == -1) break;
int m = tryCombination(can);
if (m != -1 && m < k) {
int pos = -1;
for (int l = 1, r = n - i; l <= r; ) {
int mid = (l + r) >> 1, p;
for (int i = 0; i < n; i++) {
new_state[i] = state[i];
}
for (int i = 0, j = 0; i < n; i++) {
if (can[i]) {
new_state[i] = 1;
if (!state[i]) j++;
}
if (j == mid) {
p = i;
break;
}
}
// cout << mid << '.' << p << endl;
int jury_ans = tryCombination(new_state);
if (jury_ans == m) {
pos = p;
r = mid - 1;
}
else l = mid + 1;
}
if (pos != -1) {
can[pos] = 0;
d[pos] = m;
// cout << "POS = " << pos << "\n";
}
}
else {
int pos = -1;
for (int l = 1, r = n - i; l <= r; ) {
int mid = (l + r) >> 1, p;
for (int i = 0; i < n; i++) {
new_state[i] = state[i];
}
for (int i = 0, j = 0; i < n; i++) {
if (can[i]) {
new_state[i] = 1;
if (!state[i]) j++;
}
if (j == mid) {
p = i;
break;
}
}
// cout << mid << '.' << p << endl;
int jury_ans = tryCombination(new_state);
if (jury_ans == -1 || jury_ans > k) {
pos = p;
r = mid - 1;
}
else l = mid + 1;
}
if (pos != -1) {
// cout << "POS = " << pos << "\n";
state[pos] = 1;
d[pos] = k;
}
}
// cout << cnt_query << endl;
}
for (int i = 0; i < n; i++) {
if (d[i] != -1) continue;
for (int j = 0; j < n; j++) {
new_state[j] = state[j];
}
new_state[i] ^= 1;
d[i] = tryCombination(new_state);
}
return answer(state, d);
}
#ifdef LOCAL
void solve() {
// cin >> n;
n = 5000;
cnt_query = 0;
for (int i = 0; i < n; i++) {
// cin >> real_s[i];
real_s[i] = rng() % 2;
}
for (int i = 0; i < n; i++) {
// cin >> real_d[i];
real_d[i] = i;
}
shuffle(real_d, real_d + n, rng);
exploreCave(n);
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int T = 100; // cin >> T;
while (T--) {
solve();
}
}
#endif
