Submission #1200880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200880		Nelt	Machine (IOI24_machine)	C++20	100 / 100	19 ms	444 KiB

machine

#include "machine.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;

vector<int> generate_unbalanced_sequence(int n) {
    if (n % 2 != 0) {
        throw invalid_argument("n must be even");
    }
    vector<int> base(n);
    iota(base.begin(), base.end(), 0);

    auto bit_counts = [&](const vector<int>& arr) {
        int maxv = 0;
        for (int x : arr) maxv = max(maxv, x);
        int bits = maxv > 0 ? 32 - __builtin_clz(maxv) : 1;
        vector<int> cnt(bits, 0);
        for (int x : arr) {
            for (int k = 0; k < bits; k++) {
                if (x & (1 << k)) cnt[k]++;
            }
        }
        return cnt;
    };

    auto is_unbalanced = [&](const vector<int>& arr) {
        int half = arr.size() / 2;
        auto cnt = bit_counts(arr);
        for (int c : cnt) {
            if (c == half) return false;
        }
        return true;
    };
    for (int j = n; j <= n + 2; j++) {
        for (int rm = 0; rm < n; rm++) {
            vector<int> A;
            A.reserve(n);
            for (int x : base) if (x != rm) A.push_back(x);
            A.push_back(j);
            if (is_unbalanced(A)) return A;
        }
    }

    throw runtime_error("Failed to generate unbalanced sequence");
}

std::vector<int> find_permutation(int n)
{
    std::vector<int> a(n);
    for (ll i = 0; i < n; i++)
        a[i] = i;
    if (!(n & 1))
        a = generate_unbalanced_sequence(n);
    ll ind[n + 3];
    for (ll i = 0; i < n; i++) ind[a[i]] = i;
    vector<int> b = use_machine(a);
    for (ll bit = 0; bit < 30; bit++)
    {
        ll cnt1 = 0;
        for (ll i = 0; i < n; i++) cnt1 += (a[i] >> bit & 1) - (b[i] >> bit & 1);
        if (cnt1)
            for (ll i = 0; i < n; i++) b[i] ^= (1 << bit);
    }
    for (ll i = 0; i < n; i++) b[i] = ind[b[i]];
    return b;
}

• 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