#include "machine.h"
#include <vector>
std::vector<int> find_permutation(int N) {
// We use a shift value larger than the maximum possible value of X (255).
// 512 is 2^9, which gives us a safe buffer.
const int SHIFT = 512;
std::vector<int> A(N);
for (int j = 0; j < N; ++j) {
// A[j] encodes the index j in the high bits
A[j] = j * SHIFT;
}
// Single allowed call to the machine
std::vector<int> B = use_machine(A);
// X is hidden in the lower bits of every element in B
// Since A[P[i]] = P[i] * 512, then B[i] = (P[i] * 512) ^ X
// Because X < 512, the XOR operation doesn't carry into the P[i] bits.
int X = B[0] % SHIFT;
std::vector<int> P(N);
for (int i = 0; i < N; ++i) {
// Extract P[i] by shifting back or dividing
P[i] = B[i] / SHIFT;
}
return P;
}
