답안 #54961 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54961	2018-07-05T14:41:06 Z	fallingstar	고대 책들 (IOI17_books)	C++14	50 / 100	375 ms	118764 KB

books

#include "books.h"
#include <algorithm>

#define long long long

using namespace std;

const int N = 1e6 + 2;

vector<int> p;
int gr[N], boundL[N], boundR[N];

void Dfs(int u) 
{ 
    if (gr[p[u]] == -1) 
    {
        gr[p[u]] = gr[u];
        Dfs(p[u]);         
    }
    boundL[gr[u]] = min(boundL[gr[u]], u);
    boundR[gr[u]] = max(boundR[gr[u]], u);
}

long minimum_walk(std::vector<int> p_, int s) {
    p = p_;
	int n = p.size(), L = 0, R = n - 1;
    while (R > s && p[R] == R) --R;
    while (L < s && p[L] == L) ++L;
    
    fill(gr + L, gr + R + 1, -1);
    for (int i = 0; i < n; ++i)
        boundL[i] = n, boundR[i] = 0;
    
    long ans = 0;
    for (int i = L; i <= R; ++i)
    {
        if (gr[i] == -1) gr[i] = i, Dfs(i);
        ans += abs(i - p[i]);
    }

    int curL = s, curR = s;
    while (curL != L || curR != R)
    {
        int newL, newR;
        if (curL > boundL[gr[s]] || curR < boundR[gr[s]])     // first time
        {
            newL = boundL[gr[s]], newR = boundR[gr[s]];
        }
        else 
        {
            ans += 2;
            newL = curL - (curL > L), newR = curR + (curR < R);            
        }
        while (curL != newL || curR != newR)
        {
            if (curL > newL)
            {
                --curL;
                newL = min(newL, boundL[gr[curL]]);
                newR = max(newR, boundR[gr[curL]]);
            }
            else 
            {
                ++curR;
                newL = min(newL, boundL[gr[curR]]);
                newR = max(newR, boundR[gr[curR]]);
            }
        }
    }
    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	528 KB	Output is correct
4	Correct	2 ms	528 KB	Output is correct
5	Correct	2 ms	528 KB	Output is correct
6	Correct	2 ms	528 KB	Output is correct
7	Correct	2 ms	528 KB	Output is correct
8	Correct	2 ms	528 KB	Output is correct
9	Correct	2 ms	532 KB	Output is correct
10	Correct	2 ms	540 KB	Output is correct
11	Correct	3 ms	672 KB	Output is correct
12	Correct	2 ms	672 KB	Output is correct
13	Correct	2 ms	672 KB	Output is correct
14	Correct	3 ms	672 KB	Output is correct
15	Correct	2 ms	672 KB	Output is correct
16	Correct	2 ms	680 KB	Output is correct
17	Correct	2 ms	680 KB	Output is correct
18	Correct	2 ms	740 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	528 KB	Output is correct
4	Correct	2 ms	528 KB	Output is correct
5	Correct	2 ms	528 KB	Output is correct
6	Correct	2 ms	528 KB	Output is correct
7	Correct	2 ms	528 KB	Output is correct
8	Correct	2 ms	528 KB	Output is correct
9	Correct	2 ms	532 KB	Output is correct
10	Correct	2 ms	540 KB	Output is correct
11	Correct	3 ms	672 KB	Output is correct
12	Correct	2 ms	672 KB	Output is correct
13	Correct	2 ms	672 KB	Output is correct
14	Correct	3 ms	672 KB	Output is correct
15	Correct	2 ms	672 KB	Output is correct
16	Correct	2 ms	680 KB	Output is correct
17	Correct	2 ms	680 KB	Output is correct
18	Correct	2 ms	740 KB	Output is correct
19	Correct	2 ms	744 KB	Output is correct
20	Correct	2 ms	748 KB	Output is correct
21	Correct	3 ms	752 KB	Output is correct
22	Correct	2 ms	756 KB	Output is correct
23	Correct	2 ms	780 KB	Output is correct
24	Correct	3 ms	784 KB	Output is correct
25	Correct	2 ms	788 KB	Output is correct
26	Correct	3 ms	792 KB	Output is correct
27	Correct	2 ms	796 KB	Output is correct
28	Correct	3 ms	800 KB	Output is correct
29	Correct	2 ms	848 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	528 KB	Output is correct
4	Correct	2 ms	528 KB	Output is correct
5	Correct	2 ms	528 KB	Output is correct
6	Correct	2 ms	528 KB	Output is correct
7	Correct	2 ms	528 KB	Output is correct
8	Correct	2 ms	528 KB	Output is correct
9	Correct	2 ms	532 KB	Output is correct
10	Correct	2 ms	540 KB	Output is correct
11	Correct	3 ms	672 KB	Output is correct
12	Correct	2 ms	672 KB	Output is correct
13	Correct	2 ms	672 KB	Output is correct
14	Correct	3 ms	672 KB	Output is correct
15	Correct	2 ms	672 KB	Output is correct
16	Correct	2 ms	680 KB	Output is correct
17	Correct	2 ms	680 KB	Output is correct
18	Correct	2 ms	740 KB	Output is correct
19	Correct	2 ms	744 KB	Output is correct
20	Correct	2 ms	748 KB	Output is correct
21	Correct	3 ms	752 KB	Output is correct
22	Correct	2 ms	756 KB	Output is correct
23	Correct	2 ms	780 KB	Output is correct
24	Correct	3 ms	784 KB	Output is correct
25	Correct	2 ms	788 KB	Output is correct
26	Correct	3 ms	792 KB	Output is correct
27	Correct	2 ms	796 KB	Output is correct
28	Correct	3 ms	800 KB	Output is correct
29	Correct	2 ms	848 KB	Output is correct
30	Correct	375 ms	55396 KB	Output is correct
31	Correct	333 ms	55396 KB	Output is correct
32	Correct	167 ms	55396 KB	Output is correct
33	Correct	188 ms	55396 KB	Output is correct
34	Correct	207 ms	58000 KB	Output is correct
35	Correct	183 ms	64812 KB	Output is correct
36	Correct	237 ms	71492 KB	Output is correct
37	Correct	173 ms	78304 KB	Output is correct
38	Correct	233 ms	85220 KB	Output is correct
39	Correct	269 ms	91832 KB	Output is correct
40	Correct	232 ms	99668 KB	Output is correct
41	Correct	289 ms	115780 KB	Output is correct
42	Correct	254 ms	116884 KB	Output is correct
43	Correct	204 ms	118764 KB	Output is correct

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	118764 KB	Output is correct
2	Correct	3 ms	118764 KB	Output is correct
3	Correct	2 ms	118764 KB	Output is correct
4	Incorrect	3 ms	118764 KB	3rd lines differ - on the 1st token, expected: '2094', found: '1592'
5	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	528 KB	Output is correct
4	Correct	2 ms	528 KB	Output is correct
5	Correct	2 ms	528 KB	Output is correct
6	Correct	2 ms	528 KB	Output is correct
7	Correct	2 ms	528 KB	Output is correct
8	Correct	2 ms	528 KB	Output is correct
9	Correct	2 ms	532 KB	Output is correct
10	Correct	2 ms	540 KB	Output is correct
11	Correct	3 ms	672 KB	Output is correct
12	Correct	2 ms	672 KB	Output is correct
13	Correct	2 ms	672 KB	Output is correct
14	Correct	3 ms	672 KB	Output is correct
15	Correct	2 ms	672 KB	Output is correct
16	Correct	2 ms	680 KB	Output is correct
17	Correct	2 ms	680 KB	Output is correct
18	Correct	2 ms	740 KB	Output is correct
19	Correct	2 ms	744 KB	Output is correct
20	Correct	2 ms	748 KB	Output is correct
21	Correct	3 ms	752 KB	Output is correct
22	Correct	2 ms	756 KB	Output is correct
23	Correct	2 ms	780 KB	Output is correct
24	Correct	3 ms	784 KB	Output is correct
25	Correct	2 ms	788 KB	Output is correct
26	Correct	3 ms	792 KB	Output is correct
27	Correct	2 ms	796 KB	Output is correct
28	Correct	3 ms	800 KB	Output is correct
29	Correct	2 ms	848 KB	Output is correct
30	Correct	375 ms	55396 KB	Output is correct
31	Correct	333 ms	55396 KB	Output is correct
32	Correct	167 ms	55396 KB	Output is correct
33	Correct	188 ms	55396 KB	Output is correct
34	Correct	207 ms	58000 KB	Output is correct
35	Correct	183 ms	64812 KB	Output is correct
36	Correct	237 ms	71492 KB	Output is correct
37	Correct	173 ms	78304 KB	Output is correct
38	Correct	233 ms	85220 KB	Output is correct
39	Correct	269 ms	91832 KB	Output is correct
40	Correct	232 ms	99668 KB	Output is correct
41	Correct	289 ms	115780 KB	Output is correct
42	Correct	254 ms	116884 KB	Output is correct
43	Correct	204 ms	118764 KB	Output is correct
44	Correct	3 ms	118764 KB	Output is correct
45	Correct	3 ms	118764 KB	Output is correct
46	Correct	2 ms	118764 KB	Output is correct
47	Incorrect	3 ms	118764 KB	3rd lines differ - on the 1st token, expected: '2094', found: '1592'
48	Halted	0 ms	0 KB	-

답안 #54961

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