#include <vector>
#include "messy.h"
#include <numeric>
using namespace std;
void setNumbers(int l, int r, int n)
{
if (l == r) return;
int m = (l + r) >> 1;
string number(n, '1');
for (int i = l; i <= r; ++i) number[i] = '0';
for (int i = l; i <= m; ++i)
{
number[i] = '1';
add_element(number);
number[i] = '0';
}
setNumbers(l, m, n);
setNumbers(m + 1, r, n);
}
void getPermutation(int l, int r, vector<int> inds, vector<int> &p)
{
if (l == r)
{
p[inds[0]] = l;
return;
}
string number(p.size(), '1');
for (int i : inds) number[i] = '0';
vector<int> left, right;
for (int i : inds)
{
number[i] = '1';
if (check_element(number)) left.push_back(i);
else right.push_back(i);
number[i] = '0';
}
int m = (l + r) >> 1;
getPermutation(l, m, left, p);
getPermutation(m + 1, r, right, p);
}
vector<int> restore_permutation(int n, int w, int r)
{
setNumbers(0, n - 1, n);
compile_set();
vector<int> p(n);
vector<int> inds(n);
iota(inds.begin(), inds.end(), 0);
getPermutation(0, n - 1, inds, p);
return p;
}
