#include <vector>
#include <string>
#include "messy.h"
using namespace std;
//int freqW, freqR;
string add;
void setAddInterval(int from, int to, char val) {
for(int i = from;i <= to;i++) {
add[i] = val;
}
}
void build(int from, int to) {
if(from == to) {
return;
}else {
int mid = (from + to) / 2;
for(int i = from;i <= mid;i++) {
add[i] = '1';
//freqW++;
//cerr << freqW << '\n';
//cerr << add << '\n';
add_element(add);
add[i] = '0';
}
setAddInterval(mid+1, to, '1');
build(from, mid);
setAddInterval(mid+1, to, '0');
setAddInterval(from, mid, '1');
build(mid+1, to);
setAddInterval(from, mid, '0');
}
}
string ser;
int const NMAX = 128;
int pos[1 + NMAX];
int perm[1 + NMAX];
bool outside[1 + NMAX];
void search(int from, int to, int n) {
if(from == to) {
for(int i = 0;i < n;i++) {
if(!outside[i]) {
pos[from] = i;
perm[pos[from]] = from;
return;
}
}
}else {
int mid = (from + to) / 2;
for(int i = 0;i < n;i++) {
if(outside[i]) {
ser[i] = '1';
}else {
ser[i] = '0';
}
}
vector <int> half1;
vector <int> half2;
for(int i = 0;i < n;i++) {
if(!outside[i]) {
ser[i] = '1';
//freqR++;
//cerr << freqR << '\n';
if(check_element(ser)) {
half1.push_back(i);
}else {
half2.push_back(i);
}
ser[i] = '0';
}
}
for(int i = 0;i < half2.size();i++) {
outside[half2[i]] = true;
}
search(from, mid, n);
for(int i = 0;i < half2.size();i++) {
outside[half2[i]] = false;
}
for(int i = 0;i < half1.size();i++) {
outside[half1[i]] = true;
}
search(mid+1, to, n);
for(int i = 0;i < half1.size();i++) {
outside[half1[i]] = false;
}
}
}
vector <int> restore_permutation(int n, int w, int r) {
add.resize(n);
setAddInterval(0, n-1, '0');
build(0, n-1);
compile_set();
ser.resize(n);
search(0, n-1, n);
vector <int> ans;
ans.resize(n);
//cerr << n << '\n';
for(int i = 0;i < n;i++) {
ans[i] = perm[i];
//cerr << perm[i];
}
return ans;
}
