Submission #1244660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244660		faruk	Magic Show (APIO24_show)	C++20	0 / 100	2 ms	592 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;

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

    ll x = setN(n) ^ mask;
    
    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);
    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]);
        }
    }
    
	
    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);
    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]] <= 2)
            x += (1LL << cmp);
    }

    x ^= mask;

    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: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 65