Submission #1170259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170259		madamadam3	Machine (IOI24_machine)	C++20	10 / 100	48 ms	476 KiB

machine

#include "machine.h"
#include <bits/stdc++.h>
using namespace std;

int n;

bool validate(const vector<int>& candidate, const vector<int>& S) {
    vector<int> sortedCandidate = candidate, sortedS = S;
    sort(sortedCandidate.begin(), sortedCandidate.end());
    sort(sortedS.begin(), sortedS.end());
    return sortedCandidate == sortedS;
}

vector<int> find_permutation(int N) {
    n = N;
    vector<int> A(N), S(N);
    
    if (N % 2 == 1) {
        for (int i = 0; i < N; i++) {
            A[i] = i + 1;
            S[i] = i + 1;
        }
    } else {
        for (int i = 0; i < N - 2; i++) {
            A[i] = i;      
            S[i] = i;
        }
        A[N - 2] = N + 1;
        A[N - 1] = N + 2;
        S[N - 2] = N + 1;
        S[N - 1] = N + 2;
    }
    
    vector<int> B = use_machine(A);
    
    int trueX = -1;
    vector<int> candidateArr(N);
    
    for (int x = 0; x < 256; x++) {
        for (int i = 0; i < N; i++) {
            candidateArr[i] = B[i] ^ x;
        }
        if (validate(candidateArr, S)) {
            trueX = x;
            break;
        }
    }
    
    if (trueX < 0)
        return vector<int>();
    
    for (int i = 0; i < N; i++) {
        candidateArr[i] = B[i] ^ trueX;
    }
    
    unordered_map<int, int> pos;
    for (int j = 0; j < N; j++) {
        pos[A[j]] = j;
    }
    
    vector<int> P(N);
    for (int i = 0; i < N; i++) {
        P[i] = pos[candidateArr[i]];
    }
    
    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