제출 #1251791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251791		fv3	Migrations (IOI25_migrations)	C++20	74.49 / 100	695 ms	1380 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>

using namespace std;
#ifdef LOCAL
#include "/home/fv3/Desktop/prog/debug/debug.h"
#else
#define debug(...) 42
#endif


const int N = 10000;
vector<vector<int>> adj(N);

vector<int> id = {3, 1, 2, 0, 3, 0, 1, 2, 4, 1, 2, 2, 0, 4, 3, 1, 0, 1, 2, 1, 1, 3, 2, 4, 2, 0, 2, 3};
const long long magic_number = 62486423536ll;

int diameter = 0;
int ai = 0, bi = 0;

bool Aknown = false;
bool Bknown = false;

int Abit = 0;
int Bbit = 0;

int send_message(int N_, int i, int Pi) {
    assert(N_ == 10000);

    if (i == 1) {
        debug(id);
    }

    adj[i].push_back(Pi);
    adj[Pi].push_back(i);

    vector<int> dist(i + 1), vis(i + 1);
    auto Dfs = [&](auto&& self, int j) -> void {
        vis[j] = 1;
        for (auto node : adj[j]) {
            if (vis[node]) continue;
            dist[node] = dist[j] + 1;
            self(self, node);
        }
    };
    Dfs(Dfs, i);

    if (dist[ai] > diameter) {
        bi = i;
        diameter = dist[ai];
    } else if (dist[bi] > diameter) {
        ai = i;
        diameter = dist[bi];
    }

    if (i >= N - 28) {
        auto randomize = [&](int x) -> int {
            return (x + id[i - (N - 28)]) % 5;
        };

        if (Abit >= 14) Aknown = true;
        if (Bbit >= 14) Bknown = true;

        if (Aknown && Bknown) {
            if (ai == i) {
                return randomize(1);
            } else if (bi == i) {
                return randomize(2);
            }
            return randomize(0);
        }

        if (!Aknown && !Bknown) {
            if (ai == i) {
                Aknown = true;
                return randomize(2);
            } 
            if (bi == i) {
                Bknown = true;
                return randomize(3);
            }

            return randomize(((ai & (1 << Abit++)) ? 1 : 0));
        }

        if (ai == i) {
            if (!Aknown) {
                Aknown = true;
                return randomize(4);
            }
            return randomize((2 | ((bi & (1 << Bbit++)) ? 1 : 0)));
        } else if (bi == i) {
            if (!Bknown) {
                Bknown = true;
                return randomize(4);
            } 
            return randomize((2 | ((ai & (1 << Abit++)) ? 1 : 0)));
        }

        if (!Aknown) {
            return randomize(((ai & (1 << Abit++)) ? 1 : 0));
        } else if (!Bknown) {
            return randomize(((bi & (1 << Bbit++)) ? 1 : 0));
        }

        return randomize(0);
    }

    return 0;
}

pair<int, int> longest_path(vector<int> S) {
    int A = 0, B = 0;
    bool isAknown = false;
    bool isBknown = false;

    int bitA = 0;
    int bitB = 0;


    for (int i = N - 28; i < N; i++) {
        auto unrandomize = [&](int x) -> int {
            return (5 + x - id[i-(N-28)]) % 5;
        };
        S[i] = unrandomize(S[i]);

        if (bitA >= 14) isAknown = true;
        if (bitB >= 14) isBknown = true;

        if (isAknown && isBknown) {
            if (S[i] == 1) {
                A = i;
            } else if (S[i] == 2) {
                B = i;
            } else {
                assert(S[i] == 0);
            }
            continue;
        }

        if (!isAknown && !isBknown) {
            if (S[i] == 2) {
                A = i;
                isAknown = true;
                continue;
            }
            if (S[i] == 3) {
                B = i;
                isBknown = true;
                continue;
            }

            A |= (S[i] << bitA++);
            continue;
        }

        if (S[i] == 4) {
            if (!isBknown) {
                isBknown = true;
                B = i;
            } else {
                isAknown = true;
                A = i;
            }
            continue;
        }

        if (S[i] >= 2) {
            S[i] -= 2;
            if (isAknown) {
                A = i;
            } else {
                B = i;
            }
        }

        if (!isAknown) {
            A |= (S[i] << bitA++);
        } else if (!isBknown) {
            B |= (S[i] << bitB++);
        }
    }

    return {A, B};
}

//#include "grader.cpp"

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