#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];
void convert(int i, int j)
{
for(int g = i ; g <= j ; g++)
if(!correct[g])
test[g] = 1 - test[g];
}
int bs(int cur, int k)
{
int i = 0, j = n - 1;
for(int g = 0 ; g < n ; g++)
test[g] = (correct[g]) ? combination[g] : k;
while(i < j)
{
int m = (i + j)/2;
convert(m + 1 , j);
if(tryCombination(test) != cur) convert(m + 1 , j), j = m;
else convert(i , j), i = m + 1;
}
return i;
}
void exploreCave(int N)
{
n = N;
for(int g = 0 ; g < n ; g++)
{
int i = tryCombination(combination);
int cur = (i == g) ? 1 : 0;
int id = bs(g , cur);
correct[id] = true;
switch_door[id] = g;
combination[id] = cur;
switch_state[id] = cur;
}
answer(switch_state , switch_door);
}
