#include<bits/stdc++.h>
#include "cave.h"
#define endl '\n'
using namespace std;
const int MAXN = 2005;
int n, taken[MAXN], correct[MAXN], connected_to[MAXN];
int curr_try[MAXN];
void help_try_01(int mid)
{
for (int i = 0; i < mid; ++ i)
curr_try[i] = 0;
for (int i = mid+1; i < n; ++ i)
curr_try[i] = 1;
for (int i = 0; i < n; ++ i)
{
if(taken[i])curr_try[i] = correct[i];
}
}
void help_try_10(int mid)
{
for (int i = 0; i < mid; ++ i)
curr_try[i] = 1;
for (int i = mid+1; i < n; ++ i)
curr_try[i] = 0;
for (int i = 0; i < n; ++ i)
{
if(taken[i])curr_try[i] = correct[i];
}
}
void exploreCave(int N)
{
n = N;
for (int door = 0; door < n; ++ door)
{
if(tryCombination(correct) > door)
{
int l = 0, r = n-1, mid, ans = -1;
while(l <= r)
{
mid = (l + r)/2;
help_try_01(mid);
if(tryCombination(curr_try) > door)
{
ans = mid;
l = mid - 1;
}
else r = mid + 1;
}
taken[ans] = 1;
correct[ans] = 1;
connected_to[ans] = door;
}
else
{
int l = 0, r = n-1, mid, ans = -1;
while(l <= r)
{
mid = (l + r)/2;
help_try_10(mid);
if(tryCombination(curr_try) > door)
{
ans = mid;
l = mid - 1;
}
else r = mid + 1;
}
taken[ans] = 1;
correct[ans] = 0;
connected_to[ans] = door;
}
}
answer(correct, connected_to);
}
