Submission #390148

#	Time	Username	Problem	Language	Result	Execution time	Memory
390148		KoD	Space Pirate (JOI14_space_pirate)	C++17	80 / 100	1734 ms	106268 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() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    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) {
            goes[u].reserve(N);
            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)];
        };

        Vec<ll> loop(N);
        for (int i = 0; i < N; ++i) {
            loop[i] = ord[i][last(i)] - ord[i][connects(i)] + 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 {
        Vec<int> belong(N, -1);
        Vec<Vec<int>> cycles;

        for (int src = 0; src < N; ++src) {
            if (belong[src] == -1) {
                const auto k = (int) cycles.size();
                cycles.push_back({ });
                int u = src;
                while (belong[u] == -1) {
                    belong[u] = k;
                    cycles[k].push_back(u);
                    u = A[u];
                }
            }
        }

        auto& cycle = cycles[0];
        const auto size = (int) cycle.size();
        Vec<ll> ans(N);
        ans[cycle[K % size]] += (ll) (N - size) * N;
        for (int i = 0; i < N; ++i) {
            if (belong[i] != 0) {
                ans[i] += std::min<ll>(size, K);
            }
        }
        for (int i = 0; i < size; ++i) {
            ans[cycle[i]] += 1;
        }
        for (int len = 2; len <= size; ++len) {
            const auto k = K % len;
            ans[cycle[k]] += len - k - 1;
            if (k != 0) {
                ans[cycle[size - len + k]] += k;
            }
        }
        for (int len = 2; len <= size; ++len) {
            for (int k = K % len; k < size; k += len) {
                const ll l = std::max(k, len - 1);
                const ll r = std::min(k + len - 1, size - 1);
                ans[cycle[k]] += r - l + 1;
            }
        }

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

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