#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include "messy.h"
using namespace std;
const int bits = 7;
const int maxN = 1 << bits;
int n;
int p[maxN];
map<string, bool> cache;
bool Query(const string& a)
{
auto it = cache.find(a);
if (it != cache.end())
return it->second;
return cache[a] = check_element(a);
}
void Add(int l, int r)
{
if (l == r)
return;
for (int i = l; i <= (l + r) / 2; ++i)
{
string add(n, '1');
for (int j = l; j <= r; ++j)
add[j] = '0';
add[i] = '1';
add_element(add);
}
Add(l, (l + r) / 2);
Add((l + r) / 2 + 1, r);
}
void Get(int curind, int bit)
{
if (!bit)
return;
string q(n, '1');
for (int j = 0; j < n; ++j)
if (p[j] == curind)
q[j] = '0';
for (int i = 0; i < n; ++i)
{
if (p[i] != curind) continue;
string curq = q;
curq[i] = '1';
if (!Query(curq))
p[i] = curind + bit;
}
Get(curind, bit >> 1);
Get(curind + bit, bit >> 1);
}
vector<int> restore_permutation(int n_, int w, int r) {
n = n_;
Add(0, n - 1);
compile_set();
Get(0, 1 << (__lg(n) - 1));
return vector<int>(p, p + n);
}
