답안 #46900 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46900	2018-04-24T16:00:36 Z	SpaimaCarpatilor	고대 책들 (IOI17_books)	C++17	50 / 100	244 ms	111996 KB

books

#include "books.h"
#include<bits/stdc++.h>

using namespace std;

int N, S, p[1000009], nxt[1000009];
bool ap[1000009];

long long minimum_walk (vector < int > pp, int ss)
{
    N = pp.size (), S = ss + 1;
    for (int i=1; i<=N; i++)
        p[i] = pp[i - 1] + 1;
    for (int i=1; i<=N; i++)
        if (ap[i] == 0)
        {
            int j = p[i], maxRight = i;
            ap[i] = 1;
            while (j != i)
                ap[j] = 1, maxRight = max (maxRight, j), j = p[j];
            nxt[i] = maxRight, j = p[i];
            while (j != i)
                nxt[j] = maxRight, j = p[j];
        }
    long long ans = 0;
    for (int i=1; i<=N; i++)
    {
        int curr = i - p[i];
        if (curr < 0) curr = -curr;
        ans += curr;
    }
    for (int i=1; i<N; i++)
        if (nxt[i] > nxt[i + 1])
            nxt[i + 1] = nxt[i];
    int target = 0;
    for (int i=1; i<=N; i++)
        if (p[i] != i)
            target = i;
    int pos = 1;
    while (pos < target)
    {
        if (pos == nxt[pos]) ans += 2, pos ++;
        else pos = nxt[pos];
    }
    return ans;
}

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	360 KB	Output is correct
3	Correct	2 ms	472 KB	Output is correct
4	Correct	2 ms	620 KB	Output is correct
5	Correct	2 ms	660 KB	Output is correct
6	Correct	2 ms	660 KB	Output is correct
7	Correct	2 ms	660 KB	Output is correct
8	Correct	2 ms	660 KB	Output is correct
9	Correct	2 ms	660 KB	Output is correct
10	Correct	2 ms	660 KB	Output is correct
11	Correct	2 ms	660 KB	Output is correct
12	Correct	2 ms	660 KB	Output is correct
13	Correct	2 ms	668 KB	Output is correct
14	Correct	2 ms	668 KB	Output is correct
15	Correct	2 ms	800 KB	Output is correct
16	Correct	2 ms	800 KB	Output is correct
17	Correct	2 ms	824 KB	Output is correct
18	Correct	3 ms	868 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	360 KB	Output is correct
3	Correct	2 ms	472 KB	Output is correct
4	Correct	2 ms	620 KB	Output is correct
5	Correct	2 ms	660 KB	Output is correct
6	Correct	2 ms	660 KB	Output is correct
7	Correct	2 ms	660 KB	Output is correct
8	Correct	2 ms	660 KB	Output is correct
9	Correct	2 ms	660 KB	Output is correct
10	Correct	2 ms	660 KB	Output is correct
11	Correct	2 ms	660 KB	Output is correct
12	Correct	2 ms	660 KB	Output is correct
13	Correct	2 ms	668 KB	Output is correct
14	Correct	2 ms	668 KB	Output is correct
15	Correct	2 ms	800 KB	Output is correct
16	Correct	2 ms	800 KB	Output is correct
17	Correct	2 ms	824 KB	Output is correct
18	Correct	3 ms	868 KB	Output is correct
19	Correct	2 ms	868 KB	Output is correct
20	Correct	2 ms	868 KB	Output is correct
21	Correct	3 ms	868 KB	Output is correct
22	Correct	3 ms	868 KB	Output is correct
23	Correct	3 ms	868 KB	Output is correct
24	Correct	2 ms	868 KB	Output is correct
25	Correct	3 ms	868 KB	Output is correct
26	Correct	2 ms	868 KB	Output is correct
27	Correct	2 ms	868 KB	Output is correct
28	Correct	2 ms	868 KB	Output is correct
29	Correct	2 ms	868 KB	Output is correct

