#include <bits/stdc++.h>
#include "Alice.h"
using namespace std;
int n = 5000, cnt_trans = 0, lgn = 13;
mt19937_64 mt (24022007);
int Rand (int l, int r)
{
unsigned long long x = mt ();
return x % (r - l + 1) + l;
}
vector <pair <int, int>> tree_trans;
vector <pair <int, int>> Alice()
{
for (int i = 1; i <= n; i ++)
cnt_trans += floor (log2 (i));
//cout << cnt_trans / lgn << '\n';
long long x = setN (n);
vector <int> arr (cnt_trans, 0);
for (int i = 0; i < cnt_trans; i ++)
arr[i] = i % lgn;
/*
for (auto i: arr) cout << i << ' ';
cout << endl;
*/
for (int i = 0; i < cnt_trans; i ++)
swap (arr[i], arr[Rand (0, i)]);
/*
for (auto i: arr) cout << i << ' ';
cout << endl;
*/
//cout << n << ' ' << arr.size () << endl;
string trans;
int cur_pos = 0;
for (int i = 2; i <= n; i ++)
{
//cout << i << endl;
int lg = floor (log2 (i)), p = 0;
for (int j = 0; j < lg; j ++)
p += (((x & (1LL << arr[cur_pos ++])) > 0) << j);
p ++;
//cout << p << ' ' << i << endl;
tree_trans.push_back (make_pair (p, i));
//cout << "OK" << endl;
}
return tree_trans;
}
#include <bits/stdc++.h>
#include "Bob.h"
using namespace std;
#ifndef TKML
int n = 5000, cnt_trans = 0, lgn = 13;
mt19937_64 mt (24022007);
int Rand (int l, int r)
{
unsigned long long x = mt ();
return x % (r - l + 1) + l;
}
#endif // TKML
long long Bob (vector <pair <int, int>> tree)
{
mt19937_64 mt (24022007);
for (int i = 1; i <= n; i ++)
cnt_trans += floor (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 = floor (log2 (i)), 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 ++]] --;
}
}
for (int i = 0; i < lgn; i ++)
if (vote[i] > 0) ans |= (1LL << i);
assert (ans >= 0 and ans <= (1LL << lgn));
return ans;
}
