Submission #1127793

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127793		totoro	Machine (IOI24_machine)	C++20	100 / 100	8 ms	440 KiB

machine

// SOLVED   SUBTASK 1 (07 pts)
// UNSOLVED SUBTASK 2 (12 pts)
// UNSOLVED SUBTASK 3 (19 pts)
// UNSOLVED SUBTASK 4 (21 pts)
// SOLVED   SUBTASK 5 (10 pts)
// UNSOLVED SUBTASK 6 (31 pts)
// [+-+]----------------------
// TOTAL     17/100 pts

#include "machine.h"

#include <cassert>
#include <iostream>

std::vector<int> find_permutation(int N) {
    if (N & 1) {
        std::vector<int> A(N);
        int xorsum = 0;
        for (int i = 0; i < N; i++)
            A[i] = i, xorsum ^= i;
        std::vector<int> ans = use_machine(A);
        int X = xorsum;
        for (auto el : ans) X ^= el;
        std::vector<int> P(N);
        std::transform(ans.begin(), ans.end(), P.begin(), [X](int x) { return x ^ X; });
        return P;
    }

    // N is even
    assert(!(N & 1));

    std::vector<int> A(N);
    for (int i = 0; i < N; i++)
        A[i] = i;

    if (N % 4 != 0) {
        A[N - 3] = N;
    }
    A[N - 1] = N + 2;

    // std::cout << "SUBMITTING ";
    // for (auto el : A) {
    //     std::cout << el << ' ';
    // }
    // std::cout << std::endl;

    std::vector<int> ans = use_machine(A);

    // std::cout << "RECEIVED ";
    // for (auto el : ans) {
    //     std::cout << el << ' ';
    // }
    // std::cout << std::endl;

    int X;
    for (X = 0; X < 256; ++X) {
        bool ok = true;
        for (auto el : ans) {
            if ((el ^ X) > N + 2) ok = false;
            if ((el ^ X) == N - 1) ok = false;
            if ((el ^ X) == N - 3 && (N % 4 != 0)) ok = false;
            if ((el ^ X) == N && (N % 4 == 0)) ok = false;
        }
        if (ok) break;
    }
    // std::cout << "X is " << X << std::endl;
    std::vector<int> P(N);
    std::transform(ans.begin(), ans.end(), P.begin(), [X, N](int x) {
        int xx = x ^ X;
        if (xx < N - 3 || xx == N - 2) return xx;
        if (xx == N + 2) return N - 1;
        if (xx == N && (N % 4 != 0)) return N - 3;
        if (xx == N - 3 && (N % 4 == 0)) return N - 3;
    });
    return P;
}

Compilation message (stderr)

machine.cpp: In lambda function:
machine.cpp:74:5: warning: control reaches end of non-void function [-Wreturn-type]
   74 |     });
      |     ^

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