Submission #51738

#	Time	Username	Problem	Language	Result	Execution time	Memory
51738		SpaimaCarpatilor	Space Pirate (JOI14_space_pirate)	C++17	80 / 100	1256 ms	80440 KiB

space_pirate

#include<bits/stdc++.h>

using namespace std;

int nr, N, repCyc[3009], lin[3009], col[3009], p[100009];
long long K, ans[100009];
vector < int > cyc[3009];

int aft[3009][3009], d[3009][3009];
bool can[3009][3009];
void init ()
{
    for (int i=1; i<=N; i++)
    {
        int j = p[i], oldJ = i;
        can[i][i] = 1, d[i][i] = 0, aft[i][0] = i;
        while (can[i][j] == 0)
            can[i][j] = 1, d[i][j] = d[i][oldJ] + 1,
            aft[i][d[i][j]] = j, oldJ = p[oldJ], j = p[j];
        repCyc[i] = j;
        if (lin[j] == 0)
        {
            lin[j] = ++nr, col[j] = 0;
            cyc[nr].push_back (j);
            int k = p[j];
            while (k != j)
                col[k] = cyc[nr].size (), lin[k] = nr,
                cyc[nr].push_back (k), k = p[k];
        }
    }
}

int standardJump (int i, long long K)
{
    if (lin[i] > 0)
    {
        int sz = cyc[lin[i]].size (), pos = ((col[i] + K) % sz);
        return cyc[lin[i]][pos];
    }
    int j = repCyc[i], sz = cyc[lin[j]].size (), pos = col[j];
    if (K <= d[i][j]) return aft[i][K];
    K -= d[i][j], K %= sz, pos = (pos + K) % sz;
    return cyc[lin[j]][pos];
}

int brute (int a, int b)
{
    int oldP = p[a], curr = 1;
    p[a] = b;
    long long steps = K;
    while (steps --)
        curr = p[curr];
    p[a] = oldP;
    return curr;
}

int inv[100009], c[100009];
bool isOnMainCycle[100009];
long long s[100009];

void solvePermutation ()
{
    int sz = 1;
    c[0] = 1;
    while (p[c[sz - 1]] != 1)
        c[sz] = p[c[sz - 1]], sz ++;
    for (int i=0; i<sz; i++)
        isOnMainCycle[c[i]] = 1;
    for (int i=1; i<=N; i++)
        if (!isOnMainCycle[i])
            ans[i] = sz;
    for (int length = 1; length <= sz; length ++)
    {
        int r = K % length;
        if (length <= sz)
        {
            int delta = sz + 1 - length;
            ///1)x < y; y = x + delta -> 0 <= x <= sz - 1 - delta
            ///1.a) r <= x    <=>    r  <= x <= sz - 1 - delta   -> r
            if (sz - 1 - delta >= r)
                s[r] += sz - 1 - delta - r + 1;
            ///1.b) r > x    <=>    0 <= x <= min (sz - delta - 1, r - 1)   -> sz - (length - r)
            if (min (sz - delta - 1, r - 1) >= 0)
                s[sz - (length - r)] += min (sz - delta - 1, r - 1) + 1;
        }
        ///2) x >= y; x = y + length - 1 -> 0 <= y <= sz - length
        for (int i=r; i<sz; i+=length)
        {
            ///how many are there with y <= i <= y + length - 1 <= sz - 1
            int rgt = i, lft = i - length + 1;
            if (sz - length < rgt) rgt = sz - length;
            if (lft < 0) lft = 0;
            if (lft <= rgt)
                s[i] += rgt - lft + 1;
        }
/*        for (int i=0; i<sz; i++)
            printf ("%lld ", s[i]);
        printf ("\n");*/
    }
    for (int i=0; i<sz; i++)
        ans[c[i]] += s[i];
    ans[c[K % sz]] += 1LL * (N - sz) * N;
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %lld", &N, &K);
bool isPermuatation = 1;
for (int i=1; i<=N; i++)
{
    scanf ("%d", &p[i]);
    if (inv[p[i]] != 0) isPermuatation = 0;
    else inv[p[i]] = i;
}
if (isPermuatation)
    solvePermutation ();
else
{
    init ();
    int standardEnd = standardJump (1, K);
    for (int a=1; a<=N; a++)
        for (int b=1; b<=N; b++)
        {
            int curr = -1;
            if (!can[1][a]) curr = standardEnd;
            else
            if (!can[1][b])
            {
                if (can[b][a])
                {
                    int sz = d[b][a] + 1, k = ((K - d[1][a] - 1) % sz);
                    curr = standardJump (b, k);
                }
                else
                if (!can[b][a])
                    curr = standardJump (b, K - d[1][a] - 1);
            }
            else
            if (d[1][a] >= d[1][b])
            {
                int sz = d[1][a] - d[1][b] + 1, k = ((K - d[1][b]) % sz);
                curr = standardJump (b, k);
            }
            else
            if (lin[a] == 0)
                curr = standardJump (b, K - d[1][a] - 1);
            else
            {
                assert (lin[b] == lin[a]);
                if (lin[1] == 0)
                {
                    int j = repCyc[1], sz = ((int) cyc[lin[a]].size ()) - (d[1][b] - d[1][a] - 1), k = (K - d[1][j]) % sz;
                    if (k <= d[j][a]) curr = standardJump (j, k);
                    else curr = standardJump (b, k - d[j][a] - 1);
                }
                else
                {
                    int sz = ((int) cyc[lin[a]].size ()) - (d[1][b] - d[1][a] - 1), k = (K % sz);
                    if (k <= d[1][a]) curr = standardJump (1, k);
                    else curr = standardJump (b, k - d[1][a] - 1);
                }
            }
    /*        printf ("%d%c", curr, " \n"[b == N]);
            if (curr != brute (a, b))
            {
                printf ("WA (%d %d) %d instead of %d\n", a, b, curr, brute (a, b));
                return 0;
            }*/
            ans[curr] ++;
        }
}
for (int i=1; i<=N; i++)
    printf ("%lld\n", ans[i]);
return 0;
}

Compilation message (stderr)

space_pirate.cpp: In function 'int main()':
space_pirate.cpp:110:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d %lld", &N, &K);
 ~~~~~~^~~~~~~~~~~~~~~~~~~
space_pirate.cpp:114:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &p[i]);
     ~~~~~~^~~~~~~~~~~~~

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