#include "messy.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <bitset>
#include <random>
typedef long long llong;
const int MAXN = 256;
const int MAXLOG = 8;
const int INF = 1e9;
int p[MAXN];
int posOf[MAXN];
int sorted[MAXN];
std::vector <int> perm;
std::bitset <MAXN> bs[MAXLOG];
std::vector <int> restore_permutation(int n, int w, int r)
{
if (n <= 8)
{
perm.resize(n);
std::string element(n, '0');
for (int i = 0 ; i < n ; ++i)
{
element[i] = '1';
add_element(element);
}
compile_set();
std::mt19937 mt(69420);
std::fill(element.begin(), element.end(), '0');
for (int i = 0 ; i < n ; ++i)
{
std::vector <int> zeroPos;
for (int j = 0 ; j < n ; ++j)
{
if (element[j] == '0')
{
zeroPos.push_back(j);
}
}
bool found = false;
std::shuffle(zeroPos.begin(), zeroPos.end(), mt);
for (int j = 0 ; j < zeroPos.size() - 1 ; ++j)
{
element[zeroPos[j]] = '1';
if (check_element(element))
{
perm[zeroPos[j]] = i;
found = true;
break;
}
element[zeroPos[j]] = '0';
}
if (!found)
{
element[zeroPos.back()] = '1';
perm[zeroPos.back()] = i;
}
}
} else
{
perm.resize(n);
std::string element(n, '1'); element[0] = '0';
for (int i = 0 ; (1 << i) < n ; ++i)
{
add_element(element);
element[1 << i] = '0';
}
add_element(element);
std::fill(element.begin(), element.end(), '0'); element[0] = '1';
for (int bit = 0 ; (1 << bit) < n ; ++bit)
{
element[1 << bit] = '1';
for (int i = (1 << bit) + 1 ; i < n ; ++i)
{
if (i & (1 << bit))
{
element[i] = '1';
add_element(element);
element[i] = '0';
}
}
}
std::mt19937 mt(69);
compile_set();
std::fill(element.begin(), element.end(), '1');
std::fill(posOf, posOf + n, -1);
std::iota(p, p + n, 0);
std::shuffle(p, p + n, mt);
for (int i = 0 ; i < n ; ++i)
{
element[p[i]] = '0';
if (check_element(element))
{
posOf[0] = p[i];
break;
}
element[p[i]] = '1';
}
std::iota(p, p + n, 0);
std::shuffle(p, p + n, mt);
for (int i = 0 ; (1 << i) < n ; ++i)
{
for (int j = 0 ; j < n ; ++j)
{
if (element[p[j]] == '0')
{
continue;
}
element[p[j]] = '0';
if (check_element(element))
{
posOf[1 << i] = p[j];
break;
}
element[p[j]] = '1';
}
}
std::iota(p, p + n, 0);
std::shuffle(p, p + n, mt);
std::fill(element.begin(), element.end(), '0'); element[posOf[0]] = '1';
for (int bit = 0 ; (1 << bit) < n ; ++bit)
{
bs[bit].reset();
element[posOf[1 << bit]] = '1';
for (int i = 0 ; i < n ; ++i)
{
if (element[p[i]] == '1')
{
continue;
}
element[p[i]] = '1';
if (check_element(element))
{
bs[bit][p[i]] = 1;
}
element[p[i]] = '0';
}
}
std::iota(sorted, sorted + n, 0);
std::sort(sorted, sorted + n, [&](int x, int y)
{
return __builtin_popcount(x) < __builtin_popcount(y);
});
for (int i = n - 1 ; i >= 0 ; --i)
{
int num = sorted[i];
if (posOf[num] != -1)
{
break;
}
std::bitset <MAXN> curr;
for (int j = 0 ; j < n ; ++j)
{
curr[j] = 1;
}
for (int bit = 0 ; (1 << bit) < n ; ++bit)
{
if (num & (1 << bit))
{
curr &= bs[bit];
}
}
posOf[num] = curr._Find_first();
for (int bit = 0 ; (1 << bit) < n ; ++bit)
{
if (num & (1 << bit))
{
bs[bit][posOf[num]] = 0;
}
}
}
for (int i = 0 ; i < n ; ++i)
{
perm[posOf[i]] = i;
}
}
return perm;
}
