Submission #1316961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316961		spetr	Machine (IOI24_machine)	C++20	10 / 100	43 ms	424 KiB

machine

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

• 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