#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vc vector
typedef vc<ll> vcll;
#define pr pair
typedef pr<ll, ll> prll;
#define f0r(i,a,n) for (i=a; i<n; i++)
#define f1r(i,a,n) for (i=a; i<=n; i++)
#define r0f(i,n,a) for (i=n; i>a; i--)
#define r1f(i,n,a) for (i=n; i>=a; i--)
#define pb push_back
#define mp make_pair
#define INF (LLONG_MAX>>4ll)
#define mxN 5010ll
ll n;
int bar[mxN];
int gar[mxN];
int perm[mxN];
ll cnt=0;
/*
inline int tryCombination(int *ar)
{
cnt++;
return rand() % n;
}
*/
void exploreCave(int N)
{
n=N;
ll i2;
f0r(i2,0,n)
{
bar[i2]=0;
perm[i2]=-1;
gar[i2]=-1;
}
ll cnt2=0;
f0r(i2,0,n)
{
ll i3;
f0r(i3, 0, n) if (gar[i3]==-1) bar[i3]=0;
ll i;
i = tryCombination(bar);
// cnt2++;
/*
printf("try combination(");
f0r(i3,0,n) printf("%lli ", (ll)bar[i3]);
printf("): ");
scanf("%lli", &i);
*/
if (i==-1) break;
ll j;
ll l=0, r=n-1; // both incl.
bool broke=0;
ll cnt=0;
while (l<r)
{
ll m;
m = ((l+1>=r) ? l : (l+r)/2);
// printf("l: %lli, m: %lli, r: %lli\n", l, m, r);
f1r(i3, l, m) if (gar[i3]==-1) bar[i3]^=1;
j = tryCombination(bar);
// cnt2++;
/*
printf("try combination(");
f0r(i3,0,n) printf("%lli ", (ll)bar[i3]);
printf("): ");
scanf("%lli", &j);
*/
if (j==-1)
{
broke=1;
break;
}
if (j<i)
{
i=j;
r=m;
}
else if (j==i)
{
l=m+1;
}
else
{
f1r(i3, l, m) if (gar[i3]==-1) bar[i3]^=1;
r=m;
}
}
if (broke) break;
/*
printf("try combination(");
f0r(i3,0,n) printf("%lli ", (ll)bar[i3]);
printf("): ");
scanf("%lli", &j);
*/
// if (i==j) bar[l]^=1;
bar[l]^=1;
gar[l]=bar[l];
perm[l]=i;
cnt++;
}
/*
if (cnt==n-1)
{
ll i;
for (i=0; i<n && perm[i]!=-1; i++) ;
vc<bool> has(mxN, 0);
ll i13;
f0r(i13,0,n) if (i13!=i) has[perm[i13]]=1;
ll v;
for (v=0; v<n && has[v]; v++) ;
gar[i]=bar[i];
perm[i]=v;
return void(answer(bar, perm));
}
*/
f0r(i2,0,n)
{
gar[i2]=bar[i2];
if (perm[i2]==-1)
{
ll i;
bar[i2]^=1;
// printf("real\n");
i = tryCombination(bar);
/*
printf("try combination(");
ll i3;
f0r(i3,0,n) printf("%lli ", (ll)bar[i3]);
printf("): ");
scanf("%lli", &i);
*/
bar[i2]^=1;
perm[i2]=i;
}
}
/*
ll i;
printf("gar: ");
f0r(i,0,n) printf("%lli ", (ll)gar[i]);
printf("perm: ");
f0r(i,0,n) printf("%lli ", (ll)perm[i]);
*/
answer(gar, perm);
// printf("cnt: %lli\n", cnt);
}
/*
int main()
{
srand(time(0));
ll N;
printf("n: ");
scanf("%lli", &N);
printf("\n");
exploreCave(N);
return 0;
}
*/
