Submission #1186550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186550		sqrtxsunlight	Magic Show (APIO24_show)	C++17	100 / 100	4 ms	632 KiB

Alice

#include "Alice.h" // Header được cung cấp
#include <vector>
#include <numeric> // Cho std::iota
#include <random>
#include <algorithm> // Cho std::shuffle, std::min/max
#include <cmath>     // Cho std::floor, std::log2
#include <vector>

namespace { // Sử dụng namespace ẩn danh để tránh xung đột tên

const int N_NODES = 5000;
const int BITS_X = 60;
const unsigned long long SEED = 123456789101112ULL; // Sử dụng hạt giống lớn

// Hàm tạo chuỗi bit PRNG 60 bit từ seed
long long generate_prng_sequence(unsigned long long seed) {
    std::mt19937_64 rng(seed);
    // Lấy 64 bit ngẫu nhiên và chỉ giữ lại 60 bit thấp
    return rng() & ((1LL << BITS_X) - 1);
}

// Hàm lấy bit thứ j (0-based) của số X
int get_bit(long long x, int j) {
    return (x >> j) & 1;
}

} // namespace ẩn danh

std::vector<std::pair<int, int>> Alice() {
    long long X = setN(N_NODES);

    long long prng_seq_val = generate_prng_sequence(SEED);
    long long x_prime_val = X ^ prng_seq_val;

    // Khởi tạo PRNG cho việc xáo trộn thứ tự
    std::mt19937_64 shuffle_rng(SEED);
    std::vector<int> indices(N_NODES - 2); // Indices from 3 to N_NODES
    std::iota(indices.begin(), indices.end(), 3);
    std::shuffle(indices.begin(), indices.end(), shuffle_rng);

    std::vector<int> p(N_NODES + 1);
    p[1] = 0; // Gốc không có cha
    p[2] = 1;

    long long stream_ptr = 0;

    // Xác định p[i] theo thứ tự đã xáo trộn
    for (int i : indices) {
        // floor(log2(0)) không xác định, i>=3 nên i-1 >= 2
        int b_i = static_cast<int>(std::floor(std::log2(static_cast<double>(i - 1))));

        if (b_i <= 0) continue; // Không cần lấy bit nếu b_i=0

        long long target_val = 0;
        for (int k = 0; k < b_i; ++k) {
            long long current_stream_pos = stream_ptr + k;
            int bit_idx_in_x_prime = current_stream_pos % BITS_X;
            int bit_val = get_bit(x_prime_val, bit_idx_in_x_prime);
            if (bit_val) {
                target_val |= (1LL << k); // Bit thứ k của target_val
            }
        }
        p[i] = static_cast<int>(target_val + 1);
        stream_ptr += b_i;
    }

    // Tạo danh sách cạnh
    std::vector<std::pair<int, int>> edges;
    edges.reserve(N_NODES - 1);
    for (int i = 2; i <= N_NODES; ++i) {
        // Đảm bảo p[i] hợp lệ (nếu i không có trong shuffled_indices và b_i > 0, cần xử lý)
        // Tuy nhiên, vòng lặp trên đã duyệt qua tất cả i từ 3 đến N_NODES.
        // Chỉ cần đảm bảo p[i] được khởi tạo hoặc tính toán.
         if (p[i] < 1 || p[i] >= i) {
             // Lỗi logic hoặc i=2. p[2] đã được đặt = 1.
             // Nếu p[i] chưa được gán (ví dụ do b_i=0), nó nên được gán giá trị mặc định?
             // Theo logic trên, chỉ p[2] có b_i=0. Mọi p[i] khác (i>=3) có b_i > 0 sẽ được gán.
             // Tuy nhiên, để an toàn, nếu p[i] không hợp lệ, gán nó về 1.
             if (i > 2 && p[i] == 0) p[i] = 1; // Gán mặc định nếu chưa được tính? (Không nên xảy ra)
         }
        edges.push_back({std::min(p[i], i), std::max(p[i], i)});
    }

    return edges;
}

Bob

#include "Bob.h" // Header được cung cấp
#include <vector>
#include <numeric> // Cho std::iota
#include <random>
#include <algorithm> // Cho std::shuffle, std::min/max
#include <cmath>     // Cho std::floor, std::log2
#include <map>
#include <vector>

namespace { // Sử dụng namespace ẩn danh

// Cần định nghĩa lại các hằng số giống Alice
const int N_NODES = 5000;
const int BITS_X = 60;
const unsigned long long SEED = 123456789101112ULL;

// Hàm tạo chuỗi bit PRNG 60 bit từ seed (phải giống hệt Alice)
long long generate_prng_sequence(unsigned long long seed) {
    std::mt19937_64 rng(seed);
    return rng() & ((1LL << BITS_X) - 1);
}

// Hàm lấy bit thứ j (0-based) của số X
int get_bit(long long x, int j) {
    return (x >> j) & 1;
}

} // namespace ẩn danh

long long Bob(std::vector<std::pair<int, int>> V) {
    long long prng_seq_val = generate_prng_sequence(SEED);

    // Khởi tạo PRNG cho việc xáo trộn thứ tự (giống hệt Alice)
    std::mt19937_64 shuffle_rng(SEED);
    std::vector<int> indices(N_NODES - 2); // Indices from 3 to N_NODES
    std::iota(indices.begin(), indices.end(), 3);
    std::shuffle(indices.begin(), indices.end(), shuffle_rng);

    std::map<int, int> known_p;
    for (const auto& edge : V) {
        int u = edge.first;
        int v = edge.second;
        int i = std::max(u, v);
        int p_val = std::min(u, v);
        // Chỉ lưu nếu p_val < i (luôn đúng với cây hợp lệ) và i > 1
        if (p_val > 0 && p_val < i) {
             known_p[i] = p_val;
        }
    }

    std::vector<int> vote0(BITS_X, 0);
    std::vector<int> vote1(BITS_X, 0);
    long long stream_ptr = 0;

    // Bỏ phiếu theo đúng thứ tự Alice đã dùng
    for (int i : indices) {
        int b_i = static_cast<int>(std::floor(std::log2(static_cast<double>(i - 1))));

         if (b_i <= 0) continue;

        // Kiểm tra xem Bob có biết p[i] không
        if (known_p.count(i)) {
            int p_val = known_p[i];
            long long target_val = p_val - 1;

            for (int k = 0; k < b_i; ++k) {
                long long current_stream_pos = stream_ptr + k;
                int bit_idx_in_x_prime = current_stream_pos % BITS_X;
                int bit_val = get_bit(target_val, k); // Lấy bit thứ k của target_val

                if (bit_val == 0) {
                    vote0[bit_idx_in_x_prime]++;
                } else {
                    vote1[bit_idx_in_x_prime]++;
                }
            }
        }
        // Dù biết hay không, stream pointer vẫn phải tăng
        stream_ptr += b_i;
    }

    // Quyết định các bit dựa trên phiếu bầu
    long long recovered_x_prime = 0;
    for (int j = 0; j < BITS_X; ++j) {
        if (vote1[j] > vote0[j]) {
            recovered_x_prime |= (1LL << j);
        }
        // Nếu vote0[j] >= vote1[j], bit là 0 (mặc định)
    }

    // Hoàn tác XOR để lấy X gốc
    long long recovered_X = recovered_x_prime ^ prng_seq_val;

    return recovered_X;
}

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