Submission #390144

#TimeUsernameProblemLanguageResultExecution timeMemory
390144KoDSpace Pirate (JOI14_space_pirate)C++17
47 / 100
1712 ms106276 KiB
#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; ans[cycle[size - len + 1]] += 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'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...