#include <vector>
#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
namespace subtask_1 {
const int N = 8, W = 256, R = 256;
vector<int> perm;
string get_str(int l, int r) {
int m = (l + r) >> 1;
string str(N, '0');
fill(str.begin() + l, str.begin() + m + 1, '1');
return str;
}
template <class F>
void traverse_tree(F f, int l = 0, int r = N - 1) {
if (l == r)
return;
bool ok = f(l, r);
if (not ok)
return;
int m = (l + r) >> 1;
traverse_tree(f, l, m);
traverse_tree(f, m + 1, r);
}
void add_elements() {
traverse_tree([&](int l, int r) {
add_element(get_str(l, r));
return true;
});
}
void check_elements() {
vector<int> inds;
traverse_tree([&](int l, int r) {
string str = get_str(l, r);
int m = (l + r) >> 1;
for (int i = l; i <= m; i++)
for (int j = m + 1; j <= r; j++) {
swap(str[i], str[j]);
if (check_element(str)) {
inds = {i, j};
return false;
}
swap(str[i], str[j]);
}
return true;
});
perm.resize(N);
iota(perm.begin(), perm.end(), 0);
if (not inds.empty())
swap(perm[inds.front()], perm[inds.back()]);
return;
}
vector<int> restore_permutation() {
add_elements();
compile_set();
check_elements();
return perm;
}
};
namespace subtask_2 {
int N, W, R;
vector<int> perm, inds;
void add_elements() {
inds.resize(N);
iota(inds.begin(), inds.end(), 0);
shuffle(inds.begin(), inds.end(), mt19937(0));
string tmp(N, '0');
for (int i : inds) {
tmp[i] = '1';
add_element(tmp);
}
}
void check_elements() {
perm.resize(N);
string tmp(N, '0');
for (int i : inds) {
for (int x : inds) if (tmp[x] == '0') {
tmp[x] ^= 1;
if (check_element(tmp)) {
perm[x] = i;
//cout << "perm[" << x << "] = " << i << endl;
break;
}
tmp[x] ^= 1;
}
}
}
vector<int> restore_permutation(int n, int w, int r) {
N = n, W = w, R = r;
add_elements();
compile_set();
check_elements();
return perm;
}
};
namespace subtask_full {
vector<int> perm;
void add_elements() {
}
void check_elements() {
}
vector<int> restore_permutation(int n, int w, int r) {
return perm;
}
};
vector<int> restore_permutation(int n, int w, int r) {
/*
if (n == 8 and w == 256 and r == 256)
return subtask_1::restore_permutation();
*/
//if (n == 32)
return subtask_2::restore_permutation(n, w, r);
return subtask_full::restore_permutation(n, w, r);
}
