#include "cave.h"
#include <bits/stdc++.h>
int n;
using namespace std;
void exploreCave(int N) {
/* ... */
n = N;
int okidac[n];
int gde[n]; //okidac na itom mestu pokazuje na vrata gde[i]
bool marked[n];
for(int i = 0; i < n; ++i) {
marked[i] = false;
gde[i] = 3*n;
}
for(int iter = 0; iter < n; ++iter) {
int trenutni[n];
for(int i = 0; i < n; ++i) {
trenutni[i] = 0;
}
for(int i = 0; i < n; ++i) {
if(gde[i] < iter) {
trenutni[i] = okidac[i];
}
}
int odg = tryCombination(trenutni);
int x;
if(odg == -1 || odg > iter) {
x = 0;
} else {
x = 1;
}
int l = 1, r = n - iter;
int zapravoGde = -1;
int ans = -1;
while(l <= r) {
int mid = (l + r) / 2;
for(int i = 0; i < n; ++i) {
trenutni[i] = x ^ 1;
}
for(int i = 0; i < n; ++i) {
if(gde[i] < iter) {
trenutni[i] = okidac[i];
}
}
int uzeli = 0;
for(int i = 0; i < n; ++i) {
if(marked[i]) continue;
++uzeli;
trenutni[i] = x;
if(uzeli == mid) {
zapravoGde = i;
break;
}
}
// if(l == r) break;
odg = tryCombination(trenutni);
// cerr << l << " " << r << " ";
// cerr << "(" << iter << ", " << mid << "):";
// for(int i = 0; i < n; ++i) cerr << " " << trenutni[i];
// cerr << " -> " << odg << endl;
if(odg == -1 || odg > iter) {
ans = zapravoGde;
r = mid - 1;
} else {
l = mid + 1;
}
}
gde[ans] = iter;
okidac[ans] = x;
marked[ans] = true;
}
answer(okidac, gde);
}
