#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N){
vector<int> S(N, 0);
vector<int> D(N);
vector<bool> used(N, false);
for (int door = 0; door < N; ++door) {
vector<int> test(N, 0);
for (int i = 0; i < N; ++i)
if (used[i]) test[i] = S[i];
int res = tryCombination(test.data());
int target = (res == -1 || res > door) ? 0 : 1;
int lo = 0, hi = N - 1, switchIndex = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
for (int i = 0; i < N; ++i)
test[i] = used[i] ? S[i] : target;
for (int i = lo; i <= mid; ++i)
if (!used[i]) test[i] = 1 - target;
res = tryCombination(test.data());
if (res == -1 || res > door) {
hi = mid - 1;
switchIndex = mid;
} else {
lo = mid + 1;
}
}
D[door] = switchIndex;
S[switchIndex] = target;
used[switchIndex] = true;
}
answer(S.data(), D.data());
}
