Submission #1254031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254031		fve5	Migrations (IOI25_migrations)	C++20	86.40 / 100	430 ms	196532 KiB

migrations

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

vector<vector<int>> dst = {{0}};
int get_dst(int u, int v) { return dst[max(u, v)][min(u, v)]; }

int ext1 = 0, ext2 = 0;

enum Status { FAST_ENCODE, TRANSITION, SURPRISE, SLOW_ENCODE };
Status status = FAST_ENCODE;
int enc_idx = 0;
bool was1 = false, was2 = false;
int calls = 0;

int send_message(int N, int i, int Pi) {
    dst.emplace_back(i + 1);
    for (int j = 0; j < i; j++)
        dst[i][j] = get_dst(Pi, j) + 1;
    
    int cur_d = get_dst(ext1, ext2);
    int d1 = get_dst(ext1, i);
    int d2 = get_dst(ext2, i);

    if (d1 >= d2) {
        if (d1 > cur_d) {
            ext2 = i;
        }
    } else {
        if (d2 > cur_d) {
            ext1 = i;
        }
    }

    if (i < N - 16) return 0;

    auto repr = [&]() -> int {
        int ans = 0;
        for (int i = 0; i < 14; i++) {
            ans |= ((ext1 >> i) & 1) << (2 * i);
            ans |= ((ext2 >> i) & 1) << (2 * i + 1);
        }
        return ans;
    };
    cerr << "STARTING " << i << " " << ext1 << " " << ext2 << " " << repr() << endl;

    auto fast_encode = [&]() -> int {
        if (i == ext1 || i == ext2) {
            status = TRANSITION;
            was1 = i == ext1;
            was2 = i == ext2;
            cerr << "FAST_ENCODE is ext " << was1 << " " << was2 << endl;
            return 0;
        }
        calls++;
        if (i == N - 3) {
            cerr << "FAST_ENCODE terminated" << endl;
            status = SURPRISE;
        }
        cerr << "FAST_ENCODE idx " << enc_idx << endl;
        return 1 + ((repr() >> (2 * (enc_idx++))) & 3);
    };

    auto transition = [&]() -> int {
        if ((was1 && i == ext2) || (was2 && i == ext1)) {
            cerr << "TRANSITION surprised" << endl;
            status = SURPRISE;
            if (was2) swap(ext1, ext2);
            return 0;
        }
        status = SLOW_ENCODE;
        if (i == ext1 || i == ext2) {
            cerr << "TRANSITION cur" << endl;
            return 1 + (2 | (int)(i == ext2));
        }
        cerr << "TRANSITION old" << endl;
        return 1 + (int)was2;
    };

    auto slow_encode = [&]() -> int {
        if ((was1 && i == ext2) || (was2 && i == ext1)) {
            cerr << "SLOW_ENCODE surprised" << endl;
            status = SURPRISE;
            if (was2) swap(ext1, ext2);
            return 0;
        }
        calls++;
        int enc = was1 ? ext2 : ext1;
        if (i == ext1 || i == ext2) {
            cerr << "SLOW_ENCODE cur idx " << enc_idx << endl;
            return 1 + (2 | ((enc >> (enc_idx++)) & 1));
        }
        cerr << "SLOW_ENCODE old idx " << enc_idx << endl;
        return 1 + ((enc >> (enc_idx++)) & 1);
    };

    auto surprise = [&]() -> int {
        cerr << "SURPRISE " << (i == ext1) << " " << (i == ext2) << endl;
        if (i == ext1) return 1;
        if (i == ext2) return 2;
        return 0;
    };

    switch (status) {
    case FAST_ENCODE: return fast_encode();
    case TRANSITION : return transition();
    case SLOW_ENCODE: return slow_encode();
    case SURPRISE   : return surprise();
    }
}

pair<int, int> longest_path(vector<int> S) {
    int N = S.size();
    S = vector<int>(S.rbegin(), S.rbegin() + 16);

    int enc_idx = 0;
    int ext1 = 0, ext2 = 0;

    // Fast encode
    while (enc_idx < 14) {
        int v = S.back() - 1; S.pop_back();
        if (v == -1) break;
        ext1 |= (v & 1) << enc_idx;
        ext2 |= ((v >> 1) & 1) << enc_idx;
        cerr << "FAST_DECODE " << v << " " << ext1 << " " << ext2 << endl; 
        enc_idx++;
    }

    // true for ext2
    bool which = false;

    if (enc_idx != 14) {
        // Transition
        int v = S.back() - 1; S.pop_back();
        if (v != -1) {
            which = v & 1;
            int new_ext = (v & 2) ? N - S.size() - 1 : N - S.size() - 2;

            if (which) ext2 = new_ext;
            else ext1 = new_ext;
        
            // Slow encode
            while (!S.empty()) {
                int v = S.back() - 1; S.pop_back();
                if (v == -1) {
                    if (which) {
                        ext1 = N - S.size() - 1;
                        swap(ext1, ext2);
                    } else {
                        ext2 = N - S.size() - 1;
                    }
                    break;
                }
                if (which) ext1 |= (v & 1) << enc_idx;
                else ext2 |= (v & 1) << enc_idx;
                if (v & 2) {
                    if (which) ext2 = N - S.size() - 1;
                    else ext1 = N - S.size() - 1;
                }
                enc_idx++;
            }
        } else {
            ext1 = N - S.size() - 2;
            ext2 = N - S.size() - 1;
        }
    }

    // Surprise
    while (!S.empty()) {
        int v = S.back(); S.pop_back();
        if (v == 1) ext1 = N - S.size() - 1;
        if (v == 2) ext2 = N - S.size() - 1;
    }

    return {ext1, ext2};
}

Compilation message (stderr)

migrations.cpp: In function 'int send_message(int, int, int)':
migrations.cpp:110:1: warning: control reaches end of non-void function [-Wreturn-type]
  110 | }
      | ^

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