// 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.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;
}
