/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
typedef long long ll;
int tryCombination (int state[]);
void answer (int correct[], int door[]);
void exploreCave (int n)
{
int correct[n];
int door[n];
int lever[n];
for(int i = 0; i < n; i++)
{
door[i] = -1;
lever[i] = -1;
correct[i] = -1;
}
for(int target = 0; target < n; target++)
{
int result;
{
int query[n];
for(int i = 0; i < n; i++)
{
if(door[i] != -1)
query[i] = correct[i];
else
query[i] = 0;
}
int response = tryCombination(query);
if(response == target)
result = 1;
else
result = 0;
}
int l = 0, r = n - 1;
while(l < r)
{
int mid = (l + r) / 2;
int query[n];
for(int i = 0; i < n; i++)
{
if(door[i] != -1)
query[i] = correct[i];
else if(l <= i && i <= mid)
query[i] = result;
else
query[i] = !result;
}
int response = tryCombination(query);
if(response == target)
l = mid + 1;
else
r = mid;
}
assert(l == r);
lever[target] = l;
door[lever[target]] = target;
correct[lever[target]] = result;
}
answer(correct, door);
}
