Submission #258660

#TimeUsernameProblemLanguageResultExecution timeMemory
258660fedoseevtimofeySpace Pirate (JOI14_space_pirate)C++14
10 / 100
2052 ms3456 KiB
#include <iostream> #include <string> #include <vector> #include <queue> #include <deque> #include <stack> #include <set> #include <map> #include <unordered_map> #include <unordered_set> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> #include <random> #include <iomanip> #include <functional> #include <cassert> using namespace std; typedef long long ll; const int K = 60; const int N = 3007; int go[K][N]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); #ifdef LOCAL freopen("input.txt", "r", stdin); #endif int n; ll k; cin >> n >> k; vector <int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; --a[i]; } vector <int> cnt(n); for (int x = 0; x < n; ++x) { for (int i = 0; i < n; ++i) { go[0][i] = a[i]; } go[0][x] = x; for (int i = 1; i < K; ++i) { for (int j = 0; j < n; ++j) { go[i][j] = go[i - 1][go[i - 1][j]]; } } for (int y = 0; y < n; ++y) { ll cur_k = 0; int u = 0; for (int i = K - 1; i >= 0; --i) { if ((k - cur_k) >= (1LL << i)) { if (go[i][u] != x) { u = go[i][u]; cur_k += (1LL << i); } } } if (u != x && cur_k < k && go[0][u] == x) { ++cur_k; u = x; } if (cur_k < k && u == x) { u = y; ++cur_k; } ll cycle_len = 0; for (int i = K - 1; i >= 0; --i) { if ((k - cur_k) >= (1LL << i)) { if (go[i][u] != x) { u = go[i][u]; cur_k += (1LL << i); cycle_len += (1LL << i); } } } if (u != x && cur_k < k && go[0][u] == x) { ++cur_k; ++cycle_len; u = x; } if (cur_k < k && u == x) { ++cur_k; ++cycle_len; u = y; } if (cur_k < k) { ll need = (k - cur_k) % cycle_len; for (int i = K - 1; i >= 0; --i) { if (need & (1LL << i)) { u = go[i][u]; } } } ++cnt[u]; } } for (int i = 0; i < n; ++i) { cout << cnt[i] << '\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...