#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
int n;
vector < int > p;
void dnc_add(int left, int right)
{
if(left == right)
return;
int mid = left + (right - left) / 2;
string test;
for(int i = 0; i < n; i++)
{
test += '1';
}
for(int i = left; i <= right; i++)
{
test[i] = '0';
}
for(int i = left; i <= mid; i++)
{
test[i] = '1';
add_element(test);
test[i] = '0';
}
dnc_add(left, mid);
dnc_add(mid + 1, right);
}
void dnc_check(int left, int right, vector < int > idxs)
{
if(left == right)
{
p[idxs.back()] = left;
return;
}
int mid = left + (right - left) / 2;
vector < int > idxs_left;
vector < int > idxs_right;
string test;
for(int i = 0; i < n; i++)
{
test += '1';
}
for(int idx : idxs)
{
test[idx] = '0';
}
for(int idx : idxs)
{
test[idx] = '1';
if(check_element(test))
{
idxs_left.push_back(idx);
}
else
{
idxs_right.push_back(idx);
}
test[idx] = '0';
}
dnc_check(left, mid, idxs_left);
dnc_check(mid + 1, right, idxs_right);
}
vector < int > restore_permutation(int N, int w, int r)
{
n = N;
p.resize(n);
vector < int > idxs(n);
for(int i = 0; i < n; i++)
{
idxs[i] = i;
}
dnc_add(0, n - 1);
compile_set();
dnc_check(0, n - 1, idxs);
return p;
}
