#include "cave.h"
#include<stdio.h>
static int sw[5005];
static int de[5005];
void exploreCave(int N) {
int i, j;
int l, r, m;
int s[5005];
for(i=0; i<N;i++)
{
sw[i] = -1;
s[i] = 1;
de[i] = -1;
}
int result1;
int result2;
for(i=0; i<N; i++)
{
l=0;r=N-1;
for(j=0;j<N;j++)
{
if(sw[j]==-1)
s[j]=1;
else
s[j]=sw[j];
}
result1 = tryCombination(s);
if(result1 == i)
{
for(j=0;j<N;j++)
{
if(sw[j]==-1)
s[j]=0;
else
s[j]=sw[j];
}
}
while(l<r)
{
m=(l+r)/2;
for(j=l;j<=m;j++)
{
if(sw[j]==-1)
s[j]^=1;
else
s[j]=sw[j];
}
result2 = tryCombination(s);
// for(j=l;j<=r;j++)
// printf("%d",s[j]);
// printf("\n");
// printf("%d %d %d, %d %d\n",l,m,r, result1,result2);
if(result2!=i)
{
l=m+1;
}
else
{
for(j=l;j<=m;j++)
{
if(sw[j]==-1)
s[j]^=1;
else
s[j]=sw[j];
}
r=m;
}
}
// printf("%d\n",l);
// result1 = tryCombination(s);
// printf("%d ",result1);
sw[l] = s[l];
de[l] = i;
}
// printf("%d\n",tryCombination(sw));
answer(sw, de);
}
