Submission #1127783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127783		totoro	Machine (IOI24_machine)	C++20	10 / 100	5 ms	428 KiB

machine

#include "machine.h"

#include <cassert>

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 - 2; i++)
        A[i] = i;

    A[N - 2] = N - (N % 4) / 2;
    A[N - 1] = N + 2;

    std::vector<int> ans = use_machine(A);
    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 - (N % 4 == 0)) ok = false;
        }
        if (ok) break;
    }
    std::vector<int> P(N);
    std::transform(ans.begin(), ans.end(), P.begin(), [X, N](int x) {
        int xx = x ^ X;
        if (xx < N - 2) return xx;
        if (xx == N - (N % 4) / 2) return N - 2;
        if (xx == N + 2) return N - 1;
    });
    return P;
}

Compilation message (stderr)

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

• 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