#include <vector>
#include "cave.h"
void exploreCave(int N) {
std::vector <int> finalSwitch(N), finalS(N);
int S[N], D[N];
std::vector <bool> found(N);
for (int i = 0; i < N; i++) {
S[i] = 0;
D[i] = i;
found[i] = false;
}
for (int i = 0; i < N; i++) {
int tmp[N];
for (int j = 0; j < N; j++) {
tmp[j] = S[j];
}
int door = tryCombination(tmp);
finalS[i] = 1;
if (door != i) {
finalS[i] = 0;
for (int j = 0; j < N; j++) {
if (found[j] == false) {
tmp[j] = 1 - tmp[j];
}
}
}
int lo = 0, hi = N - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
for (int j = lo; j <= mid; j++) {
if (found[j] == false) {
tmp[j] = 1 - tmp[j];
}
}
door = tryCombination(tmp);
if (door != i) {
finalSwitch[i] = mid;
hi = mid - 1;
for (int j = lo; j <= mid; j++) {
if (found[j] == false) {
tmp[j] = 1 - tmp[j];
}
}
}
else {
lo = mid + 1;
}
}
found[finalSwitch[i]] = true;
S[finalSwitch[i]] = finalS[i];
D[finalSwitch[i]] = i;
}
answer(S, D);
}
