Submission #1186697

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186697		sqrtxsunlight	Magic Show (APIO24_show)	C++17	Compilation error	0 ms	0 KiB

Alice

// Alice.cpp
#include "Alice.h"
#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() {
    // Bước 1: Chọn n và nhận X
    int n = N;
    long long X = setN(n);

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

    // Xóa trắng X
    unsigned long long Xp = ((unsigned long long)X) ^ prng_seq;

    // Bước 2: Tạo thứ tự xử lý 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);
    shuffle(indices.begin(), indices.end(), prng_shuffle);

    // Bước 3: 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) {
            // Lấy bi bit từ S' (Xp lặp lại)
            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; // với bi=0, mặc định đặt cha là 1
        }
    }

    // Bước 4: Gom các cạnh
    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>
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;
}

Compilation message (stderr)

# 1번째 컴파일 단계

Alice.cpp: In function 'std::vector<std::pair<int, int> > Alice()':
Alice.cpp:30:5: error: 'shuffle' was not declared in this scope
   30 |     shuffle(indices.begin(), indices.end(), prng_shuffle);
      |     ^~~~~~~