#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
/* Idea: Use Divide and Conquer, set each bits in interval le...ri to 1 once, adding it to data structure.
For all bits outside interval, set it to 1.
Then when checking, you can see which elemnts belong to interval le...mid and (mid + 1)...ri, then
apply DnC normally.
*/
void add_permutation(int le, int ri, int N) {
string element;
for (int i = 0; i < N; i++) element.push_back('1');
for (int i = le; i <= ri; i++) element[i - 1] = '0';
if (le >= ri) return;
int mid = (le + ri) / 2;
for (int i = le; i <= mid; i++) {
element[i - 1] = '1';
add_element(element);
element[i - 1] = '0';
}
add_permutation(le, mid, N);
add_permutation(mid + 1, ri, N);
}
void get_permutation(int le, int ri, vector<int> forbidden, vector<int> &ans, int N) {
string element;
for (int i = 0; i < N; i++) element.push_back('0');
for (auto i : forbidden) element[i - 1] = '1';
if (le == ri) {
for (int i = 0; i < N; i++) {
if (element[i] == '0') {
ans[i] = le - 1;
return;
}
}
}
vector<int> left_forbidden = forbidden, right_forbidden = forbidden;
for (int i = 1; i <= N; i++) {
if (element[i - 1] == '1') continue;
element[i - 1] = '1';
if (check_element(element)) {
right_forbidden.push_back(i);
} else {
left_forbidden.push_back(i);
}
element[i - 1] = '0';
}
int mid = (le + ri) / 2;
get_permutation(le, mid, left_forbidden, ans, N);
get_permutation(mid + 1, ri, right_forbidden, ans, N);
}
vector<int> restore_permutation(int n, int w, int r) {
vector<int> res(n);
add_permutation(1, n, n);
compile_set();
get_permutation(1, n, vector<int>(), res, n);
return res;
}
