#include "cave.h"
#define magic_sauce inline __attribute__((always_inline))
const int MAXN = 5000;
const int UNDEF = -1;
const int INF = 1e9;
int out[MAXN];
int set[MAXN];
int q[MAXN];
int p[MAXN];
int query( int n, int q[] ){
for( int i = 0 ; i < n ; i++ )
out[i] = set[i] < 0 ? q[i] : set[i];
int ret = tryCombination( out );
return ret < 0 ? +INF : ret;
}
void exploreCave( int N ){
int i, j, val;
int st, dr, mij;
for( i = 0 ; i < N ; i++ )
set[i] = UNDEF;
for( i = 0 ; i < N ; i++ ){
for( j = 0 ; j < N ; j++ )
q[j] = 0;
val = (query( N, q ) == i);
st = 0;
dr = N;
while( dr - st > 1 ){
mij = (dr + st) >> 1;
for( j = 0 ; j < mij ; j++ )
q[j] = val;
for( ; j < N ; j++ )
q[j] = (val ^ 1);
if( query( N, q ) == i )
st = mij;
else
dr = mij;
}
p[st] = i; // the st-th switch toggles the i-th door
set[st] = val;
}
answer( set, p );
}
