#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().
int next(long& lastEven, long& lastOdd, bool odd) {
if (odd) {
lastOdd += 2;
return lastOdd - 2;
} else {
lastEven += 2;
return lastEven - 2;
}
}
std::vector<std::pair<int,int>> Alice(){
long N = 4551;
long long X = setN(N);
long lastEven = 2, lastOdd = 1;
std::vector<std::pair<int, int>> output;
for (unsigned x = 0; x < 70; x++) {
bool kind = x % 2 == 0;
long last = next(lastEven, lastOdd, kind);
output.push_back({0 + 1, last + 1});
int v = X;
if (kind) v = ~v;
for (int i = 0; i < 64; i++) {
long nlast = next(lastEven, lastOdd, v & 1);
output.push_back({last + 1, nlast + 1});
last = nlast;
v >>= 1;
}
}
return output;
}
#include <algorithm>
#include <vector>
#include <bitset>
#include "Bob.h"
enum ReplicaKind {
RK_NORMAL = 0,
RK_INVERTED = 1
};
long long analyze_replica(std::vector<std::vector<int>>& adj, int node, enum ReplicaKind rk) {
int out = 0, bits = 0;
while (true) {
if (node % 2)
out |= 1ll << bits;
bits++;
if (adj[node].empty()) break;
node = adj[node][0];
}
if (rk == RK_INVERTED)
out = ~out;
return out;
}
void lildfs(std::vector<std::vector<int>>& v, int n, int p) {
auto iter = std::find(v[n].begin(), v[n].end(), p);
if (iter != v[n].end()) v[n].erase(iter);
for (auto c: v[n])
lildfs(v, c, n);
}
long long Bob(std::vector<std::pair<int,int>> V){
std::vector<std::vector<int>> adj;
for (auto edge: V) {
while (std::max(edge.first, edge.second) > adj.size())
adj.push_back({});
adj[edge.first - 1].push_back(edge.second - 1);
adj[edge.second - 1].push_back(edge.first - 1);
}
lildfs(adj, 0, 0);
int output = 0;
for (auto replica: adj[0]) {
if (adj[replica].empty()) continue;
output |= analyze_replica(adj, adj[replica][0], replica % 2 == 0 ? RK_NORMAL : RK_INVERTED);
}
return output;
}
