#include "messy.h"
#include <stdio.h>
#include <vector>
#include <string>
#include <map>
#include <stdlib.h>
#include <ctime>
#include <algorithm>
using namespace std;
#define pb push_back
const int N=250;
int per[N];
vector<string> all;
map<string,bool> was;
int add,chk,m;
/*void add_element(string s){ all.pb(s);add++;}
void compile_set()
{
int i,j;
for(i=0;i<all.size();i++)
{
string tmp;
for(j=0;j<m;j++) tmp+='0';
for(j=0;j<m;j++) tmp[j]=all[i][per[j]];
was[tmp]=1;
}
}
bool check_element(string s){ chk++;return was[s];}*/
int n;
void Set(int l, int r)
{
if(l==r) return;
int mid=l+r>>1,i,j;
string s;
for(i=1;i<=n;i++) s+='1';
for(i=l;i<=r;i++) s[i-1]='0';
for(i=l;i<=mid;i++) s[i-1]='1',add_element(s),s[i-1]='0';
Set(l,mid);Set(mid+1,r);
}
int sol[N];
void Solve(int l, int r, vector<int> v)
{
if(l==r){ sol[v[0]]=l;return;}
int mid=l+r>>1,i,j;
string s;
for(i=1;i<=n;i++) s+='1';
for(i=0;i<v.size();i++) s[v[i]-1]='0';
vector<int> ls,rs;
for(i=0;i<v.size();i++)
{
s[v[i]-1]='1';
if(check_element(s)) ls.pb(v[i]);
else rs.pb(v[i]);
s[v[i]-1]='0';
}
Solve(l,mid,ls);
Solve(mid+1,r,rs);
}
vector<int> restore_permutation(int N, int w, int r)
{
n=N;
Set(1,n);
compile_set();
vector<int> v;
int i;
for(i=1;i<=n;i++) v.pb(i);
Solve(1,n,v);
vector<int> ans;
for(i=1;i<=n;i++) ans.pb(sol[i]-1);
return ans;
}
void test()
{
int t,c=0,i,j;
scanf("%i",&t);
m=128;
int lo=-1;
int x=m;while(x) x>>=1,lo++;
for(i=0;i<m;i++) per[i]=i;
for(j=1;j<=t;j++)
{
random_shuffle(per,per+m);
add=0;chk=0;
was.clear();all.clear();
vector<int> sol=restore_permutation(m,896,896);
bool ok=1;
for(i=0;i<m;i++) if(per[i]!=sol[i]) ok=0;
if(!ok || add>m*lo || chk>m*lo)
{
printf("Test case %i:\n",j);
printf("%i\n",m);
for(i=0;i<m;i++) printf("%i ",per[i]);printf("\n");
printf("My solution:\n");
for(i=0;i<m;i++) printf("%i ",sol[i]);printf("\n");
printf("Add: %i, Chk: %i\n",add,chk);
}
else c++;
}
printf("Add: %i, Chk: %i\n",add,chk);
printf("%i of %i is correct!\n",c,t);
}
/*int main()
{
srand(time(0));
test();
return 0;
int i;
scanf("%i",&m);
for(i=0;i<m;i++) scanf("%i",&per[i]);
vector<int> sol=restore_permutation(m,896,896);
bool ok=1;
for(i=0;i<m;i++) if(per[i]!=sol[i]) ok=0;
for(i=0;i<m;i++) printf("%i ",sol[i]);printf("\n");
if(ok) printf("OK\n");
printf("Add: %i, Chk: %i\n",add,chk);
return 0;
}*/
