#include <vector>
#include <string>
#include <algorithm>
#include "messy.h"
using namespace std;
/**
* IOI 2016 - Unscrambling a Messy Bug
* n = 128 uchun w = 896, r = 896 cheklovlariga mos yechim.
*/
void build(int n, int l, int r) {
if (l + 1 == r) return;
int mid = (l + r) / 2;
// Chap bo'lakdagi bitlarni identifikatsiya qilish uchun maska qo'shamiz
string s(n, '1');
for (int i = l; i < r; i++) s[i] = '0';
for (int i = l; i < mid; i++) {
string t = s;
t[i] = '1';
add_element(t); // Chap bo'lakdagi har bir bit uchun bittadan son qo'shish [cite: 11, 50]
}
build(n, l, mid);
build(n, mid, r);
}
vector<int> p;
vector<int> ans;
void solve(int n, int l, int r, vector<int> avail) {
if (l + 1 == r) {
ans[avail[0]] = l;
return;
}
int mid = (l + r) / 2;
string s(n, '1');
for (int x : avail) s[x] = '0';
vector<int> left_side, right_side;
for (int x : avail) {
string t = s;
t[x] = '1';
if (check_element(t)) { // Agar son to'plamda bo'lsa, u chap bo'lakka tegishli [cite: 57, 61]
left_side.push_back(x);
} else {
right_side.push_back(x);
}
}
solve(n, l, mid, left_side);
solve(n, mid, r, right_side);
}
vector<int> restore_permutation(int n, int w, int r) {
// 1. Yozish bosqichi
build(n, 0, n);
compile_set(); // Permutatsiyani ishga tushirish [cite: 13, 31, 54]
// 2. O'qish va tiklash bosqichi
ans.resize(n);
vector<int> all_indices;
for (int i = 0; i < n; i++) all_indices.push_back(i);
solve(n, 0, n, all_indices);
// Permutatsiya p[i] ni qaytarish (qaysi i bit p[i] ga o'tgan) [cite: 19, 44]
vector<int> res(n);
for (int i = 0; i < n; i++) res[i] = ans[i];
return res;
}
