Submission #1186678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186678		Thanhs	Magic Show (APIO24_show)	C++20	100 / 100	616 ms	1960 KiB

Alice

#include "Alice.h"
#include <bits/stdc++.h>
using namespace std;

#define name "TENBAI"
#define fi first
#define se second
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define all(x) x.begin(), x.end()

const int L = 60;
const int n = 500;

int f(int x, int y)
{
    if (x > y)
        swap(x, y);
    mt19937 hdp(x * (n + 1) + y);
    return hdp() % L;
}

int p[n + 5];
vector<pair<int, int>> v[L];

int find(int u) {return p[u] < 0 ? u : p[u] = find(p[u]);}
void join(int u, int v)
{
    u = find(u), v = find(v);
    if (u == v)
        return;
    if (p[u] > p[v])
        swap(u, v);
    p[u] += p[v];
    p[v] = u;
}

vector<pair<int, int>> Alice()
{
    memset(p, -1, sizeof p);
    long long x = setN(n);
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            if (i != j)
                v[f(i, j)].push_back({i, j});
    vector<int> b;
    while (x)
        b.push_back(__lg(x)), x ^= 1ll << __lg(x);
    vector<pair<int, int>> res;
    int cr = 0;
    while (res.size() < n - 1)
    {
        while (v[b[cr]].empty())
            cr = (cr + 1) % b.size();
        while (find(v[b[cr]].back().fi) == find(v[b[cr]].back().se))
            v[b[cr]].pop_back();
        if (v[b[cr]].size())
        {
            res.push_back(v[b[cr]].back());
            join(v[b[cr]].back().fi, v[b[cr]].back().se);
        }
        cr = (cr + 1) % b.size();
    }
    return res;
}

Bob

#include "Bob.h"
#include <bits/stdc++.h>
using namespace std;

#define name "TENBAI"
#define fi first
#define se second
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define all(x) x.begin(), x.end()

const int L = 60;
const int n = 500;

int f(int x, int y)
{
    if (x > y)
        swap(x, y);
    mt19937 hdp(x * (n + 1) + y);
    return hdp() % L;
}

long long Bob(vector<pair<int, int>> v)
{
    long long res = 0;
    for (auto t : v)
        res |= 1ll << f(t.fi, t.se);
    return res;
}

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