#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int ans[5001], door[5001], send[5001], n;
void find(int l, int r, int id, int in){
if(l == r){
ans[l] = in;
door[id] = l;
return;
}
int m = (l + r) >> 1;
memset(send, -1, sizeof(send));
for(int i = l; i <= m; i++){
send[i] = 1;
}
for(int i = 0; i < m; i++){
if(ans[i] != -1){
send[i] = ans[i];
} else if(send[i] == -1){
send[i] = 0;
}
}
int k = tryCombination(send);
if(k == -1 || k > id){
k = 1;
} else {
k = 0;
}
if((in ^ k )== 1){
find(l, m, id, k);
} else {
find(m + 1, r, id, k ^ 1);
}
}
void exploreCave(int N) {
n = N;
memset(ans, -1, sizeof(ans));
memset(door, -1, sizeof(door));
int k;
for(int j = 0; j < n; j++){
memset(send, -1, sizeof(send));
for(int i = 0; i < n; i++){
send[i] = max(send[i], ans[i]);
}
for(int i = 0; i < n; i++){
if(send[i] == -1){
send[i] = 1;
}
}
k = tryCombination(send);
if(k == -1 || k > j){
k = 1;
} else {
k = 0;
}
find(0, n - 1, j, k);
}
answer(ans, door);
}
