#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
void exploreCave(int n) {
int* s = new int[n], * d = new int[n], * cur = new int[n], * pos = new int[n], N = 31 - __builtin_clz(n);
for (int i = 0; i < n; ++i)
cur[i] = s[i] = d[i] = pos[i] = 0;
vector<int> solved(n);
for (int i = 0; i < n; ++i) {
int spos, dpos = 0;
auto ok = [&](int cur[]) {
int ok = tryCombination(cur);
return !(ok > i || ok == -1);
};
spos = ok(cur);
for (int j = 1; j <= N; ++j) {
for (int t = 0; t < n; ++t)
pos[t] = cur[t];
for (int k = dpos; k < n; k += (1 << j))
if (!solved[k])
pos[k] = 1;
dpos |= ((ok(pos) ^ spos ^ 1) << (j - 1));
}
if (!solved[dpos]) {
for (int t = 0; t < n; ++t)
pos[t] = cur[t];
pos[dpos] = 1;
dpos |= ((ok(pos) ^ spos ^ 1) << N);
}
else
dpos |= 1 << N;
cur[dpos] = s[dpos] = spos;
d[dpos] = i;
solved[dpos] = 1;
}
answer(s, d);
}
