#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;
//for (int i = 0; i < n; ++i)
//cout << cur[i] << ' ';
//cout << '\n';
vector<int> solved(n);
for (int i = 0; i < n; ++i) {
int spos, dpos = 0;
auto ok = [&](int cur[]) {
int ok = tryCombination(cur);
//cout << "TRYCOMB " << i << ' ' << ok << '\n';
return !(ok > i || ok == -1);
};
spos = ok(cur);
//cout << i << ' ' << spos << '\n';
for (int j = 1; j <= N; ++j) {
for (int t = 0; t < n; ++t)
pos[t] = cur[t];
//cout << "POSB CHECK : ";
//for (int i = 0; i < n; ++i)
//cout << pos[i] << ' ';
//cout << '\n';
for (int k = dpos; k < n; k += (1 << j))
if (!solved[k])
pos[k] = 1;
//cout << "POSA CHECK : ";
//for (int i = 0; i < n; ++i)
//cout << pos[i] << ' ';
//cout << '\n';
dpos |= ((ok(pos) ^ spos ^ 1) << (j - 1));
}
for (int t = 0; t < n; ++t)
pos[t] = cur[t];
//cout << "DB " << dpos << '\n';
if (!solved[dpos]) {
pos[dpos] = 1;
dpos |= ((ok(pos) ^ spos ^ 1) << N);
}
else
dpos |= 1 << N;
//cout << "DA " << dpos << '\n';
cur[dpos] = spos;
d[dpos] = i;
s[dpos] = spos;
solved[dpos] = 1;
//cout << "CUR CHECK : ";
//for (int i = 0; i < n; ++i)
//cout << cur[i] << ' ';
//cout << '\n';
}
answer(s, d);
}
