#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
/* /\_/\
(= ._.)
/ > \>
*/
#define pb push_back
#define ins insert
#define sz(x) ((long long) (x).size())
#define dbg(x) cerr<<#x<<" "<<x<<endl
/*int saygex[] = {1,1,0,1,0,0,1,1},paygorn[] = {3,1,0,2,5,4,7,6},n = 8;
int tryCombination(int S[]) {
int ans = 1e9;
for(int i=0;i<n;i++) {
if(S[i] != saygex[i]) {
ans = min(ans,paygorn[i]);
}
}
return (ans == 1e9 ? -1 : ans);
}
void answer(int S[], int D[]) {
for(int i=0;i<n;i++) cout<<S[i]<<" ";
cout<<endl;
for(int i=0;i<n;i++) cout<<D[i]<<" ";
cout<<endl;
}*/
void exploreCave(int N) {
int S[N],D[N]; memset(S,0,sizeof(S)); int curr = tryCombination(S);
vector<int> idx; for(int i=0;i<N;i++) idx.pb(i);
while(idx.size()) {
int l = 0,r = sz(idx)-1,id = sz(idx);
while(l <= r) {
int m = (l + r)/2;
for(int i=0;i<=m;i++) S[idx[i]] = 1 - S[idx[i]];
int x = tryCombination(S);
if(x != curr) {
id = m;
r = m - 1;
}else {
l = m + 1;
}
for(int i=0;i<=m;i++) S[idx[i]] = 1 - S[idx[i]];
}
for(int i=0;i<=id;i++) S[idx[i]] = 1 - S[idx[i]];
int x = tryCombination(S);
if(x != -1 and x < curr) {
for(int i=0;i<=id;i++) S[idx[i]] = 1 - S[idx[i]];
D[idx[id]] = x;
} else {
D[idx[id]] = curr;
curr=(x == -1 ? N : x);
}
idx.erase(idx.begin()+id);
}
answer(S,D);
}
/*int main() {
exploreCave(8);
return 0;
}*/
