#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int n) {
int pos[n], state[n];
int s[n] = {0};
// int cur = tryCombination(s);
// if (cur == 0) {
// for (int i = 0; i < n; i++) {
// s[i] = 1;
// if (tryCombination(s) > 0) {
// pos[0] = i;
// state[i] = 1;
// break;
// }
// s[i] = 0;
// }
// } else {
// for (int i = 0; i < n; i++) {
// s[i] = 1;
// if (tryCombination(s) == 0) {
// pos[0] = i;
// state[i] = 0;
// break;
// }
// s[i] = 0;
// }
// }
for (int i = 0; i < n; i++) {
int cur = tryCombination(s);
int l = 0, r = n - 1;
if (cur == i) {
while (l < r) {
int m = (l + r) >> 1;
int ss[n];
for (int j = 0; j < n; j++) ss[j] = s[j];
for (int j = 0; j <= m; j++) ss[j] ^= 1;
for (int j = 0; j < i; j++) ss[pos[j]] = state[j];
if (tryCombination(ss) != i) {
r = m;
} else {
l = m + 1;
}
}
pos[i] = l;
state[i] = s[l] ^ 1;
s[l] ^= 1;
} else {
while (l < r) {
int m = (l + r) >> 1;
int ss[n];
for (int j = 0; j < n; j++) ss[j] = s[j];
for (int j = 0; j <= m; j++) ss[j] ^= 1;
for (int j = 0; j < i; j++) ss[pos[j]] = state[j];
if (tryCombination(ss) == i) {
r = m;
} else {
l = m + 1;
}
}
pos[i] = l;
state[i] = s[l];
}
}
int d[n];
for (int i = 0; i < n; i++) {
d[pos[i]] = i;
s[pos[i]] = state[i];
}
answer(s, d);
}
