#include "messy.h"
#include <vector>
#include <string>
using namespace std;
/**
* The goal is to find where each index 'i' ends up in the scrambled version.
* We use a Divide and Conquer approach:
* 1. "Tag" indices in the first half of a range.
* 2. Later, "Check" which scrambled positions have that tag.
*/
void encode_range(int start, int end, int n) {
if (start + 1 >= end) return; // Base case: range of size 1
int mid = start + (end - start) / 2;
// Create a "mask" where only bits in our current [start, end) are '0'
string mask(n, '1');
for (int i = start; i < end; i++) {
mask[i] = '0';
}
// "Add" elements to the set to mark everything in the LEFT half
for (int i = start; i < mid; i++) {
string query = mask;
query[i] = '1';
add_element(query);
}
// Recursively handle the left and right halves
encode_range(start, mid, n);
encode_range(mid, end, n);
}
void decode_range(int start, int end, int n, const vector<int>& scrambled_indices, vector<int>& mapping) {
if (start + 1 >= end) {
// We've narrowed it down to a single position!
// This scrambled position corresponds to the original index 'start'.
mapping[scrambled_indices[0]] = start;
return;
}
int mid = start + (end - start) / 2;
// Create a mask where only the scrambled positions we are currently
// considering are set to '0'.
string mask(n, '1');
for (int pos : scrambled_indices) {
mask[pos] = '0';
}
vector<int> left_half_positions;
vector<int> right_half_positions;
for (int pos : scrambled_indices) {
string query = mask;
query[pos] = '1';
// If the system recognizes this pattern, it was one we "tagged"
// in the encode phase as being in the left half.
if (check_element(query)) {
left_half_positions.push_back(pos);
} else {
right_half_positions.push_back(pos);
}
}
decode_range(start, mid, n, left_half_positions, mapping);
decode_range(mid, end, n, right_half_positions, mapping);
}
vector<int> restore_permutation(int n, int w, int r) {
// Phase 1: Encode the hierarchy into the messy set
encode_range(0, n, n);
compile_set();
// Phase 2: Decode the hierarchy by checking scrambled positions
vector<int> initial_positions;
for (int i = 0; i < n; i++) initial_positions.push_back(i);
vector<int> result_permutation(n);
decode_range(0, n, n, initial_positions, result_permutation);
return result_permutation;
}
