#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
typedef int INT;
#define pb push_back
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define fst first
#define snd second
#define int long long
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
const int NMAX = 5000;
const ll INF = 1e15;
int N;
INT D[NMAX], S[NMAX];
int flip(int l, int r){
int j = 0, ret = 0;
FOR(i, 0, N) {
if(D[i] == -1) {
if(j == l) ret = i;
if(j >= l and j < r) S[i] = !S[i];
j++;
}
}
return ret;
}
int query(){
return tryCombination(S);
}
void exploreCave(INT n) {
/* ... */
N = n;
FOR(i, 0, N) D[i] = -1, S[i] = 0;
FOR(d, 0, N){
// try for door d;
// The unknown levers all start randomly, the others are in the correct position
if(query() == d) flip(0, N-d);
// pos is the index in D of the leftmost element of [l, r)
int l = 0, r = N-d;
while(l+1 != r){
int m = (l+r)/2;
flip(l, m);
if( query() == d ) r = m, flip(l, r);
else l = m;
}
//cout << l << endl;
int j = 0;
FOR(i, 0, N) if(D[i] == -1) {
if(j == l){ D[i] = d;}
j++;
}
}
answer(S, D);
}
