#include <random>
#include <vector>
#include "Alice.h"
// you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables.
// you had better not use the same global variables in function Alice() and in function Bob().
std::vector<std::pair<int,int>> Alice(){
std::mt19937_64 rng(123);
#define uid(a, b) std::uniform_int_distribution<long long>(a, b)(rng)
// add your code here
// change below into your code
long long x = setN(5000);
// the number has 60 bits
// for each we will generate a
std::vector<std::pair<int, int>> edges;
edges.emplace_back(1, 2);
for (int i = 3; i <= 5000; i++) {
long long coeff = uid(0, (1LL << 60) - 1);
long long mul = coeff & x;
int answer = __builtin_popcountll(mul) & 1;
answer++;
edges.emplace_back(answer, i);
}
return edges;
}
#include <cassert>
#include <random>
#include <set>
#include <utility>
#include <vector>
#include "Bob.h"
// you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables.
// you had better not use the same global variables in function Alice() and in function Bob().
long long Bob(std::vector<std::pair<int,int>> V){
std::mt19937_64 rng(123);
#define uid(a, b) std::uniform_int_distribution<long long>(a, b)(rng)
for (auto& [u, v] : V) {
if (u > v) std::swap(u, v);
}
std::set<std::pair<int, int>> mp(V.begin(), V.end());
std::vector<long long> eqs;
for (int i = 3; i <= 5000; i++) {
long long coeff = uid(0, (1LL << 60) - 1);
bool has1 = mp.find({1, i}) != mp.end();
bool has2 = mp.find({2, i}) != mp.end();
if (!has1 && !has2) {
// removed edge
continue;
}
if (has1) {
eqs.push_back(coeff);
} else {
eqs.push_back(coeff ^ (1LL << 60));
}
}
// we have all the equations now
int neq = eqs.size();
for (int j = 0; j < 60; j++) {
for (int i = j; i < neq; i++) {
if (eqs[i] >> j & 1) {
std::swap(eqs[i], eqs[j]);
break;
}
}
assert(eqs[j] >> j & 1); // this should be good
for (int i = j + 1; i < neq; i++) {
if (eqs[i] >> j & 1) {
eqs[i] ^= eqs[j];
}
}
}
// now that everything's done
long long answer = 0;
for (int i = 59; i >= 0; i--) {
long long v = eqs[i] >> 60 & 1;
answer ^= v << i;
if (v) {
for (int j = i - 1; j >= 0; j--) {
if (eqs[j] >> i & 1) {
eqs[j] ^= 1LL << 60;
}
}
}
}
return answer;
}
