Submission #1178009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178009		trashaccount	Magic Show (APIO24_show)	C++20	100 / 100	256 ms	62228 KiB

Alice

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

#define ll long long
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
#define isz(a) (int)(a).size()

const int NM = 5000;
const ll LIM = 1e18;

vector <int> arr_Alice[NM+5];
bool chk_Alice = 0;

mt19937 rng_Alice(69420);

vector <pii> Alice(){
    ll X = setN(NM);

    if (!chk_Alice){
        for (int i = 2; i <= NM; i++){
            arr_Alice[i].clear();
            for (int j = 0; j < i-1; j++) arr_Alice[i].push_back(j+1);
            shuffle(arr_Alice[i].begin(), arr_Alice[i].end(), rng_Alice);
        }
        chk_Alice = 1;
    }

    vector <pii> res = {};
    for (int i = 2; i <= NM; i++){
        res.push_back(mp(arr_Alice[i][X%(i-1)], i));
    }
    sort(res.begin(), res.end());
    return res;
}

Bob

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

#define ll long long
#define i128 __int128
#define pii pair <int, int>
#define pll pair <ll, ll>
#define fi first
#define se second
#define mp make_pair
#define isz(a) (int)(a).size()

const int NM = 5000;
const ll LIM = 1e18;

vector <int> arr_Bob[NM+5];
bool chk_Bob = 0;
vector <pii> info;
int K, r[NM+5], m[NM+5], f[NM+5], cur[NM+5];

mt19937 rng_Bob(69420);

i128 extgcd(i128 a, i128 b, i128 &x, i128 &y){
    if (b == 0){
        x = 1;
        y = 0;
        return a;
    }
    i128 x0, y0;
    i128 g = extgcd(b, a%b, x0, y0);
    x = y0;
    y = x0-a/b*y0;
    return g;
}

ll Bob(vector <pii> E){
    if (!chk_Bob){
        for (int i = 2; i <= NM; i++){
            arr_Bob[i].clear();
            for (int j = 0; j < i-1; j++) arr_Bob[i].push_back(j+1);
            shuffle(arr_Bob[i].begin(), arr_Bob[i].end(), rng_Bob);
        }
        chk_Bob = 1;
    }

    K = 0;
    for (pii p : E){
        K++;
        m[K] = p.se-1;
        r[K] = 0;
        while (arr_Bob[p.se][r[K]] != p.fi) r[K]++;
    }
    for (int i = 2; i <= NM; i++)
        for (int j = i; j <= NM; j += i)
            if (f[j] == 0) f[j] = i;

    for (int i = 2; i <= NM; i++) cur[i] = -1;

    vector <int> arr;
    for (int i = 1; i <= K; i++){
        if (m[i] == 1) continue;
        arr.clear();
        int val = m[i];
        while (val > 1){
            if (arr.empty() || arr.back()%f[val] != 0) arr.push_back(f[val]);
            else arr.back() *= f[val];

            val /= f[val];
        }
        for (int y : arr) cur[y] = r[i]%y;
    }
    for (int i = 2; i <= NM; i++){
        if (cur[i] == -1) continue;
        bool chk = 0;
        for (int j = i*2; j <= NM; j += i)
            if (cur[j] != -1){
                chk = 1;
                break;
            }
        if (chk) cur[i] = -1;
    }
    vector <pll> T;
    for (int i = 2; i <= NM; i++)
        if (cur[i] != -1) T.push_back(mp(cur[i], i));

    i128 a1 = T[0].fi, m1 = T[0].se;
    for (int i = 1; i < isz(T); i++){
        i128 a2 = T[i].fi, m2 = T[i].se;

        i128 n1, n2, g = extgcd(m1, m2, n1, n2);

        i128 res = (a1*n2*m2+a2*n1*m1)%(m1*m2);
        if (res < 0) res += m1*m2;
        a1 = res; m1 *= m2;

        if (a1+m1 > LIM) break;
    }
    return (ll)a1;
}

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