#include<bits/stdc++.h>
#include "cave.h"
using namespace std;
void exploreCave(int N) {
int s[N], d[N];
for (int i = 0; i < N; ++i) d[i]=-1;
for (int i = 0; i < N; ++i) {
int cor;
vector<int> p;
for (int j = 0; j < N; ++j) if (d[j]==-1) p.push_back(j);
for (int j = 0; j < N-i; ++j) s[p[j]]=0;
if (tryCombination(s)==i) cor=1;
else cor=0;
for (int j = 0; j < N-i; ++j) s[p[j]]=1-cor;
int l=0, r=N-i-1;
while (l<r) {
int mid=(l+r)/2;
for (int i = l; i <= mid; ++i) s[i]=cor;
int res=tryCombination(s);
for (int i = l; i <= mid; ++i) s[i]=1-cor;
if (res==i) l=mid+1;
else r=mid;
} d[r]=i; s[r]=cor;
} answer(s, d);
}
