#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
vector<int> S(N, 0), D(N, -1);
vector<int> fixedState(N, -1);
vector<int> rem;
rem.reserve(N);
for (int i = 0; i < N; i++) rem.push_back(i);
for (int door = 0; door < N; door++) {
for (int i = 0; i < N; i++) {
if (fixedState[i] != -1) S[i] = fixedState[i];
else S[i] = 0;
}
int r = tryCombination(S.data());
int need = (r == door ? 1 : 0);
int lo = 0, hi = (int)rem.size() - 1;
while (lo < hi) {
int mid = (lo + hi) >> 1;
for (int i = 0; i < N; i++) {
if (fixedState[i] != -1) S[i] = fixedState[i];
else S[i] = (need ^ 1);
}
for (int k = lo; k <= mid; k++) S[rem[k]] = need;
int x = tryCombination(S.data());
bool ok = (x == -1 || x > door);
if (ok) hi = mid;
else lo = mid + 1;
}
int sw = rem[lo];
fixedState[sw] = need;
D[sw] = door;
rem.erase(rem.begin() + lo);
}
for (int i = 0; i < N; i++) S[i] = fixedState[i];
answer(S.data(), D.data());
}
