oj.uz

Submission #51735

# Submission time Handle Problem Language Result Execution time Memory
51735 2018-06-20T13:59:48 Z Costin Andrei Oncescu(#1294) Space Pirate (JOI14_space_pirate) C++11
47 / 100
 1229 ms 80432 KB 
#include<bits/stdc++.h>

using namespace std;

int nr, N, repCyc[3009], lin[3009], col[3009], p[3009], ans[3009];
long long K;
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 main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %lld", &N, &K);
for (int i=1; i<=N; i++)
    scanf ("%d", &p[i]);
init ();
int standardEnd = standardJump (1, K);
for (int a=1; a<=N; a++)
    for (int b=1; b<=N; b++)
    {
        if (a == 5 && b == 2)
            a = 5;
        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 ("%d\n", ans[i]);
return 0;
}

Compilation message

space_pirate.cpp: In function 'int main()':
space_pirate.cpp:62: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:64: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 1640 KB Output is correct
3 Correct 3 ms 1716 KB Output is correct
4 Correct 3 ms 1716 KB Output is correct
5 Correct 3 ms 1724 KB Output is correct
6 Correct 4 ms 1724 KB Output is correct
7 Correct 4 ms 1852 KB Output is correct
8 Correct 4 ms 1852 KB Output is correct
9 Correct 3 ms 1852 KB Output is correct
10 Correct 3 ms 1852 KB Output is correct
11 Correct 2 ms 1852 KB Output is correct
12 Correct 4 ms 1856 KB Output is correct
13 Correct 3 ms 1856 KB Output is correct
14 Correct 3 ms 1956 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 1640 KB Output is correct
3 Correct 3 ms 1716 KB Output is correct
4 Correct 3 ms 1716 KB Output is correct
5 Correct 3 ms 1724 KB Output is correct
6 Correct 4 ms 1724 KB Output is correct
7 Correct 4 ms 1852 KB Output is correct
8 Correct 4 ms 1852 KB Output is correct
9 Correct 3 ms 1852 KB Output is correct
10 Correct 3 ms 1852 KB Output is correct
11 Correct 2 ms 1852 KB Output is correct
12 Correct 4 ms 1856 KB Output is correct
13 Correct 3 ms 1856 KB Output is correct
14 Correct 3 ms 1956 KB Output is correct
15 Correct 134 ms 57724 KB Output is correct
16 Correct 70 ms 57724 KB Output is correct
17 Correct 142 ms 58000 KB Output is correct
18 Correct 437 ms 80288 KB Output is correct
19 Correct 242 ms 80288 KB Output is correct
20 Correct 635 ms 80288 KB Output is correct
21 Correct 1120 ms 80288 KB Output is correct
22 Correct 630 ms 80288 KB Output is correct
23 Correct 1229 ms 80288 KB Output is correct
24 Correct 565 ms 80288 KB Output is correct
25 Correct 69 ms 80288 KB Output is correct
26 Correct 454 ms 80432 KB Output is correct
27 Correct 561 ms 80432 KB Output is correct
28 Correct 561 ms 80432 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5 ms 80432 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1640 KB Output is correct
3 Correct 3 ms 1716 KB Output is correct
4 Correct 3 ms 1716 KB Output is correct
5 Correct 3 ms 1724 KB Output is correct
6 Correct 4 ms 1724 KB Output is correct
7 Correct 4 ms 1852 KB Output is correct
8 Correct 4 ms 1852 KB Output is correct
9 Correct 3 ms 1852 KB Output is correct
10 Correct 3 ms 1852 KB Output is correct
11 Correct 2 ms 1852 KB Output is correct
12 Correct 4 ms 1856 KB Output is correct
13 Correct 3 ms 1856 KB Output is correct
14 Correct 3 ms 1956 KB Output is correct
15 Correct 134 ms 57724 KB Output is correct
16 Correct 70 ms 57724 KB Output is correct
17 Correct 142 ms 58000 KB Output is correct
18 Correct 437 ms 80288 KB Output is correct
19 Correct 242 ms 80288 KB Output is correct
20 Correct 635 ms 80288 KB Output is correct
21 Correct 1120 ms 80288 KB Output is correct
22 Correct 630 ms 80288 KB Output is correct
23 Correct 1229 ms 80288 KB Output is correct
24 Correct 565 ms 80288 KB Output is correct
25 Correct 69 ms 80288 KB Output is correct
26 Correct 454 ms 80432 KB Output is correct
27 Correct 561 ms 80432 KB Output is correct
28 Correct 561 ms 80432 KB Output is correct
29 Execution timed out 5 ms 80432 KB Time limit exceeded (wall clock)
30 Halted 0 ms 0 KB -