#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 5e3 + 5;
int N, S[NMAX], D[NMAX], fix[NMAX], x, y;
int s[4] = {1, 1, 1, 0};
int d[4] = {2, 1, 3, 0};
void exploreCave(int N){
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++) if(!fix[j]) S[j] = 0;
y = tryCombination(S);
if(y == -1 || y > i) x = 0;
else x = 1;
int l = 0, r = N - 1, m;
while(l < r){
m = (l + r + 1) / 2;
for(int i = l; i < m; i++) if(!fix[i]) S[i] = x;
for(int i = m; i <= r; i++) if(!fix[i]) S[i] = !x;
y = tryCombination(S);
if(y == -1 || y > i) r = m - 1;
else l = m;
}
S[l] = x; D[l] = i;
fix[l] = 1;
}
answer(S, D);
return;
}
/*
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N;
cin >> N;
exploreCave(N);
return 0;
}*/
