Submission #1188133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188133		Muaath_5	Magic Show (APIO24_show)	C++17	35 / 100	4 ms	636 KiB

Alice

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#include "Alice.h"

#ifndef MUDF
#define MUDF
const int SEED = 717171, CNT = 83, BIT = 60;

int vals[BIT][CNT];
mt19937 rng(SEED);
void build_ls() {
    vector<int> ls;
    for (int i = 3; i <= CNT*BIT+2; i++) {
        ls.push_back(i);
    }
    shuffle(ls.begin(), ls.end(), rng);
    int idx = 0;
    for (int i = 0; i < BIT; i++) {
        for (int j = 0; j < CNT; j++) {
            vals[i][j] = ls[idx];
            idx++;
        }
    }
}
#endif
// 0: 11, 318, 97, 4447, 54, 62, 12
// 1:
// 2:  

// 0: 
// 1: 

vector<pii> Alice() {
    build_ls();
    ll x = setN(CNT*BIT+2);
    vector<pii> res = {{1, 2}};
    for (ll i = 0; i < BIT; i++) {
        if ((x>>i)&1ll) {
            for (int j : vals[i])
                res.push_back({2, j});
        } else {
            for (int j : vals[i])
                res.push_back({1, j});
        }
    }

    return res;
}

Bob

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#include "Bob.h"

const int SEED = 717171, CNT = 83, BIT = 60;

ll Bob(vector<pii> adj) {
    mt19937 rng(SEED);
	int vals[BIT][CNT] = {};
    vector<int> ls;
    for (int i = 3; i <= CNT*BIT+2; i++) {
        ls.push_back(i);
    }
    shuffle(ls.begin(), ls.end(), rng);
    int idx = 0;
    for (int i = 0; i < BIT; i++) {
        for (int j = 0; j < CNT; j++) {
            vals[i][j] = ls[idx];
            idx++;
        }
    }

    map<int, int> mp;
    for (int i = 0; i < BIT; i++) {
        for (int j : vals[i]) {
            mp[j] = i;
        }
    }
    const ll ONES = (1ll << BIT) - 1;
    ll x = 0, y = 0;
    for (auto [u, v] : adj) {
        if (u == 1 && v == 2) continue;
        if (!mp.count(v)) continue;
        if (u == 2) {
            x |= (1ll << mp[v]);
        } else if (u == 1) {
            y |= (1ll << mp[v]);
        }
    }
    // cerr << bitset<BIT>(x) << endl;
    // cerr << bitset<BIT>(y) << endl;
    // cerr << x << ' ' << ((~y) & ONES) << endl;
    return (x|((~y) & ONES));
}

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