Submission #1081370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081370		efishel	Magic Show (APIO24_show)	C++17	0 / 100	3 ms	1064 KiB

Alice

#include "Alice.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using ii = pair <int, int>;
using vii = vector <ii>;

const ll BITS = 60, MAXN = ll(1)<<BITS, EQS = 4998;
mt19937_64 rngA(10);

vii Alice () {
    vii ans;
    ll x = setN(2+EQS);
    ans.push_back({ 1, 2 });
    uniform_int_distribution distr(ll(1), MAXN-1);
    for (ll i = 3; i <= 2+EQS; i++) {
        ll th = distr(rngA);
        ll opans = __builtin_parityll(th & x);
        ans.push_back({ i, opans+1 });
    }
    return ans;
}

// (ans)(x_59)(x_58)...(x_0)

Bob

#include "Bob.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using ii = pair <int, int>;
using vii = vector <ii>;

const ll BITS = 60, MAXN = ll(1)<<BITS, EQS = 4998;
mt19937_64 rngB(10);

ll Bob (vii vin) {
    vll eqs(EQS, 0);
    vector <char> seen(EQS, false);
    for (auto [u, v] : vin) {
        if (u > v) swap(u, v);
        if (v == 2) continue;
        assert(u == 1 || u == 2);
        eqs[v-3] |= ll(u-1)<<BITS;
        seen[v-3] = true;
    }
    uniform_int_distribution distr(1LL, MAXN-1);
    for (ll i = 0; i < EQS; i++) {
        ll th = distr(rngB);
        if (seen[i]) eqs[i] |= th;
    }
    vll bx(BITS, -15);
    vll ixs;
    vector <char> used(EQS, false);
    for (ll bit = 0; bit < BITS; bit++) {
        ll j = 0;
        while ((j < EQS && !(eqs[j]>>bit&1)) || used[j]) j++;
        assert(j < EQS);
        assert(!used[j]);
        for (ll i = 0; i < EQS; i++)
            if (eqs[i] == eqs[j]) used[i] = true;
        ixs.push_back(j);
        for (ll &eq : eqs)
            if (eq>>bit&1 && eq != eqs[j]) eq ^= eqs[j];
    }
    for (ll ibit = BITS-1; ibit >= 0; ibit--) {
        bx[ibit] = eqs[ixs[ibit]]>>BITS;
    }
    ll x = 0;
    for (ll bit = 0; bit < BITS; bit++) x |= bx[bit]<<bit;
    return x;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 65