Submission #1256313

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256313		arafatbot144	Migrations (IOI25_migrations)	C++20	79.12 / 100	1821 ms	1108 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rngl(chrono::steady_clock::now().time_since_epoch().count());

const ll inf = 1e9;
const ll biginf = 1e18;
const int maxN = 10005;

vector<int> g[maxN];
int dist[maxN], x, y = 1;
int bfs(int x, int y) {
    for (int i = 0; i < maxN; i++) dist[i] = inf;
    queue<int> q; q.push(x); dist[x] = 0;
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int u : g[v]) {
            if (dist[u] == inf) {
                dist[u] = dist[v] + 1; q.push(u);
            }
        }
    } return dist[y];
}
int send_message(int n, int i, int pi) {
    g[pi].pb(i); g[i].pb(pi);
    if (i < n - 21) {
        if (bfs(i, x) > bfs(x, y)) y = i;
        if (bfs(i, y) > bfs(x, y)) x = i;
        return 0;
    }

    if (i < n - 14) {
        if (bfs(i, x) > bfs(x, y)) {
            y = x; x = i; return 4;
        }

        if (bfs(i, y) > bfs(x, y)) {
            x = i; return 4;
        }

        int tmp = x, pos = n - i - 15;
        while (pos--) tmp /= 4;
        return (tmp % 4);
    }

    int tmp = y, pos = n - i - 1;
    while (pos--) tmp /= 2;

    if (bfs(i, x) > bfs(x, y)) {
        y = i; return 0;
    }

    if (bfs(i, y) > bfs(x, y)) {
        x = i; return tmp % 2 + 1;
    }

    return tmp % 2 + 3;
}

pair<int, int> longest_path(vector<int> s) {
    int x = 0, y = 0, n = s.size();
    for (int i = 1; i < n; i++) {
        if (i < n - 21) continue;
        if (i < n - 14) {
            if (s[i] == 4) x = i;
            else {
                int tmp = x, pos = n - i - 15, cur = 1;
                while (pos--) tmp /= 4, cur *= 4;
                x = x - (tmp % 4) * cur + s[i] * cur;
            } continue;
        }
        
        if (s[i] == 0) y = i;
        else if (s[i] <= 2) {
            x = i;
            int tmp = y, pos = n - i - 1, cur = 1;
            while (pos--) tmp /= 2, cur *= 2;
            y = y - (tmp % 2) * cur + (s[i] - 1) * cur;
        } else {
            int tmp = y, pos = n - i - 1, cur = 1;
            while (pos--) tmp /= 2, cur *= 2;
            y = y - (tmp % 2) * cur + (s[i] - 3) * cur;
        }
    }


    return {x, y};
}

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