oj.uz

Submission #51738

# Submission time Handle Problem Language Result Execution time Memory
51738 2018-06-20T16:01:33 Z SpaimaCarpatilor Space Pirate (JOI14_space_pirate) C++17
80 / 100
 1256 ms 80440 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1768 KB Output is correct
3 Correct 3 ms 1768 KB Output is correct
4 Correct 4 ms 1768 KB Output is correct
5 Correct 3 ms 1768 KB Output is correct
6 Correct 3 ms 1768 KB Output is correct
7 Correct 4 ms 1768 KB Output is correct
8 Correct 3 ms 1768 KB Output is correct
9 Correct 3 ms 1768 KB Output is correct
10 Correct 3 ms 1768 KB Output is correct
11 Correct 3 ms 1824 KB Output is correct
12 Correct 3 ms 1872 KB Output is correct
13 Correct 3 ms 1872 KB Output is correct
14 Correct 3 ms 1872 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1768 KB Output is correct
3 Correct 3 ms 1768 KB Output is correct
4 Correct 4 ms 1768 KB Output is correct
5 Correct 3 ms 1768 KB Output is correct
6 Correct 3 ms 1768 KB Output is correct
7 Correct 4 ms 1768 KB Output is correct
8 Correct 3 ms 1768 KB Output is correct
9 Correct 3 ms 1768 KB Output is correct
10 Correct 3 ms 1768 KB Output is correct
11 Correct 3 ms 1824 KB Output is correct
12 Correct 3 ms 1872 KB Output is correct
13 Correct 3 ms 1872 KB Output is correct
14 Correct 3 ms 1872 KB Output is correct
15 Correct 127 ms 57700 KB Output is correct
16 Correct 71 ms 57700 KB Output is correct
17 Correct 142 ms 57972 KB Output is correct
18 Correct 467 ms 80440 KB Output is correct
19 Correct 255 ms 80440 KB Output is correct
20 Correct 645 ms 80440 KB Output is correct
21 Correct 1193 ms 80440 KB Output is correct
22 Correct 644 ms 80440 KB Output is correct
23 Correct 1256 ms 80440 KB Output is correct
24 Correct 550 ms 80440 KB Output is correct
25 Correct 72 ms 80440 KB Output is correct
26 Correct 439 ms 80440 KB Output is correct
27 Correct 561 ms 80440 KB Output is correct
28 Correct 523 ms 80440 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 80440 KB Output is correct
2 Correct 38 ms 80440 KB Output is correct
3 Correct 33 ms 80440 KB Output is correct
4 Correct 31 ms 80440 KB Output is correct
5 Correct 38 ms 80440 KB Output is correct
6 Correct 35 ms 80440 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1768 KB Output is correct
3 Correct 3 ms 1768 KB Output is correct
4 Correct 4 ms 1768 KB Output is correct
5 Correct 3 ms 1768 KB Output is correct
6 Correct 3 ms 1768 KB Output is correct
7 Correct 4 ms 1768 KB Output is correct
8 Correct 3 ms 1768 KB Output is correct
9 Correct 3 ms 1768 KB Output is correct
10 Correct 3 ms 1768 KB Output is correct
11 Correct 3 ms 1824 KB Output is correct
12 Correct 3 ms 1872 KB Output is correct
13 Correct 3 ms 1872 KB Output is correct
14 Correct 3 ms 1872 KB Output is correct
15 Correct 127 ms 57700 KB Output is correct
16 Correct 71 ms 57700 KB Output is correct
17 Correct 142 ms 57972 KB Output is correct
18 Correct 467 ms 80440 KB Output is correct
19 Correct 255 ms 80440 KB Output is correct
20 Correct 645 ms 80440 KB Output is correct
21 Correct 1193 ms 80440 KB Output is correct
22 Correct 644 ms 80440 KB Output is correct
23 Correct 1256 ms 80440 KB Output is correct
24 Correct 550 ms 80440 KB Output is correct
25 Correct 72 ms 80440 KB Output is correct
26 Correct 439 ms 80440 KB Output is correct
27 Correct 561 ms 80440 KB Output is correct
28 Correct 523 ms 80440 KB Output is correct
29 Correct 29 ms 80440 KB Output is correct
30 Correct 38 ms 80440 KB Output is correct
31 Correct 33 ms 80440 KB Output is correct
32 Correct 31 ms 80440 KB Output is correct
33 Correct 38 ms 80440 KB Output is correct
34 Correct 35 ms 80440 KB Output is correct
35 Runtime error 23 ms 80440 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Halted 0 ms 0 KB -