#include "cave.h"
#include <algorithm>
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
#define MAX_N 5000
void exploreCave(int N) {
vector<int> a(N), b(N);
int q[MAX_N+1];
for(int i=0; i<N; i++){
for(int j=0; j<N; j++) q[j] = 1;
for(int j=0; j<i; j++) q[b[j]] = a[j];
int t = tryCombination(q);
if(t==i) a[i] = 1;
else a[i] = 0;
int s = 0, e = N-1, m;
while(s<e){
m = (s+e)/2;
for(int j=0; j<N; j++) q[j] = 1 - a[i];
for(int j = s; j<=m; j++) q[j] = a[i];
for(int j=0; j<i; j++) q[b[j]] = a[j];
if(tryCombination(q)==i) e = m;
else s = m+1;
}
b[i] = s;
a[i] = 1 - a[i];
}
int S[MAX_N+1], D[MAX_N+1];
for(int i=0; i<N; i++){
S[b[i]] = a[i];
D[b[i]] = i;
}
answer(S, D);
}
