#include "cave.h"
#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using vi = vector<int>;
const int MAXN = 5'000;
int switches[MAXN];
// door triggered by switchID
int door[MAXN];
int gN;
// returns N instead of -1 when all doors are open
int getLastDoor()
{
int lastDoor = tryCombination(switches);
if (lastDoor == -1)
lastDoor = gN;
return lastDoor;
}
void flipSwitches(int i, int j, vi &ids)
{
for (int k = i; k <= j; k++)
switches[ids[k]] = !switches[ids[k]];
}
void exploreCave(int N)
{
gN = N;
vi unassignedSwitches;
for (int i = 0; i < N; i++)
unassignedSwitches.push_back(i);
// doors up to curDoor EXCEPT curDoor are open
for (int curDoor = 0; curDoor < N; curDoor++)
{
int doorOpen = getLastDoor() > curDoor;
int respSwitch;
int lo = 0, hi = unassignedSwitches.size() - 1;
while (lo < hi)
{
int mid = (lo + hi) / 2;
flipSwitches(lo, mid, unassignedSwitches);
int lastDoor = getLastDoor();
bool check = false;
if (doorOpen)
{
if (lastDoor == curDoor)
check = true;
}
else if (lastDoor > curDoor)
check = true;
if (check)
hi = mid;
else
lo = mid + 1;
flipSwitches(lo, mid, unassignedSwitches);
}
respSwitch = lo;
unassignedSwitches.erase(find(all(unassignedSwitches), respSwitch));
door[respSwitch] = curDoor;
if (!doorOpen)
switches[respSwitch] = !switches[respSwitch];
}
answer(switches, door);
}
