Submission #1220306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220306		The_Samurai	Broken Device (JOI17_broken_device)	C++20	0 / 100	12 ms	1344 KiB

Anna

#include "Annalib.h"
#include "bits/stdc++.h"
using namespace std;

void Anna(int n, long long x, int k, int P[] ){
    mt19937 rng(12142532);
    auto rand = [&](int l, int r) -> int {
        int x = rng();
        return abs(x) % (r - l + 1) + l;
    };

    assert(n == 150);
    vector<int> ord(n), val(n, 1);
    for (int i = 0; i < n; i++) ord[i] = i;
    // for (int i = 0; i < n; i++) swap(ord[i], ord[rand(0, i)]);
    ord = {84, 141, 40, 3, 51, 112, 144, 118, 70, 55, 94, 121, 78, 36, 4, 57, 138, 30, 91, 11, 46, 52, 92, 6, 44, 69, 25, 39, 142, 123, 125, 32, 143, 129, 56, 96, 93, 5, 49, 42, 128, 63, 22, 90, 134, 18, 110, 34, 87, 80, 71, 102, 133, 104, 120, 26, 53, 12, 61, 136, 106, 59, 147, 148, 67, 111, 20, 0, 119, 83, 139, 99, 140, 127, 16, 130, 82, 47, 135, 8, 75, 149, 88, 101, 33, 14, 28, 146, 145, 68, 79, 64, 117, 35, 15, 48, 1, 86, 66, 115, 2, 95, 113, 109, 100, 19, 97, 7, 137, 60, 116, 105, 45, 54, 74, 107, 10, 37, 122, 81, 85, 24, 23, 43, 76, 29, 17, 124, 38, 132, 72, 114, 41, 65, 50, 9, 27, 13, 21, 131, 98, 126, 77, 89, 103, 31, 108, 58, 73, 62};
    // for (int i = 0; i < n; i++) cout << ord[i] << ' ';
    // cout << endl;
    for (int i = 0; i < k; i++) val[P[i]] = 0;

    auto check = [&](long long x) -> bool {
        vector<int> vec(62);
        for (int i = 0; i <= 60; i++) vec[i] = x >> i & 1ll;
        // for (int i = 0; i < vec.size(); i++) cout << vec[i] << ' ';
        // cout << endl;
        int i = 0, j = 0;
        for (; i < n and j < 62; ) {
            if (!val[i]) {
                i++;
                continue;
            }
            if (i + 2 >= n) break;
            if (!val[i + 1] and vec[j]) {
                i++;
                continue;
            }
            if (!val[i + 2] and vec[j + 1]) {
                i++;
                continue;
            }
            i += 3;
            j += 2;
        }
        if (j < 62) return false;
        i = 0, j = 0;
        for (; i < n and j < 62; ) {
            if (!val[i]) {
                Set(ord[i], 0);
                i++;
                continue;
            }
            if (i + 2 >= n) break;
            if (!val[i + 1] and vec[j]) {
                Set(ord[i], 0);
                i++;
                continue;
            }
            if (!val[i + 2] and vec[j + 1]) {
                Set(ord[i], 0);
                i++;
                continue;
            }
            Set(ord[i], 1);
            Set(ord[i + 1], vec[j]);
            Set(ord[i + 2], vec[j + 1]);
            i += 3;
            j += 2;
        }
        for (; i < n; i++) Set(ord[i], 0);
        return true;
    };
    if (check(x)) return;
    const long long N = ((1ll << 61) - 1);
    if (check(x ^ N)) return;
    for (int i = 0; i < n; i++) Set(i, 0);
}

Bruno

#include "Brunolib.h"
#include "bits/stdc++.h"
using namespace std;


long long Bruno( int n, int a[] ){
    mt19937 rng(12142532);
    auto rand = [&](int l, int r) -> int {
        int x = rng();
        return abs(x) % (r - l + 1) + l;
    };

    vector<int> ord(n);
    for (int i = 0; i < n; i++) ord[i] = i;
    // for (int i = 0; i < n; i++) swap(ord[i], ord[rand(0, i)]);
    ord = {84, 141, 40, 3, 51, 112, 144, 118, 70, 55, 94, 121, 78, 36, 4, 57, 138, 30, 91, 11, 46, 52, 92, 6, 44, 69, 25, 39, 142, 123, 125, 32, 143, 129, 56, 96, 93, 5, 49, 42, 128, 63, 22, 90, 134, 18, 110, 34, 87, 80, 71, 102, 133, 104, 120, 26, 53, 12, 61, 136, 106, 59, 147, 148, 67, 111, 20, 0, 119, 83, 139, 99, 140, 127, 16, 130, 82, 47, 135, 8, 75, 149, 88, 101, 33, 14, 28, 146, 145, 68, 79, 64, 117, 35, 15, 48, 1, 86, 66, 115, 2, 95, 113, 109, 100, 19, 97, 7, 137, 60, 116, 105, 45, 54, 74, 107, 10, 37, 122, 81, 85, 24, 23, 43, 76, 29, 17, 124, 38, 132, 72, 114, 41, 65, 50, 9, 27, 13, 21, 131, 98, 126, 77, 89, 103, 31, 108, 58, 73, 62};

    long long ans = 0;
    int i = 0;
    for (int j = 0; j < n; ) {
        if (!a[ord[j]]) {
            j++;
            continue;
        }
        ans += (1ll << i) * a[ord[j + 1]];
        ans += (1ll << (i + 1)) * a[ord[j + 2]];
        i += 2;
        j += 3;
    }
    // const long long N = (1ll << 61) - 1;
    // if (ans >> 60 & 1) ans ^= N;
    return ans;
}

• Subtask 1: 0 / 100