Submission #1244672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244672		faruk	마술쇼 (APIO24_show)	C++20	5 / 100	2 ms	380 KiB

Alice

#include <bits/stdc++.h>
#include "Alice.h"

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;



// 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().

std::vector<std::pair<int,int>> Alice(){
    const int num_cmps = 25;
    int n = 5000;
    const int mega_root = 3541;
	// add your code here
    int cmp_size = (n - 1) / num_cmps;
    //n = cmp_size * num_cmps + 1;

    vector<pii> out;

    /*mt19937_64 rand(53);
    ll mask = rand() % (1LL << num_cmps);

    ll x = setN(n) ^ mask;
    
    
    vector<int> all_nodes(n);
    iota(all_nodes.begin(), all_nodes.end(), 1);
    all_nodes.erase(all_nodes.begin() + mega_root - 1);
    shuffle(all_nodes.begin(), all_nodes.end(), rand);
    for (int cmp = 0; cmp < num_cmps; cmp++) {
        //cout << all_nodes[cmp * cmp_size] << "\n";
        out.emplace_back(all_nodes[cmp * cmp_size], mega_root);
        if ((1LL << cmp) & x) {
            for (int i = 1; i < cmp_size; i++)
                out.emplace_back(all_nodes[cmp * cmp_size + i], all_nodes[cmp * cmp_size + i - 1]);
        } else {
            for (int i = 1; i < cmp_size; i++)
                out.emplace_back(all_nodes[cmp * cmp_size + i], all_nodes[cmp * cmp_size]);
        }
    }*/

    ll x = setN(n);
    for (int i = 1; i <= n; i++) {
        if (i != x)
            out.emplace_back(i, x);
    }
	
    return out;
}

Bob

#include <bits/stdc++.h>
#include "Bob.h"

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int num_cmps = 25;
int n = 5000;
const int mega_root = 3541;

// 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){
	// add your code here
    /*int cmp_size = (n - 1) / num_cmps;
    n = cmp_size * num_cmps + 1;

    mt19937_64 rand(53);
    ll mask = rand() % (1LL << num_cmps);

    ll x = 0;
    
    vector<pii> out;
    vector<int> all_nodes(n);
    iota(all_nodes.begin(), all_nodes.end(), 1);
    all_nodes.erase(all_nodes.begin() + mega_root - 1);
    shuffle(all_nodes.begin(), all_nodes.end(), rand);
    vector<int> what_cmp(n);*/
    int n = 5000;
    vector<int> deg(n + 1);
    for (auto [x, y] : V) {
        deg[x]++;
        deg[y]++;
    }
    /*for (int cmp = 0; cmp < num_cmps; cmp++)
    {
        if (deg[all_nodes[cmp * cmp_size]] == 1 || deg[all_nodes[cmp * cmp_size]] == 2)
            x += (1LL << cmp);
    }

    x ^= mask;*/
    int x = max_element(deg.begin(), deg.end()) - deg.begin();

    return x;
}
/*
3428
4837
3077
897
3562
4043
1443
1582
2142
572
281
4127
1550
2518
4156
2166
3251
118
4957
1408
1892
554
1734
3734
661
4976
*/

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