#include <vector>
#include <utility>
// ---------- global data, kept between calls of send_message ----------
static bool _initialized = false;
static std::vector<int> _depth;
static int _best = -1;
static int _best_depth = -1;
struct Block {
int start;
int end;
int size;
int digits_needed;
};
static std::vector<Block> _blocks;
static std::vector<int> _block_of_idx;
// Encoding state
static bool _is_encoding = false;
static int _enc_blk_id = 0;
static int _enc_offset = 0;
static int _enc_digit_idx = 0;
static int _enc_total = 0;
// ------------------------------------------------------------
static void _prepare_structures(int N) {
_initialized = true;
// ----- block sizes ------------------------------------------------
// 6 large blocks of size 1664 (need 6 base-4 digits)
// 1 padding block of size 12 (need 2 digits)
// 1 final block of size 4 (need 1 digit)
int LARGE_COUNT = 6;
int B_LARGE = 1664;
int D_LARGE = 6;
int PAD_SIZE = 12;
int D_PAD = 2;
int FIN_SIZE = 4;
int D_FIN = 1;
int cur = 0;
for (int i = 0; i < LARGE_COUNT; ++i) {
int start = cur;
int end = start + B_LARGE - 1;
_blocks.push_back({start, end, B_LARGE, D_LARGE});
cur = end + 1;
}
// padding block
int pad_start = cur;
int pad_end = pad_start + PAD_SIZE - 1;
_blocks.push_back({pad_start, pad_end, PAD_SIZE, D_PAD});
cur = pad_end + 1;
// final block
int fin_start = cur;
int fin_end = fin_start + FIN_SIZE - 1;
_blocks.push_back({fin_start, fin_end, FIN_SIZE, D_FIN});
// ----- mapping from index to block --------------------------------
_block_of_idx.assign(N, 0);
for (int b_id = 0; b_id < (int)_blocks.size(); ++b_id) {
for (int i = _blocks[b_id].start; i <= _blocks[b_id].end; ++i) {
if (i < N) {
_block_of_idx[i] = b_id;
}
}
}
// ----- depth array -------------------------------------------------
_depth.assign(N, 0);
_best = 0;
_best_depth = 0;
_is_encoding = false;
}
// ------------------------------------------------------------
int send_message(int N, int i, int Pi) {
// first call - initialise everything
if (!_initialized) {
_prepare_structures(N);
}
// ----- depth of the current vertex --------------------------------
int d = _depth[Pi] + 1;
_depth[i] = d;
// ----- maintain the deepest vertex seen so far --------------------
if (d > _best_depth) {
_best_depth = d;
_best = i;
}
// ----- if we are currently writing offset digits -------------------
if (_is_encoding) {
// current digit (least significant first) using bitwise shifts for 4^digit_idx
int power4 = 1 << (2 * _enc_digit_idx);
int digit = (_enc_offset / power4) % 4;
int val = digit + 1;
_enc_digit_idx++;
if (_enc_digit_idx == _enc_total) {
_is_encoding = false; // finished this block
}
return val;
}
// ----- we are not inside an encoding phase -------------------------
// find block of current vertex
int blk = _block_of_idx[i];
int blk_start = _blocks[blk].start;
int blk_end = _blocks[blk].end;
int blk_digits = _blocks[blk].digits_needed;
// is this vertex the last one of its block ?
if (i == blk_end) {
// does the global deepest vertex belong to this block ?
if (_best >= blk_start && _best <= blk_end) {
// we have to encode the offset of _best inside this block
int offset = _best - blk_start;
if (blk == (int)_blocks.size() - 1) {
// final block - offset fits into a single digit
return offset + 1;
} else {
// start the encoding, next D vertices will carry the digits
_is_encoding = true;
_enc_blk_id = blk;
_enc_offset = offset;
_enc_digit_idx = 0;
_enc_total = blk_digits;
return 1; // any non-zero, e.g. 1
}
} else {
return 0;
}
} else {
return 0;
}
}
// ------------------------------------------------------------
std::pair<int, int> longest_path(std::vector<int> S) {
int N = S.size();
// rebuild the same block partition as in the sender
int LARGE_COUNT = 6;
int B_LARGE = 1664;
int D_LARGE = 6;
int PAD_SIZE = 12;
int D_PAD = 2;
int FIN_SIZE = 4;
int D_FIN = 1;
std::vector<Block> blocks;
int cur = 0;
for (int i = 0; i < LARGE_COUNT; ++i) {
int start = cur;
int end = start + B_LARGE - 1;
blocks.push_back({start, end, B_LARGE, D_LARGE});
cur = end + 1;
}
int pad_start = cur;
int pad_end = pad_start + PAD_SIZE - 1;
blocks.push_back({pad_start, pad_end, PAD_SIZE, D_PAD});
cur = pad_end + 1;
int fin_start = cur;
int fin_end = fin_start + FIN_SIZE - 1;
blocks.push_back({fin_start, fin_end, FIN_SIZE, D_FIN});
// map each index to its block (needed only for the scan)
std::vector<int> block_of_idx(N, 0);
for (int b_id = 0; b_id < (int)blocks.size(); ++b_id) {
for (int i = blocks[b_id].start; i <= blocks[b_id].end; ++i) {
if (i < N) {
block_of_idx[i] = b_id;
}
}
}
// ----- find the last indicator (non-zero entry at a block's end) -----
for (int i = N - 1; i >= 0; --i) {
if (S[i] == 0) {
continue;
}
int b = block_of_idx[i];
int st = blocks[b].start;
int en = blocks[b].end;
int digits = blocks[b].digits_needed;
if (i != en) { // not a block end -> this is a digit
continue;
}
// we have found the indicator of the deepest block
int offset = 0;
if (b == (int)blocks.size() - 1) { // final block
offset = S[i] - 1;
} else {
offset = 0;
for (int k = 0; k < digits; ++k) {
int val = S[i + 1 + k]; // digits are stored immediately after the indicator
int digit = val - 1;
offset += digit * (1 << (2 * k)); // 1 << (2*k) is 4^k
}
}
int deepest = st + offset;
return {0, deepest};
}
// according to the statement this line is never reached
return {0, 0};
}
