#include <bits/stdc++.h>
#include "Alice.h"
using namespace std;
int n = 5000, cnt_trans = 0, lgn = 61;
long long Rand (int l, int r)
{
unsigned long long x = (rand () << 15) ^ rand ();
return x % (r - l + 1) + l;
}
int log2 (int i)
{
int ans = 0;
while (i) i /= 2, ans ++;
return (-- ans);
}
vector <pair <int, int>> Alice()
{
srand (24022007);
long long pbml = 0;
for (int i = 0; i < lgn - 1; i ++)
pbml ^= (Rand (0, 1) << i);
cerr << pbml << '\n';
vector <pair <int, int>> tree_trans;
for (int i = 1; i <= n; i ++)
cnt_trans += log2 (i - 1);
long long x = setN (n);
x ^= pbml;
long long bit61 = 0;
for (int i = 0; i < lgn - 1; i ++)
bit61 ^= ((x & (1LL << i)) > 0);
x ^= (bit61 << 61);
vector <int> arr (cnt_trans, 0);
for (int i = 0; i < cnt_trans; i ++)
arr[i] = i % lgn;
for (int i = 0; i < cnt_trans; i ++)
swap (arr[i], arr[Rand (0, i)]);
string trans;
int cur_pos = 0;
for (int i = 2; i <= n; i ++)
{
int lg = floor (log2 (i - 1)), p = 0;
for (int j = 0; j < lg; j ++)
p += (((x & (1LL << arr[cur_pos ++])) > 0) << j);
p ++;
tree_trans.push_back (make_pair (p, i));
}
return tree_trans;
}
#include <bits/stdc++.h>
#include "Bob.h"
using namespace std;
#ifndef PBML
int n = 5000, cnt_trans = 0, lgn = 61;
long long Rand (int l, int r)
{
unsigned long long x = (rand () << 15) ^ rand ();
return x % (r - l + 1) + l;
}
int log2 (int i)
{
int ans = 0;
while (i) i /= 2, ans ++;
return (-- ans);
}
#endif // PBML
long long Bob (vector <pair <int, int>> tree)
{
srand (24022007);
long long pbml = 0;
for (int i = 0; i < lgn - 1; i ++)
pbml ^= (Rand (0, 1) << i);
cerr << pbml << '\n';
for (int i = 1; i <= n; i ++)
cnt_trans += log2 (i);
vector <int> par (n + 1, -1);
for (auto i: tree) par[i.second] = i.first;
vector <int> arr (cnt_trans, 0);
for (int i = 0; i < cnt_trans; i ++)
arr[i] = i % lgn;
for (int i = 0; i < cnt_trans; i ++)
swap (arr[i], arr[Rand (0, i)]);
vector <int> vote (lgn, 0);
int cur_pos = 0;
long long ans = 0;
for (int i = 2; i <= n; i ++)
{
int lg = log2 (i - 1), p = 0;
if (par[i] > 0) par[i] --;
for (int j = 0; j < lg; j ++)
{
if (par[i] == -1)
{
cur_pos ++;
continue;
}
if (par[i] & (1 << j))
vote[arr[cur_pos ++]] ++;
else vote[arr[cur_pos ++]] --;
}
}
int cnt = 0;
for (int i = 0; i < lgn; i ++)
if (vote[i] == 0) cnt ++;
assert (cnt <= 1);
for (int i = 0; i < lgn; i ++)
if (vote[i] > 0) ans |= (1LL << i);
if (vote[lgn - 1] == 0) return (ans ^ pbml);
long long bit61 = (ans & (1LL << lgn));
ans ^= bit61;
bit61 >>= lgn;
for (int i = 0; i < lgn - 1; i ++)
bit61 ^= ((ans & (1LL << i)) > 0);
if (bit61)
for (int i = 0; i < lgn - 1; i ++)
if (vote[i] == 0) ans |= (1LL << i);
return (ans ^ pbml);
}
