#include "cave.h"
#include <vector>
using namespace std;
void exploreCave(int N) {
vector<int> correctState(N, 0); // correct switch positions
vector<int> switchToDoor(N, -1); // which door each switch controls
vector<bool> visited(N, false); // switches that are already assigned
vector<int> test(N, 0); // temporary array for testing
for (int d = 0; d < N; ++d) {
// Binary search to find which switch controls door d
int lo = 0, hi = N - 1;
int controllingSwitch = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
// Set unknown switches from lo to mid to 1, others to 0
for (int i = 0; i < N; ++i) {
if (visited[i]) {
test[i] = correctState[i]; // already known
} else if (i >= lo && i <= mid) {
test[i] = 1;
} else {
test[i] = 0;
}
}
int res = tryCombination(test.data());
if (res == d || res == -1) {
// One of [lo..mid] controls door d
hi = mid - 1;
} else {
lo = mid + 1;
}
}
controllingSwitch = lo;
// Figure out the correct position for the controlling switch
// Set it to 0 first
for (int i = 0; i < N; ++i)
test[i] = visited[i] ? correctState[i] : 0;
test[controllingSwitch] = 0;
int res0 = tryCombination(test.data());
correctState[controllingSwitch] = (res0 == d || res0 == -1) ? 0 : 1;
switchToDoor[controllingSwitch] = d;
visited[controllingSwitch] = true;
}
answer(correctState.data(), switchToDoor.data());
}
