#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
int *inp,*ans;
int chk(vector<int> a){
for(int x: a){
inp[x] ^= 1;
}
int res = tryCombination(inp);
for(int x: a){
inp[x] ^= 1;
}
return res;
}
void exploreCave(int n){
inp = new int[n];
ans = new int[n];
set<int> st;
for(int i = 0; i < n; i++){
inp[i] = 0;
st.insert(i);
}
for(int i = 0; i < n; i++){
if(chk({i}) == 0){
inp[i] ^= 1;
break;
}
}
int cur = 0;
while(1){
vector<int> b(st.begin(), st.end());
int lst = -1,lo = 0,hi = b.size() - 1;
while(lo <= hi){
int m = (lo + hi) / 2;
int res = chk(vector<int>(b.begin(),b.begin() + m + 1));
if(res > cur || res == -1){
hi = m - 1;
lst = m;
}else{
lo = m + 1;
}
}
assert(lst != -1);
int nxt = chk({b[lst]});
inp[b[lst]] ^= 1;
st.erase(b[lst]);
if(nxt == -1) break;
for(int i = 1; i <= nxt - cur - 1; i++){
vector<int> b(st.begin(), st.end());
lst = -1,lo = 0,hi = b.size() - 1;
while(lo <= hi){
int m = (lo + hi) / 2;
if(chk(vector<int>(b.begin(),b.begin() + m + 1)) == cur + i){
hi = m - 1;
lst = m;
}else{
lo = m + 1;
}
}
assert(lst != -1);
st.erase(b[lst]);
}
cur = nxt;
}
for(int i = 0; i < n; i++){
ans[i] = chk({i});
}
answer(inp,ans);
}
