#include <bits/stdc++.h>
#include "cave.h"
#define MAX 5010
using namespace std;
int n;
int test[MAX];
int combination[MAX];
int switch_door[MAX];
int switch_state[MAX];
bool correct[MAX];
/*int tryCombination(int s[])
{
for(int g = 0 ; g < n ; g++) printf("%d ",s[g]);
printf("\n");
int a;
scanf("%d",&a);
return a;
}*/
int bs(int cur, int k)
{
int i = 0, j = n - 1;
//todos começam com 1 - k, tirando os corretos
for(int g = 0 ; g < n ; g++)
test[g] = (correct[g]) ? combination[g] : k;
while(i < j)
{
int m = (i + j)/2;
//if(i == j - 1) m = j;
//printf("i = %d j = %d m = %d\n",i,j,m);
for(int g = m + 1 ; g <= j ; g++)
if(!correct[g])
test[g] = 1 - test[g];
if(tryCombination(test) != cur)
{
for(int g = m + 1 ; g <= j ; g++)
if(!correct[g])
test[g] = 1 - test[g];
j = m;
}
else
{
for(int g = i ; g <= j ; g++)
if(!correct[g])
test[g] = 1 - test[g];
i = m + 1;
}
//for(int g = 0 ; g < n ; g++) printf("%d ",test[g]);
//printf("\n");
}
return i;
}
void exploreCave(int N)
{
n = N;
for(int g = 0 ; g < n ; g++)
{
int i = tryCombination(combination);//tudo com 0, menos os corretos
int cur = (i == g) ? 1 : 0;
int id = bs(g , cur);
//printf("g = %d bs = %d\n",g,id);
correct[id] = true;
switch_door[id] = g;
combination[id] = cur;
switch_state[id] = cur;
}
answer(switch_state , switch_door);
//for(int g = 0 ; g < n ; g++)
//printf("%d %d\n",switch_door[g],switch_state[g]);
}
/*int main()
{
scanf("%d",&n);
exploreCave(n);
}*/