Subtask #3
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	360 KB	Output is correct
3	Correct	2 ms	472 KB	Output is correct
4	Correct	2 ms	620 KB	Output is correct
5	Correct	2 ms	660 KB	Output is correct
6	Correct	2 ms	660 KB	Output is correct
7	Correct	2 ms	660 KB	Output is correct
8	Correct	2 ms	660 KB	Output is correct
9	Correct	2 ms	660 KB	Output is correct
10	Correct	2 ms	660 KB	Output is correct
11	Correct	2 ms	660 KB	Output is correct
12	Correct	2 ms	660 KB	Output is correct
13	Correct	2 ms	668 KB	Output is correct
14	Correct	2 ms	668 KB	Output is correct
15	Correct	2 ms	800 KB	Output is correct
16	Correct	2 ms	800 KB	Output is correct
17	Correct	2 ms	824 KB	Output is correct
18	Correct	3 ms	868 KB	Output is correct
19	Correct	2 ms	868 KB	Output is correct
20	Correct	2 ms	868 KB	Output is correct
21	Correct	3 ms	868 KB	Output is correct
22	Correct	3 ms	868 KB	Output is correct
23	Correct	3 ms	868 KB	Output is correct
24	Correct	2 ms	868 KB	Output is correct
25	Correct	3 ms	868 KB	Output is correct
26	Correct	2 ms	868 KB	Output is correct
27	Correct	2 ms	868 KB	Output is correct
28	Correct	2 ms	868 KB	Output is correct
29	Correct	2 ms	868 KB	Output is correct
30	Correct	231 ms	24144 KB	Output is correct
31	Correct	244 ms	31032 KB	Output is correct
32	Correct	143 ms	37780 KB	Output is correct
33	Correct	154 ms	44412 KB	Output is correct
34	Correct	154 ms	51196 KB	Output is correct
35	Correct	174 ms	57972 KB	Output is correct
36	Correct	161 ms	64776 KB	Output is correct
37	Correct	171 ms	71516 KB	Output is correct
38	Correct	202 ms	78172 KB	Output is correct
39	Correct	182 ms	84988 KB	Output is correct
40	Correct	213 ms	91748 KB	Output is correct
41	Correct	217 ms	98492 KB	Output is correct
42	Correct	214 ms	105256 KB	Output is correct
43	Correct	160 ms	111996 KB	Output is correct

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	111996 KB	3rd lines differ - on the 1st token, expected: '3304', found: '2744'
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	360 KB	Output is correct
3	Correct	2 ms	472 KB	Output is correct
4	Correct	2 ms	620 KB	Output is correct
5	Correct	2 ms	660 KB	Output is correct
6	Correct	2 ms	660 KB	Output is correct
7	Correct	2 ms	660 KB	Output is correct
8	Correct	2 ms	660 KB	Output is correct
9	Correct	2 ms	660 KB	Output is correct
10	Correct	2 ms	660 KB	Output is correct
11	Correct	2 ms	660 KB	Output is correct
12	Correct	2 ms	660 KB	Output is correct
13	Correct	2 ms	668 KB	Output is correct
14	Correct	2 ms	668 KB	Output is correct
15	Correct	2 ms	800 KB	Output is correct
16	Correct	2 ms	800 KB	Output is correct
17	Correct	2 ms	824 KB	Output is correct
18	Correct	3 ms	868 KB	Output is correct
19	Correct	2 ms	868 KB	Output is correct
20	Correct	2 ms	868 KB	Output is correct
21	Correct	3 ms	868 KB	Output is correct
22	Correct	3 ms	868 KB	Output is correct
23	Correct	3 ms	868 KB	Output is correct
24	Correct	2 ms	868 KB	Output is correct
25	Correct	3 ms	868 KB	Output is correct
26	Correct	2 ms	868 KB	Output is correct
27	Correct	2 ms	868 KB	Output is correct
28	Correct	2 ms	868 KB	Output is correct
29	Correct	2 ms	868 KB	Output is correct
30	Correct	231 ms	24144 KB	Output is correct
31	Correct	244 ms	31032 KB	Output is correct
32	Correct	143 ms	37780 KB	Output is correct
33	Correct	154 ms	44412 KB	Output is correct
34	Correct	154 ms	51196 KB	Output is correct
35	Correct	174 ms	57972 KB	Output is correct
36	Correct	161 ms	64776 KB	Output is correct
37	Correct	171 ms	71516 KB	Output is correct
38	Correct	202 ms	78172 KB	Output is correct
39	Correct	182 ms	84988 KB	Output is correct
40	Correct	213 ms	91748 KB	Output is correct
41	Correct	217 ms	98492 KB	Output is correct
42	Correct	214 ms	105256 KB	Output is correct
43	Correct	160 ms	111996 KB	Output is correct
44	Incorrect	2 ms	111996 KB	3rd lines differ - on the 1st token, expected: '3304', found: '2744'
45	Halted	0 ms	0 KB	-

답안 #46900

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 10.0 / 10.0

Subtask #3 28.0 / 28.0

Subtask #4 0 / 20.0

Subtask #5 0 / 30.0

Subtask #1
12.0 / 12.0

Subtask #2
10.0 / 10.0

Subtask #3
28.0 / 28.0

Subtask #4
0 / 20.0

Subtask #5
0 / 30.0