Submission #1275585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275585		mehrzad	Migrations (IOI25_migrations)	C++17	0 / 100	31 ms	1084 KiB

migrations

#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};
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 30
• Subtask 2: 0 / 70