#include "cave.h"
void exploreCave(int n)
{
int position[n];
for(int i = 0; i < n; i++) position[i] = -1;
int guess[n];
int ans[n];
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++) guess[j] = position[j] == -1 ? 1 : position[j];
int x = tryCombination(guess);
if(x == -1) x = n;
position[i] = x > i;
int l = 0, r = n - 1;
while(l != r)
{
int mid = (l + r) / 2;
for(int j = 0; j < l; j++) guess[j] = position[j] == -1 ? 1 - position[i] : position[j];
for(int j = l; j <= mid; j++) guess[j] = position[j] == -1 ? position[i] : position[j];
for(int j = mid + 1; j < n; j++) guess[j] = position[j] == -1 ? 1 - position[i] : position[j];
int x = tryCombination(guess);
if(x == -1) x = n;
if(x > i) r = mid;
else l = mid + 1;
}
ans[l] = i;
}
answer(position, ans);
}
