#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> sol(vector<int> &A, int s, int e,int tar){
if(s>=e) return A;
int mid = (s+e)/2;
vector<int> C = A;
int n = A.size();
int B[n];
for(int i=0;i<n;++i){
B[i] = A[i];
}
for(int i=mid;i<=e;++i){
B[i] = (B[i]+1)%2;
A[i] = B[i];
}
int res = tryCombination(B);
if(res == -1 || (res > tar && tar != -1)){
return A;
}else if(res > tar){
return sol(A,0,n-1,-1);
}else{
vector<int> D = sol(C,mid,e,tar);
vector<int> E = sol(C,s,mid-1,tar);
for(int i=0;i<n;++i){
B[i] = D[i];
}
res = tryCombination(B);
if(res == -1) return D;
for(int i=0;i<n;++i){
B[i] = E[i];
}
res = tryCombination(B);
if(res == -1) return E;
if(res<=tar) return D;
else return E;
}
}
void exploreCave(int N) {
vector<int> A(N,0);
A = sol(A,0,N-1,-1);
int B[N];
for(int i=0;i<N;++i) B[i] = A[i];
int door[N];
for(int i=0;i<N;++i){
B[i] = (B[i]+1)%2;
door[i] = tryCombination(B);
B[i] = (B[i]+1)%2;
}
answer(B,door);
}
