#include <bits/stdc++.h>
#include "messy.h"
#define pb push_back
using namespace std;
int nBits;
void ajouterElements(int gauche, int droite){
if (gauche == droite)
return;
int milieu = (gauche + droite)/2;
for (int a0 = gauche; a0 <= milieu; ++a0){
string chaine = "";
for (int _ = 0; _ < nBits; ++_)
chaine += '0';
for (int ind = gauche; ind <= droite; ++ind)
chaine[ind] = '1';
chaine[a0] = '0';
add_element(chaine);
}
ajouterElements(gauche, milieu);
ajouterElements(milieu + 1, droite);
}
vector<int> permutation;
void retrouver(int gauche, int droite, vector<int> iChiffres){
if (gauche == droite){
permutation[gauche] = iChiffres[0];
return;
}
vector<int> aGauche, aDroite;
for (int ind = gauche; ind <= droite; ++ind){
string chaine = "";
for (int _ = 0; _ < nBits; ++_)
chaine += '0';
for (int iChiffre : iChiffres)
chaine[iChiffre] = '1';
chaine[ind] = '0';
if (check_element(chaine))
aGauche.pb(ind);
else
aDroite.pb(ind);
}
int milieu = (gauche + droite)/2;
retrouver(gauche, milieu, aGauche);
retrouver(milieu + 1, droite, aDroite);
}
vector<int> restore_permutation(int n, int w, int r) {
nBits = n;
permutation.resize(nBits);
for (int ind = 0; ind < nBits; ++ind)
permutation[ind] = ind;
ajouterElements(0, nBits - 1);
compile_set();
retrouver(0, nBits - 1, permutation);
/*for (int e : permutation)
cout << e << " ";
cout << endl;*/
return permutation;
}
