Submission #1040080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040080		_8_8_	Magic Show (APIO24_show)	C++17	0 / 100	94 ms	35212 KiB

Alice

#include <bits/stdc++.h>
#include "Alice.h"
using namespace std;
typedef long long ll;
vector<pair<int,int>> vec;
const int N = 5e3;
int p[N + 12];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int get(int v) {
    if(p[v] == v) return v;
    return p[v] = get(p[v]);
}
bool merge(int x,int y) {
    x = get(x);
    y = get(y);
    if(x == y) return false;
    p[x] = y;
    return 1;
}
vector<pair<int,int>> Alice(){
    long long x = setN(5000);
    iota(p+1,p+N+1,1);
    for(int i = 1;i <= N;i++) {
        for(int j = 1; j <= N; j++) {
            if((x >> ((i + j)%60)) & 1) {
                vec.push_back({i,j});
            }
        }
    }
    shuffle(vec.begin(),vec.end(),rng);
    vector<pair<int,int>> ans;
    for(auto [x,y]:vec) {
        if(merge(x,y)) {
            ans.push_back({x,y});
        }
    }
    return ans;
}

Bob

#include <vector>
#include "Bob.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long Bob(std::vector<std::pair<int,int>> V){
    ll X = 0;
    for(auto [x,y]:V) {
        X |= ((x + y) % 60);
    }
    return X;
}

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