#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXS = 5001;
int sw[MAXS], opens[MAXS], definedcomb[MAXS];
void funfun(int l, int r, int color, int currdoor)
{
// base case:
if (l==r){
definedcomb[r]=color;
opens[r]=currdoor;
return;
}
// general case:
int mid=(l+r)/2;
for (int i=l; i<=mid; i++)
if (definedcomb[i]==-1)
sw[i]=color;
int complement=color ^ 1;
for (int i=mid+1; i<=r; i++)
if (definedcomb[i]==-1)
sw[i]=complement;
int temp=tryCombination(sw);
if (temp!=currdoor){
funfun(l, mid, color, currdoor);
}else{
for(int i=l; i<=mid; i++)
if (definedcomb[i]==-1)
sw[i]=complement;
for (int i=mid+1; i<=r; i++)
if (definedcomb[i]==-1)
sw[i]=color;
funfun(mid+1, r, color, currdoor);
}
}
void exploreCave(int N)
{
memset(opens, -1, sizeof opens);
memset(definedcomb, -1, sizeof definedcomb);
int n=N;
for (int i=0; i<n; i++){ //find out the switch of the ith door
memset(sw, 0, sizeof sw);
for (int j=0; j<n; j++)
if (definedcomb[j]!=-1)
sw[j]=definedcomb[j];
int temp=tryCombination(sw);
if (temp!=i){
//ok this opens the door
funfun(0, n-1, 0, i);
}else{
for (int j=0; j<n; j++){
if (definedcomb[j]==-1) sw[j]=1;
else sw[j]=definedcomb[j];
}
funfun(0, n-1, 1, i);
}
}
answer(definedcomb, opens);
}
