#include "cave.h"
#include <vector>
using namespace std;
void exploreCave(int N) {
vector<int> s(N, 0); // current guess for switch states
vector<int> finalSwitch(N); // correct states of switches
vector<int> doorToSwitch(N); // which switch controls each door
vector<bool> used(N, false); // mark switches already assigned
for (int d = 0; d < N; ++d) {
int low = 0, high = N - 1, found = -1;
// Binary search to find the switch controlling door d
while (low <= high) {
int mid = (low + high) / 2;
for (int i = 0; i < N; ++i) {
if (used[i]) continue;
s[i] = 0;
}
for (int i = low; i <= mid; ++i) {
if (!used[i]) s[i] = 1;
}
int res = tryCombination(s.data());
if (res == d || res == -1) {
// Found the switch in [low, mid]
found = -1;
for (int i = low; i <= mid; ++i) {
if (!used[i]) {
found = i;
break;
}
}
high = mid - 1;
} else {
low = mid + 1;
}
}
// Find correct state (0 or 1) for switch `found`
s[found] = 0;
for (int i = 0; i < N; ++i)
if (!used[i] && i != found) s[i] = 0;
int res0 = tryCombination(s.data());
finalSwitch[found] = (res0 == d || res0 == -1) ? 0 : 1;
doorToSwitch[found] = d;
used[found] = true;
}
answer(finalSwitch.data(), doorToSwitch.data());
}
