#include "cave.h"
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
void exploreCave(int n)
{
vector<bool> found(n);
vector<bool> value(n);
vector<int> chamber(n);
int *guess = new int[n];
for (int k = 0; k < n; ++k)
{
for (int i = 0; i < n; ++i)
{
if (found[i]) guess[i] = value[i];
else guess[i] = 0;
}
int this_value = tryCombination(guess) != k;
for (int i = 0; i < n; ++i)
{
if (!found[i]) guess[i] = 1 - this_value;
}
int left = 0;
int right = n - 1;
int mid;
while (left < right)
{
mid = (left + right) / 2;
for (int i = left; i <= mid; ++i)
{
if (!found[i]) guess[i] = this_value;
}
int ans = tryCombination(guess);
for (int i = left; i <= mid; ++i)
{
if (!found[i]) guess[i] = 1 - this_value;
}
if (ans == k) left = mid + 1;
else right = mid;
}
value[left] = this_value;
chamber[left] = k;
}
int *S = new int[n];
int *D = new int[n];
for (int i = 0; i < n; ++i) S[i] = value[i];
for (int i = 0; i < n; ++i) D[i] = chamber[i];
answer(S, D);
}
