#include <bits/stdc++.h>
#include "messy.h"
void divide(int la,int ra,std::string tot){
if(la==ra){
return;
}
int m = (la+ra)/2;
///Adiciona N/2 elementos por nivel
for(int i=la;i<=m;++i){
std::string x = tot;
x[i]='1';
add_element(x);
}
{
std::string copia = tot;
for(int i=m+1;i<=ra;++i){
copia[i]='1';
}
divide(la,m,copia);
}
{
std::string copia = tot;
for(int i=la;i<=m;++i){
copia[i]='1';
}
divide(m+1,ra,copia);
}
}
int indices[300];
void gerar(int la,int ra,std::vector<int> valido,std::string lixo){
if(la==ra){
/// std::cout<<valido.size()<<"\n";
assert(valido.size()==1);
indices[valido[0]]=la;
return;
}
/// std::cout<<valido.size()<<" "<<(ra-la+1)<<" "<<la<<" "<<ra<<"\n";
std::vector<int> a,b;
for(auto&x:valido){
std::string copia = lixo;
copia[x]='1';
bool res = check_element(copia);
if(res){
a.push_back(x);
}else b.push_back(x);
}
/// std::cout<<valido.size()<<" "<<(ra-la+1)<<" "<<a.size()<<" "<<b.size()<<"\n";
int m = (la+ra)/2;
{
std::string novastr=lixo;
for(auto&x:b)novastr[x]='1';
gerar(la,m,a,novastr);
}
{
std::string novastr=lixo;
for(auto&x:a)novastr[x]='1';
gerar(m+1,ra,b,novastr);
}
}
std::vector<int> restore_permutation(int n, int w, int r) {
std::string g;
for(int i=0;i!=n;++i)g+='0';
std::vector<int> a;
for(int i=0;i!=n;++i)a.push_back(i);
/// std::cout<<a.size()<<"!!\n";
divide(0,n-1,g);
/// std::cout<<"ok\n";
compile_set();
gerar(0,n-1,a,g);
std::vector<int> ans;
for(int i=0;i!=n;++i)ans.push_back(indices[i]);
return ans;
}
