Submission #132295

#	Time	Username	Problem	Language	Result	Execution time	Memory
132295		egorlifar	Space Pirate (JOI14_space_pirate)	C++17	10 / 100	2043 ms	135672 KiB

space_pirate

/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>

using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left224
#define right right224
#define next next224
#define rank rank224
#define prev prev224
#define y1 y1224
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define mp make_pair
const string FILENAME = "input";
const int MAXN = 3028;

int n;
long long k;
int a[MAXN];
int cnt[MAXN];
int uk = 1;
int used[MAXN];
int pos[MAXN];
int jump[MAXN][65];
bool can[MAXN][MAXN];
int dist[MAXN][MAXN];

int go(int i, long long f) {
    for (int s = 62; s >= 0; s--) {
        if (f >= (1LL << s)) {
            f -= 1LL << s;
            i = jump[i][s];
        }
    }
    return i;
}


vector<int> fk[MAXN];
vector<int> sk[MAXN];


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //read(FILENAME);
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
        //cout << i + 1 << ' '  << a[i] + 1 << endl;
        jump[i][0] = a[i];
    }
    int it = 0;
    pos[0] = 0;
    vector<int> g;
    int cur = 0;
    while (used[cur] != uk && it < k) {
        used[cur] = uk;
        pos[cur] = it;
        g.pb(cur);
        it++;
        cur = a[cur];
    }
    assert(sz(g) <= n);
    if (it != k) {
        int f = it - pos[cur];
        for (int jj = 0; jj < (k - it) % f; jj++) {
            cur = a[cur];
        }
    }
    for (int i = 0; i < n; i++) {
        if (used[i] != uk) {
            cnt[cur] += n;
        }
    }
    for (int k = 1; k <= 63; k++) {
        for (int i = 0; i < n; i++) {
            jump[i][k] = jump[jump[i][k - 1]][k - 1];
        }
    }
    for (int i = 0; i < n; i++) {
        int f = i;
        for (int j = 0; j < n; j++) {
            if (can[i][f]) break;
            can[i][f] = true;
            dist[i][f] = j;
            fk[i].pb(f);
            f = a[f];
        }
    }
    //cout << jump[2][0] + 1 << endl;
    for (int i = 0; i < n; i++) {
        int t = go(i, k - sz(g));
        for (int f = 0; f < sz(g); f++) {
            sk[i].pb(t);
            t = a[t];
        }
    }
    long long ks = k;
    for (int i = 0; i < sz(g); i++) {
        for (int j = 0; j < n; j++) {
            if (j == a[g[i]]) {
                cnt[cur]++;
            } else {
                if (can[j][g[i]]) {
                  //  cout << j << ' ' << g[i] << endl;
                    int fs = dist[j][g[i]] + 1;
                   // cout << dist[0][0] << endl;
                    long long kk = k;
                    if (kk == 0) {
                        cnt[g[i]]++;
                        continue;
                    }
                    kk--;
                    kk %= fs;
                    if (kk == 0) {
                        //cout << g[i] << endl;

                        cnt[j]++;
                    } else {

                        cnt[fk[j][kk]]++;
                    }
                } else {
                    if (k == 0) {
                        cnt[g[i]]++;
                        continue;
                    }
                    cnt[sk[j][k - 1 - (ks - sz(g))]]++;
                }
            }
        }
        k--;
    }
    for (int i = 0; i < n; i++) {
        cout << cnt[i] << '\n';
    }
    return 0;
}

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