#include "migrations.h"
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
/*
Hybrid protocol:
- Tail window W=50.
- Base-4 digits mapped 1..4; RESET is 0 (non-counting).
- Need 14 digits (7 per index). If a change happens with <14 slots left, fallback once with a big value (10000 + other+1).
- Museum: prefer the last >4 (fallback) message; otherwise decode last 14 digits after last reset.
*/
namespace {
// Per-test state
bool inited = false;
int Nglob = 0, LOGv = 0;
const int W = 50;
int tailStart = 1;
// LCA tables
vector<int> depth;
vector< vector<int> > up; // up[v][k]
// Online diameter
int A = 0, B = 0, D = 0;
// Streaming state
int stream_pos = -1; // 0..13 for 14 digits; >=14 means padding
int lastA = 0, lastB = 0;
bool have_reset = false;
inline void reset_test(int N){
inited = true;
Nglob = N;
LOGv = 0; while ((1 << LOGv) <= max(1, Nglob)) ++LOGv;
depth.assign(Nglob, 0);
up.assign(Nglob, vector<int>(LOGv, 0));
for (int k=0;k<LOGv;++k) up[0][k] = 0;
A=B=0; D=0;
tailStart = max(1, Nglob - W);
stream_pos = -1;
lastA = lastB = 0;
have_reset = false;
}
inline int lca(int u,int v){
if (depth[u] < depth[v]) swap(u,v);
int diff = depth[u] - depth[v];
for (int k=0;k<LOGv;++k) if (diff & (1<<k)) u = up[u][k];
if (u == v) return u;
for (int k=LOGv-1;k>=0;--k){
if (up[u][k] != up[v][k]){
u = up[u][k];
v = up[v][k];
}
}
return up[u][0];
}
inline int dist(int u,int v){
int w = lca(u,v);
return depth[u] + depth[v] - 2*depth[w];
}
inline int get_digit_base4(int x, int d){ // d-th digit LSB-first
return (x >> (2*d)) & 3; // 2 bits per base-4 digit
}
}
int send_message(int N, int i, int Pi){
if (!inited || i == 1) reset_test(N);
// Build LCA info
depth[i] = depth[Pi] + 1;
up[i][0] = Pi;
for (int k=1;k<LOGv;++k) up[i][k] = up[ up[i][k-1] ][k-1];
// Update diameter
int dA = dist(i, A), dB = dist(i, B);
bool changed = false;
int other = -1;
if (dA > D){ changed = true; other = A; B = i; D = dA; }
else if (dB > D){ changed = true; other = B; A = i; D = dB; }
int out = 0;
// Only speak in tail window
if (i >= tailStart){
// Ensure we start a stream with a reset the first time we enter the window
if (!have_reset){
out = 0; // RESET (0 doesn't count toward Z)
have_reset = true;
stream_pos = 0;
lastA = A; lastB = B;
return out;
}
// If endpoints changed
if (changed){
int slots_left = (Nglob - 1) - i; // remaining indices after i
if (slots_left >= 14){
// Safe to RESET and restart stream for new endpoints
out = 0; // RESET
stream_pos = 0;
lastA = A; lastB = B;
return out;
} else {
// Too late to complete 14 digits → fallback with a single big value
// Encodes 'other+1' so Museum can return (i, other)
int v = 10000 + (other + 1); // ≤ 20000 since other+1 ≤ 10000
out = v;
// After fallback we can be silent; correctness already guaranteed
return out;
}
}
// No change: continue (or start) streaming digits for the current (A,B)
if (stream_pos < 14){
int which = stream_pos;
int digit;
if ((which & 1) == 0){ // even -> A's digit
int du = which/2;
digit = get_digit_base4(A, du);
} else { // odd -> B's digit
int dv = which/2;
digit = get_digit_base4(B, dv);
}
out = digit + 1; // map 0..3 -> 1..4 (Z ≤ 4 if no fallback)
++stream_pos;
} else {
// Optional: send padding '1' to keep Z small (or just be silent)
out = 1; // harmless digit 0
}
}
return out; // 0..20000
}
std::pair<int,int> longest_path(std::vector<int> S){
int N = (int)S.size();
int tailStart = max(1, N - 50);
// If any fallback (>4) exists, last one wins: (index, other)
for (int i = N-1; i >= tailStart; --i){
if (S[i] > 4){
int other = S[i] - 10000 - 1;
if (other < 0) other = 0;
if (other >= N) other = N-1;
return { i, other };
}
}
// Otherwise decode base-4 stream after the last RESET (0)
int lastReset = -1;
for (int i = N-1; i >= tailStart; --i){
if (S[i] == 0){ lastReset = i; break; }
}
if (lastReset == -1){
// Fallback safety: no reset found → default
return {0, 0};
}
// Collect all digits (1..4) after lastReset
vector<int> digs;
for (int i = lastReset + 1; i < N; ++i){
if (S[i] >= 1 && S[i] <= 4) digs.push_back(S[i] - 1);
}
// Need the LAST 14 digits (pad with zeros if fewer due to tiny N)
if ((int)digs.size() < 14) digs.insert(digs.begin(), 14 - (int)digs.size(), 0);
else digs.erase(digs.begin(), digs.end() - 14);
int U = 0, V = 0;
for (int pos = 0; pos < 14; ++pos){
int d = digs[pos] & 3;
if ((pos & 1) == 0){ // U
int k = pos/2;
U |= (d << (2*k));
} else { // V
int k = pos/2;
V |= (d << (2*k));
}
}
if (U >= N) U = N-1;
if (V >= N) V = N-1;
return {U, V};
}
