#include <vector>
#include <numeric>
#include <algorithm>
#include <map>
#include "machine.h"
using namespace std;
vector<int> find_permutation(int N) {
// 1. Příprava vstupního pole A
// Použijeme čísla 0, 1, ..., N-2 a N. Vynecháme N-1.
// Tím rozbijeme symetrii pro XOR.
vector<int> A(N);
vector<int> target_set; // Pro porovnávání množin
map<int, int> val_to_original_index; // Abychom věděli, kde číslo původně bylo
for (int i = 0; i < N - 1; i++) {
A[i] = i;
}
A[N - 1] = N; // Tady je ten trik: skok o 2 (vynechali jsme N-1)
// Uložíme si, co jsme poslali, pro pozdější kontrolu
target_set = A;
sort(target_set.begin(), target_set.end());
// Mapování hodnoty na původní index v A
for(int i=0; i<N; i++) {
val_to_original_index[A[i]] = i;
}
// 2. Zavoláme stroj
vector<int> B = use_machine(A);
// 3. Najdeme X hrubou silou (0..255)
int found_X = -1;
for (int cand_X = 0; cand_X <= 255; cand_X++) {
vector<int> potential_A;
potential_A.reserve(N);
// Zkusíme od-XORovat výstup aktuálním kandidátem
for (int x : B) {
potential_A.push_back(x ^ cand_X);
}
// Seřadíme a porovnáme s tím, co jsme skutečně poslali
sort(potential_A.begin(), potential_A.end());
if (potential_A == target_set) {
found_X = cand_X;
break;
}
}
// 4. Rekonstruujeme permutaci
// Máme vrátit P, kde B[i] = A[P[i]] ^ X
// Tedy A[P[i]] = B[i] ^ found_X
// P[i] je index, na kterém v A leží hodnota (B[i] ^ found_X)
vector<int> P(N);
for (int i = 0; i < N; i++) {
int original_val = B[i] ^ found_X;
P[i] = val_to_original_index[original_val];
}
return P;
}
