#include <bits/stdc++.h>
// #include "grader.cpp"
// #include "messy.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
int used_buffers[130];
vi perm;
map<ii, string> range_bases;
void construct_perm(int l, int r) {
// cerr << "// construct_perm(" << l << ", " << r << ")\n";
int interval_size = r - l;
int m = (l + r) / 2;
if (interval_size == 1) return;
string base = range_bases[ii(l, r)];
string new_base = range_bases[ii(l, r)];
for (int i = 0; i < n; i++) {
new_base[perm[i]] = base[i];
}
base = new_base;
// cerr << "// base : " << base << '\n';
set<int> left_locations, right_locations;
for (int i = l; i < r; i++) {
right_locations.insert(perm[i]);
}
for (int i = l; i < r; i++) {
string input = "";
copy(base.begin(), base.end(), back_inserter(input));
// cerr << "// perm[" << i << "] : " << perm[i] << '\n';
// assert((perm[i] == '0') && "perm[i] is occupied!");
input[perm[i]] = '1';
if (check_element(input)) {
// cerr << "// " << input << " is present!\n";
left_locations.insert(perm[i]);
right_locations.erase(perm[i]);
}
}
// cerr << "// left_locations :";
// for (int ele : left_locations) cerr << ' ' << ele;
// cerr << '\n';
// cerr << "// right_locations :";
// for (int ele : right_locations) cerr << ' ' << ele;
// cerr << '\n';
for (int i = l; i < r; i++) {
if (i < m) {
perm[i] = *left_locations.begin();
left_locations.erase(perm[i]);
} else {
perm[i] = *right_locations.begin();
right_locations.erase(perm[i]);
}
}
// cerr << "// perm :";
// for (int ele : perm) cerr << ' ' << ele;
// cerr << '\n';
construct_perm(l, m);
construct_perm(m, r);
}
vi restore_permutation(int n, int w, int r) {
for (int window_size = n; window_size >= 2; window_size /= 2) {
// cerr << "// window_size : " << window_size << '\n';
int sub_window_size = window_size / 2;
for (int i = 0; i < n; i += window_size) {
string base = "";
for (int j = 0; j < n; j++) {
bool bit = 0;
if (i) {
if (j < sub_window_size) bit = 1;
}
if (j >= i + window_size) bit = 1;
base += (bit ? "1" : "0");
}
range_bases[ii(i, i + window_size)] = base;
for (int k = i; k < i + sub_window_size; k++) {
string input = "";
copy(base.begin(), base.end(), back_inserter(input));
input[k] = '1';
// cerr << "// input : " << input << '\n';
add_element(input);
}
}
}
compile_set();
perm.resize(n);
for (int i = 0; i < n; i++) {
perm[i] = i;
}
construct_perm(0, n);
vi new_perm(n, 0);
for (int i = 0; i < n; i++) {
new_perm[perm[i]] = i;
}
perm = new_perm;
return perm;
}
// 0000000000000000
// ????????00000000 : 0
// ????000011111111 : 8
// 11110000????0000 : 4
// ??00111111111111 : 12
// 1100??0011111111 : 10
// 11000000??001111 : 6
// 110000000000??00 : 2
// ?011111111111111 : 14
// 1011111111111111 : 14
Compilation message
messy.cpp: In function 'void construct_perm(int, int)':
messy.cpp:24:22: error: 'n' was not declared in this scope
24 | for (int i = 0; i < n; i++) {
| ^
messy.cpp:43:7: error: 'check_element' was not declared in this scope
43 | if (check_element(input)) {
| ^~~~~~~~~~~~~
messy.cpp: In function 'vi restore_permutation(int, int, int)':
messy.cpp:100:5: error: 'add_element' was not declared in this scope
100 | add_element(input);
| ^~~~~~~~~~~
messy.cpp:105:2: error: 'compile_set' was not declared in this scope
105 | compile_set();
| ^~~~~~~~~~~
