Submission #1186698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186698		sqrtxsunlight	Magic Show (APIO24_show)	C++17	100 / 100	2 ms	376 KiB

Alice

// Alice.cpp
#include "Alice.h"
#include <algorithm>    // <— thêm dòng này
#include <vector>
#include <random>
#include <cmath>
using namespace std;

static const int N = 5000;
static const unsigned long long SEED = 123456789101112ULL;
static const int BITS_X = 60;

vector<pair<int,int>> Alice() {
    int n = N;
    long long X = setN(n);

    // PRNG để làm trắng
    mt19937_64 prng_whiten(SEED);
    unsigned long long prng_seq = prng_whiten() & ((1ULL<<BITS_X) - 1);

    unsigned long long Xp = ((unsigned long long)X) ^ prng_seq;

    // Tạo thứ tự ngẫu nhiên
    mt19937_64 prng_shuffle(SEED);
    vector<int> indices;
    indices.reserve(n-2);
    for(int i = 3; i <= n; i++) indices.push_back(i);
    std::shuffle(indices.begin(), indices.end(), prng_shuffle);

    // Xây dựng cây
    vector<int> p(n+1);
    p[1] = 0;
    p[2] = 1;
    unsigned long long stream_ptr = 0;

    for(int i : indices) {
        int bi = (i>2 ? (int)floor(log2(i-1)) : 0);
        if(bi > 0) {
            unsigned long long target_val = 0;
            for(int k = 0; k < bi; k++) {
                int bit = (Xp >> ((stream_ptr + k) % BITS_X)) & 1ULL;
                target_val |= (bit << k);
            }
            p[i] = (int)target_val + 1;
            stream_ptr += bi;
        } else {
            p[i] = 1;
        }
    }

    vector<pair<int,int>> edges;
    edges.reserve(n-1);
    for(int i = 2; i <= n; i++) {
        int u = min(p[i], i), v = max(p[i], i);
        edges.emplace_back(u, v);
    }
    return edges;
}

Bob

// Bob.cpp
#include "Bob.h"
#include <vector>
#include <random>
#include <cmath>
#include <algorithm>
using namespace std;

static const int N = 5000;
static const unsigned long long SEED = 123456789101112ULL;
static const int BITS_X = 60;

long long Bob(vector<pair<int,int>> V) {
    int n = N;
    // Bước 1: Khôi phục các p[i] còn biết
    vector<int> known_p(n+1, 0);
    for(auto &e : V) {
        int u = e.first, v = e.second;
        int i = max(u, v), par = min(u, v);
        known_p[i] = par;
    }

    // Tạo PRNG để làm trắng (giống Alice)
    mt19937_64 prng_whiten(SEED);
    unsigned long long prng_seq = prng_whiten();
    prng_seq &= ((1ULL<<BITS_X) - 1);

    // Bước 2: Tạo thứ tự xử lý ngẫu nhiên (giống Alice)
    mt19937_64 prng_shuffle(SEED);
    vector<int> indices;
    indices.reserve(n-2);
    for(int i = 3; i <= n; i++) indices.push_back(i);
    shuffle(indices.begin(), indices.end(), prng_shuffle);

    // Bỏ phiếu
    vector<int> vote0(BITS_X, 0), vote1(BITS_X, 0);
    unsigned long long stream_ptr = 0;
    for(int i : indices) {
        int bi = (i>2 ? (int)floor(log2(i-1)) : 0);
        if(bi > 0) {
            int pval = known_p[i];
            if(pval != 0) {
                unsigned long long target_val = (unsigned long long)(pval - 1);
                for(int k = 0; k < bi; k++) {
                    int bit = (int)((target_val >> k) & 1ULL);
                    int bit_idx = (stream_ptr + k) % BITS_X;
                    if(bit) vote1[bit_idx]++;
                    else    vote0[bit_idx]++;
                }
            }
            stream_ptr += bi;
        }
    }

    // Bước 3: Khôi phục X'
    unsigned long long rec_xp = 0;
    for(int j = 0; j < BITS_X; j++) {
        if(vote1[j] > vote0[j]) {
            rec_xp |= (1ULL << j);
        }
    }

    // Bước 4: Hoàn tác làm trắng
    unsigned long long rec_x = rec_xp ^ prng_seq;
    return (long long)rec_x;
}

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