Submission #1203820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203820		Sharky	Magic Show (APIO24_show)	C++20	100 / 100	2 ms	592 KiB

Alice

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

// you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables.
// you had better not use the same global variables in function Alice() and in function Bob().

using ll = long long;

random_device rd;
mt19937 g(rd());

mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());

int rnd(int u, int v) {
    return uniform_int_distribution<int> (u, v) (rng);
}

std::vector<std::pair<int,int>> Alice(){
    vector<pair<int, int>> edge;
    ll x = setN(5000);
    vector<int> tar;
    for (ll i = 59; i >= 0; i--) if (x & (1LL << i)) {
        for (int j = 0; j < 30; j++) tar.push_back(i+1000);
    }
    shuffle(tar.begin(), tar.end(), g);
    int free = 5000 - tar.size();
    for (int i = 2; i <= free; i++) edge.push_back({rnd(max(1, i-999), i-1), i});
    for (auto& x : tar) {
        free++;
        edge.push_back({free-x, free});
    }
    return edge;
}

Bob

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

// you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables.
// you had better not use the same global variables in function Alice() and in function Bob().

long long Bob(std::vector<std::pair<int,int>> V){
    set<int> bt;
    for (auto& [x, y] : V) {
        if (abs(x - y) < 1000) continue;
        bt.insert(abs(x - y) - 1000);
    }
    long long res = 0;
    for (auto x : bt) res += (1LL << x);
    return res;
}

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