#include "cave.h"
#include <vector>
#include <ranges>
using namespace std;
const int max_N = 5000;
// toTry[s] is the position of switch s to try the next time.
// For switches whose correct position is known, toTry[s]
// is frozen to the correct position.
int toTry[max_N];
// The switches whose door isn't yet known.
vector<int> remainingSwitches;
// door[i] is the door number connected to switch i.
int door[max_N];
void solve(int d);
void exploreCave(int N) {
remainingSwitches.resize(N);
for(int i : views::iota(0,N)) {
remainingSwitches[i] = i;
}
for(int d : views::iota(0,N)) {
solve(d);
}
answer(toTry, door);
}
// Tries with the configuration toTry, and returns whether door d is open,
// assuming all earlier doors are open.
bool isDoorOpen(int d) {
int firstClosedDoor = tryCombination(toTry);
return (firstClosedDoor == -1 || firstClosedDoor > d);
}
// Solve for door d, assuming all previous doors have been solved.
void solve(int d) {
for(int s : remainingSwitches) {
toTry[s] = 0;
}
int correctSwitchPosition = isDoorOpen(d) ? 0 : 1;
int L = 0, U = remainingSwitches.size();
// Invariant: The correct switch corresponding to door d is remainingSwitches[i]
// for some i in [L, U).
while(U-L > 1) {
int mid = L+(U-L)/2;
for(int q : views::iota(L, mid)) {
toTry[remainingSwitches[q]] = correctSwitchPosition;
}
for(int q : views::iota(mid, U)) {
toTry[remainingSwitches[q]] = 1-correctSwitchPosition;
}
if(isDoorOpen(d)) {
U = mid;
} else {
L = mid;
}
}
int switchForThisDoor = remainingSwitches[L];
door[switchForThisDoor] = d;
toTry[switchForThisDoor] = correctSwitchPosition;
remainingSwitches.erase(remainingSwitches.begin() + L);
}
