#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
int a[N], ans[N];
for(int i = 0; i < N; i++) a[i] = 0, ans[i] = -1;
int cur = tryCombination(a);
for(int i = 0; i < N - 1; i++){
// cout << "cur = " << cur << endl;
int l = 0, r = N - 1;
while(l < r){
int mid = (l + r) / 2;
for(int j = l; j <= mid; j++){
if(ans[j] != -1) continue;
a[j] = 1;
}
int judges = tryCombination(a);
// cout << i << " " << l << " " << r << " " << judges << endl;
for(int j = l; j <= mid; j++){
if(ans[j] != -1) continue;
a[j] = 0;
}
if(cur != i){
if(judges != i){
l = mid + 1;
} else {
r = mid;
}
} else {
if(judges == i){
l = mid + 1;
} else {
r = mid;
}
}
}
ans[l] = i;
if(cur == i) a[l] = 1;
cur = tryCombination(a);
}
for(int i = 0; i < N; i++){
if(ans[i] == -1){
ans[i] = N - 1;
a[i] = 1;
if(tryCombination(a) == N - 1) a[i] = 0;
}
}
answer(a, ans);
}
