// #include "migrations.h"
#include <vector>
#include <utility>
#include <iostream>
#include <tuple>
#include <iomanip>
/*
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
*/
int lca(int a,int b,const std::vector<int>& d,const std::vector<int>& gp,const std::vector<int>& P) {
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,const std::vector<int>& d,const std::vector<int>& gp,const std::vector<int>& P) {
int v = d[a] + d[b] - 2*d[lca(a,b,d,gp,P)];
//STDCERR << "dist(" << a << "," << b << ") = " << v << "\n";
return v;
}
/*
translation of problem:
encoder knows a pair (a,b) that starts as (0,1)
for i = 2..N either the pair stays or one of them changes to i (3 options) (for i=2 it must change)
can optionally return a number 1 <= Z <= [4] at most M = [8] times
the decoder needs to figure out the final pair (may be reversed)
*/
// 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;
/*
use the last 200ish to encode
75 values alternatingly:
first 50 encode A/200 with one-hot
last 25 encode A % 200 with choose-2
if interrupted in first 50:
last 25 encodes the position within
if then interrupted in last 25:
encode position within somehow
*/
// neither == the pair stays [A,B]
// newA == the pair changes to [i,B]
// newB == the pair changes to [i,A]
int send_message_internal(const int N,const int i,bool newA,bool newB);
int send_message(const int N,const int i,const int Pi) { // this can retain information across calls
static std::vector<int> P{{0}},d{{0}},gp{{0}};
static int A = 1,B = 0,D = 1; // invariant: A > B
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);
const bool newA = dist(i,B,d,gp,P) > D;
const bool newB = !newA && dist(i,A,d,gp,P) > D;
if (newB) {
D++;
B = A;
A = i;
}
else if (newA) {
D++;
A = i;
}
if(i >= N-M-2 && newA || newB) std::cerr << newA << newB << " " << A << " " << B << "\n";
// if(i == N-M) {std::cerr << "...";}
// if (i >= N-M) {std::cerr << 2*newA + newB << " ";}
return send_message_internal(N,i,newA,newB);
}
int send_message_internal(const int N,const int i,bool newA,bool newB)
{
static int A = 1;
static int B = 0; // invariant: A > B
static int to_encode = -1;
if (i == N-M) {
to_encode = encode(A,B);
// std::cerr << i << " " << A << " " << B << " " << to_encode << "\n";
}
if (newA) A = i;
if (newB) {B = A;A = i;}
static enum {
neither,
cA,
cB,
both
} seen;
if (i < N-M) return 0;
if(i == N-M) {
}
int idx = N-i;
if (idx == 1) {
switch (seen)
{
case neither:
case both:
return 2*newB + newA;
case cA:
if (newB) return 4;
return 2*newA;
case cB:
if (newB) return 4;
return 2*newA+1;
}
}
int retval = 0;
retval = (to_encode >> (idx - 2))&1;
if (seen == both) retval = 0;
if (newA) {
switch (seen)
{
case neither:
seen = cA;
case cA:
case cB:
retval += 2;
break;
case both:
//STDCERR << " nA b\n";
retval = 1;
break;
}
}
if (newB) {
switch (seen)
{
case neither:
seen = cB;
retval += 2;
break;
case cA:
case cB:
seen = both;
retval = 4;
break;
case both:
//STDCERR << " nB cB\n";
retval = 2;
break;
}
}
return retval;
}
std::pair<int, int> longest_path(std::vector<int> S) {
//STDCERR << "---------\n";
int A = 1,B=0;
int to_decode = 0;
int prev = -1;
const int N = S.size();
// std::cerr << "\n...";
// for(int i = N-M; i < N; i++) std::cerr << S[i] << " ";
// std::cerr << "\n";
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
A = -1;
int i;
for(i = 0; i < N; i++) {
if (S[i] < 2) continue;
if (S[i] == 4) break;
A = i;
}
B = A;
A = i;
// std::cerr << ":" << A << " " << B << "\n";
for(;i < N; i++) {
if (S[i] == 1) A = i;
else if (S[i] == 2) {B = A; A = i;};
// std::cerr << (S[i]==1) << (S[i]==2) << ":" << A << " " << B << "\n";
}
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(A,B) = decode(to_decode);
// std::cerr << A << " " << B << " " << to_decode << " " << prev << "\n";
if (prev == -1) {
switch (S.back())
{
case 0:
return {A,B};
case 1:
return {B,N-1};
case 2:
return {A,N-1};
default:
return {-1,-1};//std::unreachable();
}
}
if (S.back() > 1) prev = N-1;
if (S.back() & 1) return {prev,A};
else return {prev,B};
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
