#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
int n;
void applyChanges(int combo[], int l, int r, int setInterrup, int preRequisites[]){
for(int i = l; i <= r; ++i) combo[i] = setInterrup;
for(int i = 0; i < n;++i){
if(preRequisites[i] != -1) combo[i] = preRequisites[i];
}
}
void exploreCave(int N) {
/* ... */
//answer(switches, correspondence)
n = N;
int setInterruptors[N];
memset (setInterruptors, -1, sizeof(setInterruptors));
int yourInterruptor[N];
for(int door = 0; door < N; ++door){
int lo = 0; int hi = N-1;
int InterruptVal;
int combo[N];
memset (combo, 0, sizeof(combo));
applyChanges(combo, 0, 0, 0, setInterruptors);
int ans = tryCombination(combo);
InterruptVal = 0;
if(ans == -1 or ans > door) InterruptVal = 0;
else InterruptVal = 1;
int pos = 0;
while(lo <= hi){
int mid = lo + (hi - lo)/2;
memset(combo, InterruptVal^1, sizeof(combo));
applyChanges(combo, lo, mid, InterruptVal, setInterruptors);
ans = tryCombination(combo);
if(ans == -1 or ans > door){
hi = mid-1;
pos = mid;
}
else lo = mid+1;
}
yourInterruptor[door] = pos;
setInterruptors[pos] = InterruptVal;
}
int interruptToDoor[N];
for(int i = 0; i < N; ++i){
interruptToDoor[yourInterruptor[i]] = i;
}
answer(setInterruptors, interruptToDoor);
}
