#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
const int N = 5100;
bool found[N];
int connection[N];
bool foundswitch[N];
int final_combination[N];
int n;
int empty_x;
void solve(int i, bool state, int l=0, int r=n-1) {
if(l == r) {
// base case
connection[l] = i;
foundswitch[i] = true;
found[l] = true;
final_combination[l] = state;
//cout<<"Finishing door "<<i<<" with switch "<<l<<"\n";
}
else {
int combination[n];
for(int j=0;j<n;j++) {
if(found[j]) combination[j] = final_combination[j];
else combination[j] = false;
}
// fill up to mid with state
int mid = (l + r) / 2;
for(int j=l;j<=mid;j++) {
if(!found[j]) combination[j] = state;
}
for(int j=mid+1;j<=r;j++) {
if(!found[j]) combination[j] = !state;
}
int x1 = tryCombination(combination);
if(x1 == -1) x1 = n;
//cout<<i<<", "<<state<<" - "<<x1<<"\n";
if(x1 > i) solve(i, state, l, mid); //left
else solve(i, state,mid+1,r); //right
}
}
void exploreCave(int N) {
n = N;
int combination[N];
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
if(found[j]) {
combination[j] = final_combination[j];
}
else {
combination[j] = false;
}
}
empty_x = tryCombination(combination);
if(empty_x == -1) empty_x = n;
bool state;
if(empty_x > i) state = false;
else state = true;
//cout<<"Calling "<<i<<" with state: "<<state<<"\n";
solve(i, state);
}
/*for(int i=0;i<N;i++) {
cout<<final_combination[i]<<" "<<connection[i]<<"\n";
}*/
answer(final_combination, connection);
}
