#include <iostream>
#include "cave.h"
int n;
int const NMAX = 5000;
int query[1 + NMAX];
bool fixed[1 + NMAX];
int sol[2][1 + NMAX];
void printQuery() {
for(int i = 0;i < n;i++) {
std::cerr << query[i] << ' ';
}
std::cerr << '\n';
}
void buildQuery(int val1, int val2, int mid) {
int ind = 0;
for(int i = 0;i < n;i++) {
if(!fixed[i]) {
ind++;
if(ind <= mid) {
query[i] = val1;
}else {
query[i] = val2;
}
}
}
}
int getPos(int mid) {
int ind = 0;
for(int i = 0;i < n;i++) {
if(!fixed[i]) {
ind++;
if(ind == mid) {
return i;
}
}
}
return -1;
}
int cautbin(int from, int to, int val1, int val2, int target) {
//std::cerr << from << ' ' << to << " :\n";
if(from >= to) {
return from;
}else {
int mid = (from + to) / 2;
buildQuery(val1, val2, mid);
int temp = tryCombination(query);
//printQuery();
//std::cerr << " " << target << ' ' << mid << ' ' << temp << '\n';
if(temp == -1 || temp > target) {
return cautbin(from, mid, val1, val2, target);
}else {
return cautbin(mid+1, to, val1, val2, target);
}
}
}
void solve() {
for(int i = 0;i < n;i++) {
int temp, val1 = 1, val2 = 0;
buildQuery(0, 0, 0);
//printQuery();
temp = tryCombination(query);
//std::cerr << temp << '\n';
if(temp == -1 || temp > i) {
val1 = 0;
val2 = 1;
}
//std::cerr << i << ":\n";
int pos = getPos(cautbin(1, n-i, val1, val2, i));
//std::cerr << pos << "\n\n";
query[pos] = val1;
fixed[pos] = true;
sol[0][pos] = val1;
sol[1][pos] = i;
}
}
void exploreCave(int N) {
n = N;
solve();
answer(sol[0], sol[1]);
}
