#include <bits/stdc++.h>
#include "cave.h"
#define MAXN 50005
#define lp(i,a,b) for(int i = a ; i < b ; i++)
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
int N ;
int A[MAXN] , B[MAXN] , s[MAXN];
int resp1[MAXN] , resp2[MAXN] ;
pii ans[MAXN] ;
// int tryCombination(int S[])
// {
// pii v[MAXN] , novo[MAXN];
// lp(i,0,N) v[i] = pii ( ans[i].ff , S[i] ) ;
// lp(i,0,N) novo[i] = ans[i] ;
// sort(v,v+N) ;
// sort(novo, novo+N) ;
// lp(i,0,N)
// if( novo[i].ss != v[i].ss ) return v[i].ff ;
// return -1 ;
// }
int findDoor( int door )
{
if( B[door] != -1 ) return B[door] ;
memset(s , 0 , sizeof s) ;
lp(i,0,N)
if( A[i] != -1 ) s[ A[i] ] = B[i] ;
int k = tryCombination(s) ;
if(k == -1) k = door + 1 ;
if( k > door ) return B[door] = 0 ;
else return B[door] = 1 ;
}
int findSwitch( int door )
{
int u = 0 , l = N-1 , mid ;
int x = findDoor(door) ;
while( u <= l )
{
mid = (u+l)/2 ;
memset(s , -1 , sizeof s) ;
lp(i,0,N)
if(A[i] != -1) s[ A[i] ] = B[ i ] ;
lp(i,u,mid+1)
if(s[i] == -1 ) s[i] = x ;
lp(i,mid+1 , l+1)
if( s[i] == -1 ) s[i] = !x ;
int k = tryCombination(s) ;
if( k == -1 ) k = door + 1 ;
if(k > door) l = mid - 1 ;
else u = mid + 1 ;
}
return l + 1 ;
}
void exploreCave( int n )
{
//
N = n ;
memset(A, -1 , sizeof A) ;
memset(B, -1, sizeof B) ;
//
lp(i,0,N)
{
B[i] = findDoor(i) ;
A[i] = findSwitch(i) ;
}
pii p[MAXN] ;
lp(i,0,N) p[i] = pii( A[i] , i ) ;
sort(p,p+N) ;
lp(i,0,N) resp1[i] = p[i].ss ;
lp(i,0,N) resp2[i] = B[ p[i].ss ] ;
lp(i,0,N) printf("%d " , resp1[i]) ;
lp(i,0,N) printf("%d " , resp2[i]) ;
answer(resp1, resp2) ;
}
// int main()
// {
// int n;
// scanf("%d", &n) ;
// lp(i,0,n) scanf("%d" , &ans[i].ss) ;
// lp(i,0,n) scanf("%d", &ans[i].ff);
// exploreCave(n) ;
// }
