#include <bits/stdc++.h>
using namespace std;
#ifndef ARTHUR_LOCAL
#include "cave.h"
#endif
#ifdef ARTHUR_LOCAL
int tryCombination(int an_S[])
{
cout << "TRYING: ";
for(int i=0; i<4; i++) cout << an_S[i] << " ";
cout << endl;
int ans=-1;
if(an_S[0]!=1) ans=3;
if(an_S[3]!=0) ans=2;
if(an_S[1]!=1) ans=1;
if(an_S[2]!=1) ans=0;
cout << ans << endl;
return ans;
}
#endif
void exploreCave(int n)
{
int D[n];
int S[n];
for(int i=0; i<n; i++)
{
S[i]=0;
D[i]=0;
}
if(n==1)
{
if(tryCombination(S)==-1) answer(S,D);
S[0]=1;
answer(S,D);
}
vector<int> lock(n);
for(int i=0; i<n; i++)
{
int l=0;
int r=n-1; // door i is controlled by a switch in the range between l and r
int now=-1;
int cur=-1;
bool first_go=1;
while(l<r)
{
// cout << l << " " << r << endl;
if(first_go)
{
cur = tryCombination(S);
first_go=0;
}
else cur = now;
int mid = int((l+r)/2);
for(int j=l; j<=mid; j++)
{
if(!lock[j]) S[j]=1-S[j];
}
now = tryCombination(S);
if(cur==now || (cur!=i && now!=i))
{
// cout << cur <<" " << now << " " << i << " " << mid << endl;
l = mid+1;
}
else
{
r=mid;
}
}
if(now == i) S[l]=1-S[l];
lock[l]=1;
D[l]=i;
}
answer(S,D);
}
