#include<bits/stdc++.h>
#include "messy.h"
using namespace std;
int nbBits;
vector<int> rep;
string transfo(vector<int> v) {
string s;
for (int i:v) {
if (i==0) {
s+='0';
}
else {
s+='1';
}
}
//cout<<s<<endl;
return s;
}
void ajout(int deb,int fin) {
if (deb==fin) {
return;
}
vector<int> quest(nbBits);
for (int i=0;i<nbBits;i++) {
quest[i]=1;
}
for (int i=deb;i<=fin;i++) {
quest[i]=0;
}
int mid=(deb+fin)/2;
for (int i=deb;i<=mid;i++) {
quest[i]=1;
add_element(transfo(quest));
quest[i]=0;
}
ajout(deb,mid);
ajout(mid+1,fin);
}
void calc(int deb,int fin,vector<int> possi) {
/*cout<<deb<<" "<<fin<<" : ";
for (int i:possi) {
cout<<i<<" ";
}
cout<<endl;*/
if (deb==fin) {
rep[possi[0]]=deb;
return;
}
vector<int> quest(nbBits);
for (int i=0;i<nbBits;i++) {
quest[i]=1;
}
for (int i:possi) {
quest[i]=0;
}
vector<int> petit,grand;
int mid=(deb+fin)/2;
for (int i:possi) {
quest[i]=1;
if (check_element(transfo(quest))) {
petit.push_back(i);
}
else {
grand.push_back(i);
}
quest[i]=0;
}
calc(deb,mid,petit);
calc(mid+1,fin,grand);
}
vector<int> restore_permutation(int n, int w, int r) {
nbBits=n;
ajout(0,nbBits-1);
vector<int> initPossi;
compile_set();
rep.resize(nbBits);
for (int i=0;i<nbBits;i++) {
initPossi.push_back(i);
}
calc(0,nbBits-1,initPossi);
return rep;
}
