#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;
}
#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;
}
