#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
void exploreCave(int N) {
int S[N], D[N];
bool used[N] = {false};
for (int door = 0; door < N; door++) {
int comb[N];
int l = 0, r = N - 1;
int switchIndex = -1;
// Binary search over unused switches
while (l <= r) {
int mid = (l + r) / 2;
// Reset combination
for (int i = 0; i < N; i++) {
comb[i] = used[i] ? S[i] : 0;
}
// Set switches in range [l, mid] to 1
for (int i = l; i <= mid; i++) {
if (!used[i]) comb[i] = 1;
}
int result = tryCombination(comb);
if (result == -1 || result > door) {
// The switch is in [l, mid]
r = mid;
} else {
// The switch is in [mid + 1, r]
l = mid + 1;
}
if (l == r) {
switchIndex = l;
break;
}
}
// Determine correct state of switch
for (int i = 0; i < N; i++) {
comb[i] = used[i] ? S[i] : 0;
}
comb[switchIndex] = 0;
if (tryCombination(comb) == door) {
S[switchIndex] = 1;
} else {
S[switchIndex] = 0;
}
D[switchIndex] = door;
used[switchIndex] = true;
}
answer(S, D);
}
