#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
#include "machine.h"
using namespace std;
std::vector<int> find_permutation(int N) {
// STRATEGIE: Množina {3, 4, ..., N+2}
// Vynecháním 0, 1, 2 zaručíme, že se množina při XORu s malým X
// netransformuje sama na sebe.
vector<int> A(N);
vector<int> target_set;
map<int, int> val_to_original_index;
// Naplníme A čísly 3, 4, ..., N+2
for (int i = 0; i < N; i++) {
A[i] = i + 3;
val_to_original_index[A[i]] = i; // Uložíme si, kde které číslo bylo
}
// Uložíme si setříděnou verzi pro porovnávání
target_set = A;
sort(target_set.begin(), target_set.end());
// 1. Jediný povolený dotaz
vector<int> B = use_machine(A);
// 2. Najdeme X hrubou silou
// Hledáme takové X, pro které platí: sorted(B ^ X) == sorted(A)
int found_X = -1;
// Musíme vyzkoušet všechna možná X (0-255)
for (int cand_X = 0; cand_X <= 255; cand_X++) {
vector<int> decoded_B;
decoded_B.reserve(N);
bool possible = true;
for (int x : B) {
int val = x ^ cand_X;
// Optimalizace: Pokud hodnota po XORu vůbec není v našem rozsahu,
// rovnou víme, že toto X je špatné.
// Naše hodnoty jsou v rozsahu <3, N+2>
if (val < 3 || val > N + 2) {
possible = false;
break;
}
decoded_B.push_back(val);
}
if (!possible) continue;
// Pokud čísla sedí rozsahově, zkontrolujeme přesnou shodu množin
sort(decoded_B.begin(), decoded_B.end());
if (decoded_B == target_set) {
found_X = cand_X;
break; // Našli jsme správné X, končíme hledání
}
}
// Záchranná brzda (neměla by nastat, pokud je úloha korektní)
if (found_X == -1) {
// Pokud se to stane, zkusíme fallback na X=0 nebo vrátíme identitu
found_X = 0;
}
// 3. Rekonstrukce permutace
// Víme, že B[i] = A[P[i]] ^ X
// Tedy: A[P[i]] = B[i] ^ X
// Z hodnoty (B[i] ^ X) zjistíme, na jakém indexu v A byla (pomocí mapy)
vector<int> P(N);
for (int i = 0; i < N; i++) {
int original_val = B[i] ^ found_X;
// Najdeme index, na kterém byla tato hodnota v poli A
P[i] = val_to_original_index[original_val];
}
return P;
}
