#include "cave.h"
#include <stdio.h>
#include <vector>
using namespace std;
#define pb push_back
const int N=5005;
int id[N],ty[N];
int mask[N],n,good[N],k[N];
bool done[N];
/*int lid[N],tid[N];
int ok[N];
int tryCombination(int a[])
{
int i;
for(i=0;i<n;i++) ok[lid[i]]=a[i]==tid[i];
for(i=0;i<n;i++) if(!ok[i]) return i;
return -1;
}
void answer(int a[], int id[])
{
int i;
for(i=0;i<n;i++) printf("%i ",a[i]);printf("\n");
for(i=0;i<n;i++) printf("%i ",id[i]);printf("\n");
}*/
int get(int a[]){ int x=tryCombination(a);if(x==-1) return n;return x;}
void exploreCave(int N)
{
n=N;
int x=get(mask),y;
int i,j;
for(i=0;i<n;i++)
{
mask[i]=1;
y=get(mask);
if(y<x)
{
id[i]=y,ty[i]=0,done[i]=1,good[i]=0;
//printf("1:%i:%i %i\n",i,ty[i],id[i]);
}
mask[i]=0;
}
vector<int> pos,tmp[2];
bool ok=1;
for(i=x;i<n;i++)
{
pos.clear();
for(j=0;j<n;j++) if(!done[j]) pos.pb(j);
while(pos.size()>1)
{
tmp[0].clear();tmp[1].clear();
for(j=0;j<pos.size();j++) tmp[j&1].pb(pos[j]);
for(j=0;j<tmp[0].size();j++) good[tmp[0][j]]^=1;
y=get(good);
if(ok)
{
if(y>i) pos=tmp[0];
else pos=tmp[1];
}
else
{
if(y>i) pos=tmp[1];
else pos=tmp[0];
}
for(j=0;j<tmp[0].size();j++) good[tmp[0][j]]^=1;
}
id[pos[0]]=i;
ty[pos[0]]=good[pos[0]]=ok;
y=get(good);
done[pos[0]]=1;
if(y>i+1) ok=0;
else ok=1;
//printf("2:%i:%i %i\n",pos[0],ty[pos[0]],id[pos[0]]);
}
answer(ty,id);
}
/*int main()
{
int n,i;
scanf("%i",&n);
for(i=0;i<n;i++) scanf("%i",&tid[i]);
for(i=0;i<n;i++) scanf("%i",&lid[i]);
exploreCave(n);
return 0;
}*/
