#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int door[5005];
int color[5005];
bool ima[5005];
int query[5005];
vector <int> vec;
int n;
void dc(int which, int l, int r, int col){
if(l == r){
door[vec[l]] = which;
color[vec[l]] = col;
ima[vec[l]] = 1;
vec.erase(vec.begin()+l);
return;
}
int mid = (l+r)/2;
for(int i=0; i<n; i++) query[i] = 1 - col;
for(int i=l; i<=mid; i++){
query[vec[i]] = col;
}
for(int i=0; i<n; i++) if(ima[i]) query[i] = color[i];
int g = tryCombination(query);
if(g == -1 || g > which){
dc(which, l, mid, col);
}
else dc(which, mid+1, r, col);
}
void exploreCave(int N) {
n = N;
for(int i=0; i<N; i++) vec.push_back(i);
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
query[j] = 0;
if(ima[j]) query[j] = color[j];
}
int g = tryCombination(query);
if(g == -1 || g > i) dc(i, 0, N-i, 0);
else dc(i, 0, N-i, 1);
}
answer(color, door);
}
