#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
unordered_map<int, int> door, s; // u[i] = j -> switch j is for door i
// initialize door
for(int i=0; i<N; i++) s[i] = -1;
for(int i=0; i<N; i++){ // iterate doors
int buffer[N];
for(int j=0; j<N; j++){
if(s[j] != -1) buffer[j] = s[j];
else buffer[j] = 1; // arbitrary
}
int switchdoor; // switch mode for door i (0 / 1)
if(tryCombination(buffer) == i){
switchdoor = 0;
}else{
switchdoor = 1;
}
int l = 0, r = N - 1;
while(l < r){
int mid = (l + r) / 2;
for(int j=l; j<=mid; j++){
if(s[j] != -1) buffer[j] = s[j];
else buffer[j] = switchdoor;
}
for(int j=mid+1; j<=r; j++){
if(s[j] != -1) buffer[j] = s[j];
else buffer[j] = abs(switchdoor - 1);
}
int firstclosed = tryCombination(buffer);
if(firstclosed > i || firstclosed == -1){
r = mid;
}else{
l = mid + 1;
}
}
door[i] = l;
s[l] = switchdoor;
}
int doorans[N], switchans[N];
for(int i=0; i<N; i++) doorans[door[i]] = i;
for(int i=0; i<N; i++) switchans[i] = s[i];
answer(switchans, doorans);
return;
}
