제출 #1040090

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1040090		_8_8_	마술쇼 (APIO24_show)	C++17	100 / 100	428 ms	132380 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 = i+1; j <= N; j++) {
            ll t = (i + j) % 60;
            if((x >> t) & 1) {
                vec.push_back({i,j});
            }
        }
    }
    shuffle(vec.begin(),vec.end(),rng);
    vector<pair<int,int>> ans;
    for(auto [x,y]:vec) {
        if((int)ans.size() == 4999) break;
        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 |= (1ll << ((x + y) % 60));
    }
    return X;
}

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