#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstdio>
#include "cave.h"
using namespace std;
#define ll long long
#define pii pair<int,int>
#define ff first
#define ss second
#define pb push_back
#define vi vector<int>
#define fr(i,ii,iii) for(int i=ii;i<iii;i++)
int tryCombination(int S[]);
void answer(int S[], int D[]);
void exploreCave(int N);
#define MAX_N 5000
#define MAX_CALLS 70000
#define fail(s, ...) do { \
fprintf(stderr, s "\n", ##__VA_ARGS__); \
exit(1); \
} while(0)
/* Symbol obfuscation */
#define N koala
#define realS kangaroo
#define realD possum
#define inv platypus
#define num_calls echidna
static int N;
static int realS[MAX_N];
static int realD[MAX_N];
static int inv[MAX_N];
static int num_calls;
//void answer(int S[], int D[]) {
// bool correct = true;
// for (int i = 0; i < N; ++i) {
// if (S[i] != realS[i] || D[i] != realD[i]) {
// correct = false;
// break;
// }
// }
//
// if (correct)
// cout << "CORRECT" << endl;
// else
// cout << "INCORRECT" << endl;
//
// for (int i = 0; i < N; ++i) {
// if (i > 0) cout << " ";
// cout << S[i];
// }
// cout << endl;
//
// for (int i = 0; i < N; ++i) {
// if (i > 0) cout << " ";
// cout << D[i];
// }
// cout << endl;
//
// exit(0);
//}
//
//int tryCombination(int S[]) {
// if (num_calls >= MAX_CALLS) {
// cout << "INCORRECT\nToo many calls to tryCombination()." << endl;
// exit(0);
// }
// ++num_calls;
//
// for (int i = 0; i < N; ++i) {
// if (S[inv[i]] != realS[inv[i]])
// return i;
// }
// return -1;
//}
//
//int init() {
// ifstream fin("cave.in");
// if (!fin)
// fail("Failed to open input file.");
//
// fin >> N;
//
// for (int i = 0; i < N; ++i)
// fin >> realS[i];
//
// for (int i = 0; i < N; ++i) {
// fin >> realD[i];
// inv[realD[i]] = i;
// }
//
// num_calls = 0;
// return N;
//}
void exploreCave(int N){
int s[N],d[N];
bool f[N];
fr(i,0,N){
s[i]=0;
d[i]=0;
f[i]=0;
}
fr(tt,0,N){
fr(i,0,N){
if(f[i]==0){
s[i]=0;
}
}
int x=tryCombination(s);
int ss;
if(x!=tt)ss=0;
else ss=1;
fr(i,0,N){
if(f[i]==0){
s[i]=1-ss;
}
}
int l=0,r=N-1,m,ind=0;
while(l<r){
m=(l+r)/2;
fr(i,l,m+1){
if(f[i]==0){
s[i]=ss;
}
}
x=tryCombination(s);
if(x!=tt){
ind=m;
r=m;
}
else{
ind=m+1;
l=m+1;
}
fr(i,l,m+1){
if(f[i]==0){
s[i]=1-ss;
}
}
}
//cout<<ind;
d[ind]=tt;
f[ind]=1;
s[ind]=ss;
}
answer(s,d);
}
//int main() {
// int N;
// N = init();
// exploreCave(N);
// //printf("INCORRECT\nYour solution did not call answer().\n");
// return 0;
//}
/*
l=0
r=2
m=1
*/
