#include <vector>
#include <iostream>
#include <map>
#include "messy.h"
std::vector<int> ans;
std::string cur[100010] = { "" };
std::vector< std::vector<int> > ansing(100010);
std::map<int, int> mapa;
void insertion(int low, int high, std::string str, int pos)
{
if (low == high)
return;
int mid = low + (high - low) / 2;
for (int i = low; i <= mid; ++i)
{
str[i] = '1';
add_element(str);
str[i] = '0';
}
for (int i = mid + 1; i <= high; ++i)
{
str[i] = '1';
}
insertion(low, mid, str, pos * 2 + 1);
for (int i = mid + 1; i <= high; ++i)
{
str[i] = '0';
}
str[low] = '1';
insertion(mid + 1, high, str, pos * 2 + 2);
str[low] = '0';
cur[pos] = str;
}
void checking(int low, int high, std::string str, int pos)
{
if (low == high)
{
ans[ansing[pos][0]] = low;
mapa.insert(std::make_pair(low, ansing[pos][0]));
return;
}
for (int i = 0; i < ansing[pos].size(); ++i)
{
int val = ansing[pos][i];
str[val] = '1';
// std::cout << str << " " << check_element(str) << " ";
if (check_element(str))
{
ansing[pos * 2 + 1].push_back(val);
}
else
{
ansing[pos * 2 + 2].push_back(val);
}
str[val] = '0';
}
// std::cout << "\n";
std::string temp = str;
for (int i = 0; i < ansing[pos * 2 + 2].size(); ++i)
{
int val = ansing[pos * 2 + 2][i];
str[val] = '1';
}
int mid = low + (high - low) / 2;
checking(low, mid, str, pos * 2 + 1);
temp[mapa[low]] = '1';
checking(mid + 1, high, temp, pos * 2 + 2);
}
std::vector<int> restore_permutation(int n, int w, int r) {
std::string str = "";
for (int i = 0; i < n; ++i)
{
str += "0";
ans.push_back(0);
ansing[0].push_back(i);
}
insertion(0, n - 1, str, 0);
compile_set();
checking(0, n - 1, str, 0);
return ans;
}
