#include <vector>
#include <random>
#include "Alice.h"
#include <cstdlib>
namespace {
using u64 = unsigned long long;
u64 coeff[5001];
void init() {
std::mt19937 gen(8686);
std::uniform_int_distribution<> dis(1, 2);
for (int i = 0; i < 5001; ++i)
for (long long j = 0; j < 60; ++j)
coeff[i] ^= (dis(gen) & 1ll) << j;
}
};
std::vector<std::pair<int,int>> Alice(){
init();
long long x = setN(5000);
int i, ans;
std::vector<std::pair<int, int > > T = { {1, 2} };
for (i = 3; i <= 5000; ++i) {
ans = 0;
for (u64 j = 0; j < 60; ++j)
ans ^= ((coeff[i] >> j) & 1) * ((x >> j) & 1);
T.emplace_back(i, 1 + ans);
}
return T;
}
#include <vector>
#include <cstdlib>
#include <algorithm>
#include "Bob.h"
#include <cstring>
#include <random>
namespace {
using u64 = unsigned long long;
u64 coeff[5001];
void init() {
std::mt19937 gen(8686);
std::uniform_int_distribution<> dis(1, 2);
for (int i = 0; i < 5001; ++i)
for (long long j = 0; j < 60; ++j)
coeff[i] ^= (dis(gen) & 1ll) << j;
}
};
long long Bob(std::vector<std::pair<int,int>> T) {
long long x;
int pivot[60] = { 0 };
int ans[5001] = { 0 };
int used[5001] = { 0 };
memset(ans, -1, sizeof ans);
memset(used, 0, sizeof used);
for (auto [u, v] : T) {
if (u > v)
std::swap(u, v);
if (v <= 2)
continue;
ans[v] = u - 1;
}
init();
for (int j = 59; j >= 0; --j) {
int piv = -1;
for (int i = 3; piv == -1 && i <= 5000; ++i)
if (ans[i] != -1 && !used[i] && ((coeff[i] >> j) & 1)) {
used[i] = 1;
piv = i;
}
assert(piv + 1);
for (int i = 3; i <= 5000; ++i) {
if (ans[i] == -1 || i == piv || 0 == ((coeff[i] >> j) & 1))
continue;
ans[i] ^= ans[piv];
coeff[i] ^= coeff[piv];
}
pivot[j] = piv;
}
x = 0;
for (long long j = 0; j < 60; ++j)
x ^= ans[pivot[j]] << j;
return x;
}
Compilation message
Bob.cpp: In function 'long long int Bob(std::vector<std::pair<int, int> >)':
Bob.cpp:47:9: error: 'assert' was not declared in this scope
47 | assert(piv + 1);
| ^~~~~~
Bob.cpp:7:1: note: 'assert' is defined in header '<cassert>'; did you forget to '#include <cassert>'?
6 | #include <random>
+++ |+#include <cassert>
7 |
