Submission #1254067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254067		canadavid1	Migrations (IOI25_migrations)	C++20	73.68 / 100	40 ms	636 KiB

migrations

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

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