#include"cave.h"
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 5e3;
int S[MAX_N + 5], D[MAX_N + 5];
vector<int> Switches;
///find switch for first door of set
int solve(int l, int r, int pos, int numDoor) {
if(l == r) {
return Switches[l];
}
int mid = (l + r) / 2;
for(int i = l; i <= mid; i++) S[Switches[i]] = pos;
for(int i = mid + 1; i <= r; i++) S[Switches[i]] = 1 - pos;
int door = tryCombination(S);
if(door > numDoor || door == -1) return solve(l, mid, pos, numDoor);
for(int i = l; i <= mid; i++) S[Switches[i]] = 1 - pos;
for(int i = mid + 1; i <= r; i++) S[Switches[i]] = pos;
return solve(mid + 1, r, pos, numDoor);
}
void exploreCave(int N) {
for(int i = 0; i < N; i++) {
Switches.push_back(i);
}
for(int numDoor = 0; numDoor < N; numDoor++) {
for(auto e : Switches) {
S[e] = 0;
}
int pos, door = tryCombination(S);
if(door > numDoor || door == -1) {
pos = 0;
}
else {
pos = 1;
}
int numSwitch = solve(0, Switches.size() - 1, pos, numDoor);
D[numSwitch] = numDoor;
S[numSwitch] = pos;
Switches.erase(lower_bound(Switches.begin(), Switches.end(), numSwitch));
//cout << numSwitch << " " << numDoor << " " << pos << "\n";
}
answer(S, D);
}
