#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; }