Submission #1316963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316963		spetr	Machine (IOI24_machine)	C++20	10 / 100	5 ms	440 KiB

machine

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

• Subtask 0: 0 / 0
• Subtask 1: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 19
• Subtask 4: 0 / 21
• Subtask 5: 10 / 10
• Subtask 6: 0 / 31