#include "machine.h"
#include <vector>
std::vector<int> find_permutation(int N) {
// 1. Find the hidden XOR value X
// We send an array of all zeros.
// B[i] = A[P[i]] ^ X => B[i] = 0 ^ X = X.
std::vector<int> zero_input(N, 0);
std::vector<int> res_x = use_machine(zero_input);
int X = res_x[0];
// 2. Find the permutation P
// We send an array where each index contains its own value.
// A = {0, 1, 2, ..., N-1}
std::vector<int> id_input(N);
for (int i = 0; i < N; ++i) {
id_input[i] = i;
}
std::vector<int> res_p = use_machine(id_input);
// 3. Reconstruct P
// B[i] = A[P[i]] ^ X
// Since A[j] = j, then B[i] = P[i] ^ X
// Therefore, P[i] = B[i] ^ X
std::vector<int> P(N);
for (int i = 0; i < N; ++i) {
P[i] = res_p[i] ^ X;
}
return P;
}
