제출 #1275580

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275580		mehrzad	이주 (IOI25_migrations)	C++17	0 / 100	30 ms	1080 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;

/*
Goal: Z ≤ 4, M ≈ 15–20, correctness guaranteed.

Protocol (tail-window streaming):
- Reserve a window of size W at the end (W >= 1 + 14 = 15; we use W = 20 for slack).
- At i == N - W      : send RESET (= 4).
- For i in (N - W + 1) .. (N - 1):
    * Track online diameter endpoints (A,B).
    * If (A,B) changed since the last emitted digit → send RESET (=4), mark a new stream start.
    * Else emit the next base-4 digit of U and V interleaved, LSB-first:
        order: u0, v0, u1, v1, ..., u6, v6  (14 digits total)
      The digit positions wrap if the stream restarts.
- Outside the window: send 0.

Museum decoding:
- From the tail window, take digits after the LAST reset (value 4).
- Read the LAST 14 digits after that reset; interleaved LSB-first, reconstruct U and V.
- If there are fewer than 14 digits (very small N), pad missing high digits with 0.
*/

namespace {
    // globals per test
    bool inited = false;
    int Nglob = 0, LOGv = 0;
    const int W = 20;                 // tail window size (tune: 20–32)
    int startTail = 1;                // N - W
    // tree lifting
    vector<int> depth;
    vector<vector<int>> up;
    // diameter state
    int A = 0, B = 0, D = 0;
    // streaming state
    int stream_pos = -1;              // -1 means not streaming yet; else 0..13
    int lastA = 0, lastB = 0;         // to detect changes
    bool streaming = false;
    // helpers
    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;
        startTail = max(1, Nglob - W);
        stream_pos = -1;
        lastA = lastB = 0;
        streaming = 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; diff; ++k, diff>>=1) if (diff&1) 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; // since base-4 digit = 2 bits
    }
}

int send_message(int N, int i, int Pi){
    if (!inited || i==1) reset_test(N);

    // build lifting
    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);
    if (dA > D){ B = i; D = dA; }
    else if (dB > D){ A = i; D = dB; }

    // default silent
    int out = 0;

    if (i == N - W){
        // force a reset: start of tail window
        out = 4;               // RESET marker (Z ≤ 4 holds)
        streaming = false;
        stream_pos = -1;
        lastA = A; lastB = B;
    } else if (i > N - W){
        // inside tail window
        bool changed = (A != lastA) || (B != lastB);
        if (changed){
            out = 4;           // RESET
            streaming = false;
            stream_pos = -1;
            lastA = A; lastB = B;
        } else {
            // continue / start streaming digits for (A,B)
            if (!streaming){ streaming = true; stream_pos = 0; }
            int digit;
            if (stream_pos < 14){
                // interleaved u0,v0,u1,v1,...
                int which = stream_pos;
                if (which % 2 == 0){
                    int du = which/2;
                    digit = get_digit_base4(A, du);
                } else {
                    int dv = which/2;
                    digit = get_digit_base4(B, dv);
                }
            } else {
                // extra digits (if any) harmless; send 0 to stay in Z ≤ 4
                digit = 0;
            }
            out = digit + 1;   // map {0,1,2,3} -> {1,2,3,4}
            ++stream_pos;
        }
    }

    return out; // 0 outside window; 1..4 inside
}

std::pair<int,int> longest_path(std::vector<int> S){
    int N = (int)S.size();
    int tailStart = max(1, N - 20); // must match W in send_message
    // Find the last reset (=4) in the tail window
    int lastReset = -1;
    for (int i = N-1; i >= tailStart; --i){
        if (S[i] == 4) { lastReset = i; break; }
    }
    // Collect digits after last reset
    vector<int> digs; digs.reserve(20);
    for (int i = max(tailStart, lastReset+1); i < N; ++i){
        int v = S[i];
        if (v >= 1 && v <= 4) digs.push_back(v-1); // base-4 digit
    }
    // We need the last 14 digits after the last reset.
    while ((int)digs.size() < 14) digs.push_back(0); // pad if tiny N
    // Take the last 14
    vector<int> last14(digs.end()-14, digs.end());
    // Reconstruct A and B from interleaved LSB-first digits
    int A = 0, B = 0;
    for (int pos = 0; pos < 14; ++pos){
        int d = last14[pos];
        if (pos % 2 == 0){ // A digit
            int k = pos/2;
            A |= (d << (2*k));
        } else { // B digit
            int k = pos/2;
            B |= (d << (2*k));
        }
    }
    // Clamp to [0, N-1]
    if (A >= N) A = N-1;
    if (B >= N) B = N-1;
    return {A, B};
}

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