#include "migrations.h"
#include <utility>
#include <iostream>
#include <tuple>
/*
to get some longest path: choose the two oldest candidates
upon update, at one of the previous is still included, and the other is the new node
=> Z = 2, M=N solution
*/
std::vector<int> P{{0}},d{{0}},gp{{0}};
int curA=0,curB=1,curD=1;
enum {
neither,
cA,
cB,
both
} seen;
int lca(int a,int b) {
int ct = 0;
if (d[a] < d[b]) std::swap(a,b);
while(d[a] > d[b])
if (d[gp[a]] >= d[b]) a = gp[a];
else a = P[a];
while (a != b)
if (gp[a] != gp[b]) a = gp[a],b=gp[b];
else a = P[a],b=P[b];
return a;
}
int dist(int a,int b) {
int v = d[a] + d[b] - 2*d[lca(a,b)];
//STDCERR << "dist(" << a << "," << b << ") = " << v << "\n";
return v;
}
// using the last M messages, encode which two
// can change during, but then do some skip-code thing
/*
subtask 1:
last M messages encode the bits of the end. if it suddenly changes to current node, encode with 0.
M = 29 Z <= 4:
14+14 bits to encode ends: first and second.
If second is interrupted by POI: +1 end bit direction
If first is interrupted by POI: +1 end bit.
0/1 -> normal bit
2/3 -> POI + normal bit
4 -> second POI. mode switch.
after 4, have seen both. 2 -> new of the older, 4 -> new of the newer.
else:
1 extra:
if none were interrupted:
0 -> normal
1 -> this is end A
2 -> this is end B
if some were interrupted:
0/1 -> which end is to be kept (normal)
2/3 -> this is one end, which end is to be kept
4 -> this is the second POI. last 2/3 is the first one.
*/
int encode(int A,int B) {
// return A * 10000 + B;
if (A <= B) return -1;
int to_decode = 0;
to_decode = B;
for(int j = 0; j < A; j++) to_decode += j;
return to_decode;
}
std::pair<int,int> decode(int c) {
// return {c / 10000, c % 10000};
int s = 0;
int i = 0;
for(i = 0; c >= s;i++) s+=i;
s -= i;
return {i-1,c-s-1};
}
int M = 27;
bool B_4 = false;
int to_encode = -1;
int send_message(int N, int i, int Pi) { // this can retain information across calls
if (i == N-M) {
if (curA < curB) std::swap(curA,curB);
to_encode = encode(curA,curB);
std::cerr << i << " " << curA << " " << curB << " " << to_encode << "\n";
}
P.push_back(Pi);
d.push_back(d[Pi]+1);
if(d[gp[gp[Pi]]] - 2*d[gp[Pi]] + d[Pi] == 0) gp.push_back(gp[gp[Pi]]);
else gp.push_back(Pi);
bool newA = dist(i,curB) > curD;
bool newB = !newA && dist(i,curA) > curD;
if (newB) {
curD=dist(curA,i);
curB = i;
}
else if (newA) {
curD=dist(curB,i);
curA = i;
}
if (i < N-M) return 0;
if(i == N-M) {
}
int idx = N-i;
if (idx == 1) {
switch (seen)
{
case neither:
return 2*newB + newA;
case cA:
if (newB) return 4;
return 2*newA;
case cB:
if (newA) return 4;
return 2*newB+1;
case both:
if (!(newA || newB)) return 0;
if (newA) return 2 - B_4;
else return 1 + B_4;
}
}
int retval = 0;
retval = (to_encode >> (idx - 2))&1;
if (seen == both) retval = 0;
if (newA) {
switch (seen)
{
case neither:
case cA:
//STDCERR << " nA cA\n";
retval += 2;
seen = cA;
break;
case cB:
//STDCERR << " nA cB\n";
seen = both;
retval = 4;
break;
case both:
//STDCERR << " nA b\n";
retval = 2 - B_4;
break;
}
}
if (newB) {
switch (seen)
{
case neither:
case cB:
//STDCERR << " nB cB\n";
retval += 2;
seen = cB;
break;
case cA:
//STDCERR << " nB cA\n";
seen = both;
retval = 4;
B_4 = true;
break;
case both:
//STDCERR << " nB cB\n";
retval = 1 + B_4;
break;
}
}
return retval;
}
std::pair<int, int> longest_path(std::vector<int> S) {
//STDCERR << "---------\n";
int cur[2] = {0,0};
int to_decode = 0;
int prev = -1;
const int N = S.size();
bool any_4 = false;
for(int i = N-M; i < N; i++) any_4 |= S[i] == 4;
//STDCERR << "any_4: " << any_4 << "\n";
if (any_4) {
// both are >= N-M
int A = -1;
int i;
for(i = N-M; i < N; i++) {
if (S[i] < 2) continue;
if (S[i] == 4) break;
A = i;
}
int B = i;
for(;i < N; i++) {
if (S[i] == 1) A = i;
if (S[i] == 2) B = i;
}
return {A,B};
}
for(int idx = M; idx > 1; idx--) {
if (S[N-idx] >= 2) prev = N-idx;
to_decode |= (S[N-idx]&1) << (idx - 2);
// cur[idx&1] |= (S[N-idx]&1) << (idx / 2 - 1);
}
std::tie(cur[1],cur[0]) = decode(to_decode);
std::cerr << cur[0] << " " << cur[1] << " " << to_decode << " " << prev << "\n";
if (prev == -1) {
switch (S.back())
{
case 0:
return {cur[0],cur[1]};
case 1:
return {N-1,cur[1]};
case 2:
return {cur[0],N-1};
default:
return {-1,-1};//std::unreachable();
}
}
if (S.back() > 1) prev = N-1;
return {prev,cur[S.back()&1]};
}
