#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
static vector<int> S, D;
static vector<int> assignedState, assignedDoor;
static vector<int> cand, tmp;
void exploreCave(int N) {
S.assign(N, 0);
D.assign(N, 0);
assignedState.assign(N, -1);
assignedDoor.assign(N, -1);
cand.clear();
cand.reserve(N);
for (int i = 0; i < N; i++) cand.push_back(i);
for (int door = 0; door < N; door++) {
// determine correct state for the switch controlling this door
for (int i = 0; i < N; i++) {
if (assignedState[i] != -1) S[i] = assignedState[i];
else S[i] = 0;
}
int res = tryCombination(S.data());
int targetState = (res == -1 || res > door) ? 0 : 1;
// binary search for the switch in cand controlling this door
while (cand.size() > 1) {
int mid = cand.size() / 2;
for (int i = 0; i < N; i++) S[i] = (targetState ^ 1);
for (int v : cand) {
if (assignedState[v] != -1) {
S[v] = assignedState[v];
} else {
S[v] = (targetState ^ 1);
}
}
for (int i = 0; i < mid; i++) {
int v = cand[i];
if (assignedState[v] == -1) S[v] = targetState;
}
int x = tryCombination(S.data());
bool inFirst = (x == -1 || x > door);
tmp.clear();
tmp.reserve(cand.size());
if (inFirst) {
for (int i = 0; i < mid; i++) tmp.push_back(cand[i]);
} else {
for (size_t i = mid; i < cand.size(); i++) tmp.push_back(cand[i]);
}
cand.swap(tmp);
}
// assign the found switch
int sw = cand[0];
assignedDoor[sw] = door;
assignedState[sw] = targetState;
cand.clear();
cand.reserve(N);
for (int i = 0; i < N; i++) {
if (assignedDoor[i] == -1) cand.push_back(i);
}
}
for (int i = 0; i < N; i++) {
S[i] = assignedState[i];
D[i] = assignedDoor[i];
}
answer(S.data(), D.data());
}
