Submission #1232624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232624		Double_Slash	Broken Device (JOI17_broken_device)	C++20	100 / 100	55 ms	1572 KiB

Anna

#include "Annalib.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void Anna(int N, ll X, int K, int P[]) {
    mt19937 gen;
    uniform_int_distribution<ll> rng(1, (1ll << 60) - 1);
    ll a[N];
    for (ll &ai: a) ai = rng(gen);
    for (int i = K; i--;) a[P[i]] = 0;
    vector<pair<int, ll>> basis;
    for (int i = N; i--;) {
        ll b = 1ll << basis.size();
        for (auto [j, k]: basis) {
            ll x = a[i] ^ a[j];
            if (x >= a[i]) continue;
            a[i] = x;
            b ^= k;
        }
        if (a[i]) basis.emplace_back(i, b);
    }
    ll x = 0;
    for (auto [i, j]: basis) {
        if ((X ^ a[i]) >= X) continue;
        X ^= a[i];
        x ^= j;
    }
    bool ans[N]{};
    for (int j = 60; j--;) {
        if ((x >> j) & 1) ans[basis[j].first] = true;
    }
    for (int i = N; i--;) Set(i, ans[i]);
}

Bruno

#include "Brunolib.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll Bruno(int N, int A[]) {
    mt19937 gen;
    uniform_int_distribution<ll> rng(1, (1ll << 60) - 1);
    ll a[N];
    for (ll &ai: a) ai = rng(gen);
    ll x = 0;
    for (int i = N; i--;) x ^= a[i] * A[i];
    return x;
}

• Subtask 1: 100 / 100