oj.uz

Submission #1081370

# Submission time Handle Problem Language Result Execution time Memory
1081370 2024-08-30T02:17:05 Z efishel Magic Show (APIO24_show) C++17
0 / 100
 3 ms 1064 KB 
#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)
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 808 KB Correct.
2 Runtime error 2 ms 1064 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 808 KB Correct.
2 Runtime error 2 ms 1064 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 808 KB Correct.
2 Runtime error 2 ms 1064 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -