#include "cave.h"
#include "bits/stdc++.h"
using namespace std;
void exploreCave(int N) {
int S[N], D[N];
bool fixed[N];
for (int i = 0; i < N; i++) S[i] = 0, D[i] = -1, fixed[i] = false;
int curr;
for (int i = 0; i < N; i++) {
curr = tryCombination(S);
if (curr == i) {
int low = 0, high = N - 1, mid, best = -1;
while (low <= high) {
mid = (low + high) >> 1;
int lb = low, rb = mid;
for (int j = lb; j <= rb; j++) {
if (!fixed[j]) S[j] = 1;
}
curr = tryCombination(S);
if (curr != i || curr == -1) high = mid - 1, best = mid;
else low = mid + 1;
for (int j = lb; j <= rb; j++) if (!fixed[j]) S[j] = 0;
}
D[best] = i, S[best] = 1, fixed[best] = true;
} else {
int low = 0, high = N - 1, mid, best = -1;
while (low <= high) {
mid = (low + high) >> 1;
int lb = low, rb = mid;
for (int j = lb; j <= rb; j++) {
if (!fixed[j]) S[j] = 1;
}
curr = tryCombination(S);
if (curr == i) high = mid - 1, best = mid;
else low = mid + 1;
for (int j = lb; j <= rb; j++) if (!fixed[j]) S[j] = 0;
}
D[best] = i, S[best] = 0, fixed[best] = true;
}
}
answer(S, D);
}
