Submission #132458

#	Time	Username	Problem	Language	Result	Execution time	Memory
132458		egorlifar	Space Pirate (JOI14_space_pirate)	C++17	80 / 100	451 ms	173092 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 = 100028;

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

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;
}


int fk[3028][3028];
int sk[3028][3028];


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //read(FILENAME);
    cin >> n >> k;
    vector<int> ggg;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
        jump[i][0] = a[i];
        ggg.pb(a[i]);
    }
    sort(all(ggg));
    ggg.resize(distance(ggg.begin(), unique(all(ggg))));
    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];
    }
    int cur1 = 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];
        }
    }
    if (sz(ggg) == n) {
        for (int i = 0; i < sz(g); i++) {
            if (k - i >= 0) {
                cnt[g[i]]++;
            }
        }
        for (int i = 1; i <= sz(g) - 1; i++) {
            long long kk = k - 1;
            long long st = 0;
            while (st < min(1LL * sz(g), k) && kk >= 0) {
                long long pos = (st + i + kk % (sz(g) - i + 1)) % sz(g);
                long long gg = min(min(1LL * sz(g), k) - st, kk % (sz(g) - i + 1) + 1);
                cnt[g[pos]] += gg;
                st += kk % (sz(g) - i + 1);
                kk -= kk % (sz(g) - i + 1);
                st++;
                kk--;
            }
        }
        for (int i = 0; i < n; i++) {
            if (used[i] != uk) {
                cnt[i] += min(1LL * sz(g), k);
            }
        }
        for (int i = 0; i < n; i++) {
            cout << cnt[i] << '\n';
        }
        return 0;
    }
    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][j] = f;
            f = a[f];
        }
    }
    for (int i = 0; i < n; i++) {
        int t = go(i, k - sz(g));
        for (int f = 0; f < sz(g); f++) {
            sk[i][f] = t;
            t = a[t];
        }
    }
    long long ks = k;
    for (int j = 0; j < n; j++) {
        k = ks;
        for (int i = 0; i < sz(g); i++) {
            if (j == a[g[i]]) {
                cnt[cur]++;
            } else {
                if (k == 0) {
                    cnt[g[i]]++;
                    continue;
                }
                if (can[j][g[i]]) {
                    int fs = dist[j][g[i]] + 1;
                    long long kk = k;
                    kk--;
                    kk %= fs;
                    if (kk == 0) {
                        cnt[j]++;
                    } else {
                        cnt[fk[j][kk]]++;
                    }
                } else {
                    cnt[sk[j][k - 1 - (ks - sz(g))]]++;
                }
            }
            k--;
        }
    }
    for (int i = 0; i < n; i++) {
        cout << cnt[i] << '\n';
    }
    return 0;
}

Compilation message (stderr)

space_pirate.cpp: In function 'int main()':
space_pirate.cpp:112:9: warning: unused variable 'cur1' [-Wunused-variable]
     int cur1 = cur;
         ^~~~

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