//2013 IOI P4
#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int query(int N, int S[])
{
int x = tryCombination(S);
if (x==-1)
return N;
return x;
}
int flip_switches(int s[], int assignment[], int l, int r, int N)
{
vector<int> changes;
for (int i=l; i<=r; i++)
{
if (assignment[i] == -1)
{
changes.push_back(i);
s[i] = 1;
}
}
int ans = query(N, s);
for (int i: changes)
s[i] = 0;
return ans;
}
void exploreCave(int N)
{
int switches[N];
int assignment[N];
for (int i=0; i<N; i++)
{
switches[i] = 0;
assignment[i] = -1;
}
for (int door = 0; door<N; door++)
{
int lo = 0;
int hi = N-1;
int curr = query(N, switches);
while (lo!=hi)
{
int mid = (lo+hi)/2;
if (((flip_switches(switches, assignment, lo, mid, N)>door)+(curr>door))%2)
hi = mid;
else
lo = mid + 1;
}
if (curr > door)
switches[lo] = 0;
else
switches[lo] = 1;
assignment[lo] = door;
}
answer(switches, assignment);
}
