#include <vector>
#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
int sz;
void add(int mask) {
string s;
for(int i = 0; i < sz; i++) {
s += (mask >> i & 1) + '0';
}
add_element(s);
}
bool check(int mask) {
string s;
for(int i = 0; i < sz; i++) {
s += (mask >> i & 1) + '0';
}
return check_element(s);
}
int popcount(int mask) {
return __builtin_popcount(mask);
}
std::vector<int> restore_permutation(int n, int w, int r) {
sz = n;
int mask1 = 0, mask2 = 0, mask3 = 0;
for(int i = 0, cur = 0; i < n; i++, cur ^= 1) {
mask1 |= (cur << i);
}
for(int i = 0, cur = 0; i < n; i += 2, cur ^= 1) {
mask2 |= (cur << i);
}
for(int i = 1, cur = 0; i < n; i += 2, cur ^= 1) {
mask3 |= (cur << i);
}
add(mask1); // (i & 1) != (j & 1)
add(mask2); // even
add(mask3); // odd
compile_set();
set<int> st;
for(int mask = 0; mask < (1 << n); mask++) {
if(check(mask)) st.emplace(mask);
}
vector<int> p(n);
iota(p.begin(), p.end(), 0);
auto dif = [&](int m1, int m2) {
vector<int> ind;
for(int i = 0; i < n; i++) {
if((m1 >> i & 1) != (m2 >> i & 1)) ind.push_back(i);
}
if(ind.empty()) return;
swap(p[ind[0]], p[ind[1]]);
};
if(st.count(mask1)) {
st.erase(mask1);
if(st.count(mask2)) {
st.erase(mask2);
dif(mask3, *st.begin());
} else {
assert( st.count(mask3) );
st.erase(mask3);
dif(mask2, *st.begin());
}
} else {
for(auto mask : st) {
if(popcount(mask) == n / 2) {
dif(mask1, mask);
break;
}
}
}
return p;
}
