#include "machine.h"
#include <vector>
#include <numeric>
#include <algorithm>
/**
* Checks if a candidate XOR value (X) correctly transforms the machine's
* output back into the original input values we provided.
*/
bool is_correct_x(int candidate_x, const std::vector<int>& input_a, const std::vector<int>& machine_output_b) {
int n = machine_output_b.size();
std::vector<int> recovered_values(n);
for (int i = 0; i < n; ++i) {
recovered_values[i] = machine_output_b[i] ^ candidate_x;
}
// Since the machine shuffles the array, we sort both to compare the sets
std::sort(recovered_values.begin(), recovered_values.end());
// input_a is already sorted based on how we constructed it
return recovered_values == input_a;
}
std::vector<int> find_permutation(int N) {
// 1. Construct a unique input array A.
// We use {1, 2, ..., N-1, N+2}. This stays within the M <= N+2 limit.
std::vector<int> A(N);
std::iota(A.begin(), A.end(), 1);
A.back() += 2;
// 2. Query the machine exactly once.
// Returns B[i] = A[P[i]] ^ X[cite: 30].
std::vector<int> B = use_machine(A);
// 3. Brute-force find the hidden XOR constant X.
// X is between 0 and 255[cite: 37].
int hidden_x = 0;
for (int x = 0; x < 256; ++x) {
if (is_correct_x(x, A, B)) {
hidden_x = x;
break;
}
}
// 4. Reconstruct the permutation P.
// Initially, recovered[i] = A[P[i]].
std::vector<int> P(N);
for (int i = 0; i < N; ++i) {
int original_a_val = B[i] ^ hidden_x;
// Map the value from A back to the index in A.
// If the value is N+2, its index was N-1.
// Otherwise, the index was (value - 1).
if (original_a_val == N + 2) {
P[i] = N - 1;
} else {
P[i] = original_a_val - 1;
}
}
return P;
}
