#include "cave.h"
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int) (x).size())
using namespace std;
void answer(int S[], int D[]);
int tryCombination(int S[]);
void recur(int l, int r, int res, vector<int>&v, int S[], int D[]){
if(l == r){
if(res == -1){
S[v[l]] ^= 1;
D[v[l]] = tryCombination(S);
S[v[l]] ^= 1;
} else{
D[v[l]] = res;
S[v[l]] ^= 1;
}
v.erase(find(v.begin(), v.end(), v[l]));
return;
}
int m = (l + r) / 2;
for(int i = l; i <= m; i++){
S[v[i]] ^= 1;
}
int res2 = tryCombination(S);
for(int i = l; i <= m; i++){
S[v[i]] ^= 1;
}
if(res == res2){
recur(m+1, r, res, v, S, D);
return;
}
if(res2 == -1 || res2 > res){
recur(l, m, res, v, S, D);
return;
}
if(res2 < res){
for(int i = l; i <= m; i++){
S[v[i]] ^= 1;
}
recur(l, m, res2, v, S, D);
return;
}
}
void exploreCave(int N){
int S[N], D[N];
memset(S, 0, sizeof(S));
memset(D, -1, sizeof(D));
vector<int> v(N);
iota(v.begin(), v.end(), 0);
while(SZ(v)){
recur(0, SZ(v) - 1, tryCombination(S), v, S, D);
}
answer(S, D);
}
