#include <bits/stdc++.h>
#include "cave.h"
#define maxn 5000
#define pb push_back
using namespace std;
// tryCombination(a[])
// answer(a[],b[])
int n;
bool isOpen(int val , int id) {
return val == -1 || val > id;
}
void exploreCave(int N) {
n = N;
int turn[n];
int doors[n];
memset(turn,-1,sizeof(turn));
memset(doors,-1,sizeof(doors));
int curr[n];
for( int i = 0 ; i < n ; i++ )
curr[i] = 0;
int leftmost = tryCombination(curr);
bool openNow = isOpen(leftmost,0);
bool openBefore = openNow;
for( int door = 0 ; door < n ; door++ ) {
vector<int> ids;
for( int i = 0 ; i < n ; i++ )
if(doors[i] == -1)
ids.pb(i);
else
curr[i] = turn[i];
int l = 0 , r = n-door;
while(l < r) {
int m = (l+r)>>1;
for( int i = l ; i <= m ; i++ )
curr[ids[i]] ^= 1;
leftmost = tryCombination(curr);
openNow = isOpen(leftmost,door);
if(openBefore == openNow)
l = m+1;
else
r = m;
openBefore = openNow;
}
doors[l] = door;
if(openNow)
turn[l] = curr[l];
else {
turn[l] = !curr[l];
curr[l] = !curr[l];
openNow = tryCombination(curr);
openBefore = openNow;
}
}
answer(turn,doors);
}
