#include "Alice.h"
#include <random>
#include <vector>
std::vector<std::pair<int, int>> Alice() {
const int seed = 69;
const int n = 5000;
long long x = setN(n);
std::mt19937 rng(seed);
std::uniform_int_distribution<int> dist(0, 2);
std::vector<std::pair<int, int>> ans = {{1, 2}};
for (int i = 0; i < n - 2; ++i) {
int sum = 0;
for (int j = 0; j < 60; ++j) {
sum += !!(x & (1LL << j)) * dist(rng);
}
ans.push_back({!(sum & 1) + 1, i + 3});
}
return ans;
}
#include "Bob.h"
#include <bitset>
#include <random>
#include <vector>
void gauss(std::vector<std::bitset<61>> a, int n, int m,
std::vector<bool> &ans) {
std::vector<int> where(m, -1);
for (int col = 0, row = 0; col < m && row < n; ++col) {
for (int i = row; i < n; ++i)
if (a[i][col]) {
swap(a[i], a[row]);
break;
}
if (!a[row][col])
continue;
where[col] = row;
for (int i = 0; i < n; ++i)
if (i != row && a[i][col])
a[i] ^= a[row];
++row;
}
for (int j = 0; j < m; ++j) {
if (where[j] != -1) {
ans[j] = a[where[j]][m];
}
}
}
long long Bob(std::vector<std::pair<int, int>> V) {
const int seed = 69;
const int n = 5000;
std::mt19937 rng(seed);
std::uniform_int_distribution<int> dist(0, 2);
std::vector<std::bitset<61>> a(n - 2);
for (int i = 0; i < n - 2; ++i) {
for (int j = 0; j < 60; ++j) {
a[i][j] = dist(rng);
}
}
std::vector<bool> good(n - 2);
for (auto &[u, v] : V) {
a[v - 3][60] = u % 2;
good[v - 3] = true;
}
for (int i = 0; i < n - 2; ++i) {
if (!good[i]) {
for (int j = 0; j < 60; ++j) {
a[i][j] = 0;
}
}
}
std::vector<bool> ans(60);
gauss(a, n - 2, 60, ans);
long long x = 0;
for (int bt = 0; bt < 60; ++bt) {
x += ans[bt] * (1LL << bt);
}
return x;
}
