Submission #390121

#	Time	Username	Problem	Language	Result	Execution time	Memory
390121		KoD	Space Pirate (JOI14_space_pirate)	C++17	47 / 100	1783 ms	115812 KiB

space_pirate

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

using ll = long long;

constexpr ll INF = std::numeric_limits<ll>::max();

int main() {
    int N;
    ll K;
    std::cin >> N >> K;
    Vec<int> A(N);
    for (auto &x: A) {
        std::cin >> x;
        x -= 1;
    }

    if (N <= 3000) {
        Vec<Vec<int>> goes(N);
        Vec<Vec<ll>> ord(N, Vec<ll>(N, INF));
        for (int u = 0; u < N; ++u) {
            ord[u][u] = 0;
            goes[u].push_back(u);
            while (ord[u][A[goes[u].back()]] == INF) {
                const auto v = A[goes[u].back()];
                const auto k = (int) goes[u].size();
                ord[u][v] = k;
                goes[u].push_back(v);
            }
        }
        
        const auto last = [&](const int u) {
            return goes[u].back();
        };
        const auto connects = [&](const int u) {
            return A[last(u)];
        };
        const auto loop = [&](const int u) {
            return ord[u][last(u)] - ord[u][connects(u)] + 1;
        };
        const auto kth = [&](const int u, const ll k) {
            if (k < (int) goes[u].size()) {
                return goes[u][k];
            }
            else {
                const auto rem = (k - (int) goes[u].size()) % loop(u);
                return goes[u][ord[u][connects(u)] + rem];
            }
        };

        Vec<int> ans(N);
        for (int a = 0; a < N; ++a) {
            for (int b = 0; b < N; ++b) {
                if (ord[0][a] >= K) {
                    ans[kth(0, K)] += 1;
                }
                else {
                    const auto rem = K - ord[0][a] - 1;
                    if (ord[b][a] >= rem) {
                        ans[kth(b, rem)] += 1;
                    }
                    else {
                        const auto idx = (rem - ord[b][a] - 1) % (ord[b][a] + 1);
                        ans[kth(b, idx)] += 1;
                    }
                }
            }
        }

        for (const auto x: ans) {
            std::cout << x << '\n';
        }
    }

    else {

    }
}

• Subtask 1: 10 / 10
• Subtask 2: 37 / 37
• Subtask 3: 0 / 33
• Subtask 4: 0 / 20