Submission #1253152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253152		QwertyPi	Migrations (IOI25_migrations)	C++20	0 / 100	32 ms	1208 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
#define int long long
#define all(a) begin(a), end(a)
using namespace std;

const int N = 10'000;
const int LGN = 20;
vector<int> G[N];

pair<int, int> dfs(int v, int pa = -1) {
    int ud = v, d = -1;
    for (int u : G[v]) {
        if (u == pa) continue;
        auto [ud2, d2] = dfs(u, v);
        if (d2 > d) ud = ud2, d = d2;
    }
    return {ud, d + 1};
}

int binom(int k, int l) {
    int res = 1;
    for (int i = 1; i <= l; i++) {
        res = res * (k + 1 - i) / i;
    }
    return res;
}

int f(int K, int L) {
    int res = 0;
    for (int l = 0; l <= L; l++) {
        res += binom(K, l) << (l * 2);
    }
    return res;
}

void test() {
    for (int k = 0; k <= 50; k++) {
        for (int l = 0; l <= min(k, 20LL); l++) {
            printf("f(%02d, %02d) = %lld\n", k, l, f(k, l));
        }
    }
    exit(0);
}

vector<pair<int, int>> K {{48, 4}, {6, 3}, {3, 2}, {2, 2}};

void precalc() {

}

int encrypt(int N, int a, int b) {
    assert(a < b);
    int X = 0;
    for (int i = 0; i < a; i++) X += N - 1 - i;
    for (int i = a + 1; i < b; i++) X++;
    return X;
}

pair<int, int> decrypt(int N, int X) {
    int a = 0, b = 1;
    while (X >= N - 1 - a) X -= N - 1 - a, ++a, b = a + 1;
    while (X >= 1) --X, ++b;
    return {a, b};
}

int msg[N];

vector<int> R {0};
vector<int> C {19, 7, 4}, P {12, 3, 2};

pair<int, int> diameter() {
    auto [u, du] = dfs(0);
    auto [v, d] = dfs(u);
    if (u > v) swap(u, v);
    int a = find(all(R), u) - R.begin();
    int b = find(all(R), v) - R.begin();
    return {a, b};
}

int J1, K1;
int32_t send_message(int32_t N, int32_t i, int32_t Pi) {
    for (int x = 0; x < C.size(); x++) {
        int c = C[x], p = P[x];
        if (i == N - c) {
            auto [a, b] = diameter();
            int X = encrypt(R.size(), a, b);
            R = {R[a], R[b]};
            for (int j = 0; j < p; j++) {
                msg[N - c + j] = X % 5;
                X /= 5;
            }
        }
    }
    vector<vector<int>> M1 {
        {0, 1, 2},
        {2, 3, 4},
        {4, 0, 2},
        {2, 4, 1},
        {1, 3, 0}
    };
    if (i == N - 2) {
        G[i].push_back(Pi);
        G[Pi].push_back(i);
        R.push_back(i);
        auto [a, b] = diameter();
        for (int j = 0; j < 5; j++) {
            for (int k = 0; k < 2; k++) {
                if (set<int>{a, b} == set<int>{M1[j][k], M1[j][k + 1]}) {
                    msg[N - 2] = j;
                    J1 = j; K1 = k;
                }
            }
        }
    } else if (i == N - 1) {
        G[i].push_back(Pi);
        G[Pi].push_back(i);
        R.push_back(i);
        auto [a, b] = diameter();
        if (b == 5) {
            for (int k = 0; k < 3; k++) {
                if (M1[J1][k] == a) msg[N - 1] = 2 + k;
            }
        } else {
            for (int k = 0; k < 2; k++) {
                if (set<int>{a, b} == set<int>{M1[J1][k], M1[J1][k + 1]}) {
                    msg[N - 1] = k;
                }
            }
        }
    } else {
        G[i].push_back(Pi);
        G[Pi].push_back(i);
        R.push_back(i);
    }
    return msg[i];
}

pair<int32_t, int32_t> longest_path(vector<int32_t> S) {
    S.insert(S.begin(), 0);
    int prv = 1;
    for (int x = 0; x < C.size(); x++) {
        int c = C[x], p = P[x];
        while (prv < c) R.push_back(prv++);
        int X = 0;
        for (int i = c + p - 1; i >= c; i--) {
            X = X * 5 + S[i];
        }
        auto [a, b] = decrypt(R.size(), X);
        R = {R[a], R[b]};
    }

    R.push_back(N - 4);
    R.push_back(N - 3);
    R.push_back(N - 2);

    vector<vector<int>> M1 {
        {0, 1, 2},
        {2, 3, 4},
        {4, 0, 2},
        {2, 4, 1},
        {1, 3, 0}
    };

    switch (S[N - 1]) {
        case 0:
            return {R[M1[S[N - 2]][0]], R[M1[S[N - 2]][1]]};
        case 1:
            return {R[M1[S[N - 2]][1]], R[M1[S[N - 2]][2]]};
        case 2:
            return {R[M1[S[N - 2]][0]], N - 1};
        case 3:
            return {R[M1[S[N - 2]][1]], N - 1};
        case 4:
            return {R[M1[S[N - 2]][2]], N - 1};
    }
}

Compilation message (stderr)

migrations.cpp: In function 'void test()':
migrations.cpp:40:26: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   40 |             printf("f(%02d, %02d) = %lld\n", k, l, f(k, l));
      |                       ~~~^                   ~
      |                          |                   |
      |                          int                 long long int
      |                       %02lld
migrations.cpp:40:32: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
   40 |             printf("f(%02d, %02d) = %lld\n", k, l, f(k, l));
      |                             ~~~^                ~
      |                                |                |
      |                                int              long long int
      |                             %02lld
migrations.cpp: In function 'std::pair<int, int> longest_path(std::vector<int>)':
migrations.cpp:177:1: warning: control reaches end of non-void function [-Wreturn-type]
  177 | }
      | ^

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