#include "messy.h"
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
void write_specials(int n, int special);
void write_range(int l, int r, int n, int depth);
std::vector<int> find_specials(int n, int special);
void solve_range(int n, int l, int r, int depth, std::vector<int> indexes, std::vector<int> specials, std::vector<int>& ans);
std::vector<int> restore_permutation(int n, int w, int r) {
int logn = 0;
while (1 << logn < n) ++logn;
int special = logn - 1; // These are calculated explicitly
write_specials(n, special);
write_range(special, n - 1, n, 0);
compile_set();
std::vector<int> specials = find_specials(n, special);
std::vector<int> ans(n, -1);
for (int i = 0; i < special; ++i) ans[specials[i]] = i;
std::vector<int> nonspecial;
for (int i = 0; i < n; ++i) {
if (ans[i] == -1) nonspecial.push_back(i);
}
solve_range(n, special, n - 1, 0, nonspecial, specials, ans);
return ans;
}
void write_specials(int n, int special) {
for (int i = 0; i < special; ++i) {
std::string writebuf(n, '1');
writebuf[i] = '0';
add_element(writebuf);
}
std::string writebuf(n, '0');
for (int i = 0; i < special; ++i) {
writebuf[i] = '1';
add_element(writebuf);
}
}
void write_range(int l, int r, int n, int depth) {
// std::cout << "writing range from " << l << " to " << r << " with depth " << depth << '\n';
if (l > r) return;
if (l == r) return;
int m = (l + r - 1) / 2;
std::string setspecials(n, '0');
// set first `depth` special bits
for (int i = 0; i < depth; ++i) {
setspecials[i] = '1';
}
for (int i = l; i <= m; ++i) {
std::string writebuf = setspecials;
writebuf[i] = '1';
add_element(writebuf);
}
write_range(l, m, n, depth + 1);
write_range(m + 1, r, n, depth + 1);
}
std::vector<int> find_specials(int n, int special) {
std::vector<int> unordered;
for (int i = 0; i < n; ++i) {
std::string readbuf(n, '1');
readbuf[i] = '0';
if (check_element(readbuf)) {
unordered.push_back(i);
}
}
std::cout << unordered.size() << '\n';
std::vector<int> seen(special);
std::vector<int> ordered;
for (int i = 0; i < special; ++i) {
for (int j = 0; j < special; ++j) {
std::string readbuf = std::string(n, '0');
for (int k : ordered) {
readbuf[k] = '1';
}
if (seen[j]) continue;
readbuf[unordered[j]] = '1';
if (check_element(readbuf)) {
seen[j] = true;
ordered.push_back(unordered[j]);
break;
}
}
}
return ordered;
}
void solve_range(int n, int l, int r, int depth, std::vector<int> indexes, std::vector<int> specials, std::vector<int>& ans) {
assert(indexes.size() == r - l + 1);
if (l > r) return;
if (l == r) {
ans[indexes[0]] = l;
return;
}
int m = (l + r - 1) / 2;
int lcount = m - l + 1;
std::vector<int> left, right;
std::string setspecials(n, '0');
for (int i = 0; i < depth; ++i) setspecials[specials[i]] = '1';
for (int index : indexes) {
if (index == indexes.back()) {
if (left.size() < lcount) {
left.push_back(index);
} else {
right.push_back(index);
}
break;
}
std::string readbuf = setspecials;
readbuf[index] = '1';
if (check_element(readbuf)) {
left.push_back(index);
} else {
right.push_back(index);
}
}
solve_range(n, l, m, depth + 1, left, specials, ans);
solve_range(n, m + 1, r, depth + 1, right, specials, ans);
}
