#include "cave.h"
#include "bits/stdc++.h"
using namespace std;
const int MAXN=5005;
int state[MAXN],lampu[MAXN],benar,it; //saklar ke i 0/1, door ke i saklarnya yang mana
bool sudah[MAXN];
vector<int> belom;
bool valid(){
int ret=tryCombination(state);
return ret>it || ret==-1;
}
void DNC(int ki,int ka){
if(ki==ka){
//lampu it saklarnya belom[ki]
lampu[belom[ki]]=it;
state[belom[ki]]=benar;
sudah[belom[ki]]=true;
return;
}
int mid=(ki+ka)/2;
for(int i=ki;i<=mid;i++)state[belom[i]]=1-benar;
if(valid()){
for(int i=ki;i<=mid;i++)state[belom[i]]=benar;
DNC(mid+1,ka);
}
else{
for(int i=ki;i<=mid;i++)state[belom[i]]=benar;
DNC(ki,mid);
}
}
void exploreCave(int N) {
for(it=0;it<N;it++){
//try door i
belom.clear();
for(int j=0;j<N;j++){
if(!sudah[j])belom.push_back(j);
}
for(auto isi : belom)state[isi]=0;
if(valid())benar=0;
else{
benar=1;
for(auto isi : belom)state[isi]=1;
}
DNC(0,belom.size()-1);
}
answer(state,lampu);
}
