Submission #42475

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
42475	2018-02-27T15:50:21 Z	yusufake	Ancient Books (IOI17_books)	C++	50 / 100	278 ms	118664 KB

books

#include<bits/stdc++.h>
 
using namespace std;
 
#define _   int v, int tl, int tr, int l, int r
#define tm  (tl+tr >> 1)
#define sol v+v,tl,tm,l,r
#define sag v+v+1,tm+1,tr,l,r
 
#define mp make_pair
#define pb push_back
#define st first
#define nd second
 
typedef long long ll;
typedef pair < ll , ll > pp;
 
const int mod = 1e9 + 7;
const int N   = 1e6 + 6;
 
ll H[N],A[N],n,i,j,l,r,t,x,a,b;
 
ll minimum_walk(vector < int > p , int s){
    x = t = a = b = 0;
	n = p.size();
    for(i=0;i<n;i++) H[i] = 0;
	for(i=0;i<n;i++){
		x += abs(p[i] - i);
		if(H[i]) continue;
		l = r = i;
		for(j=i; !H[j] ; j = p[j]){
			H[j] = 1;
			l = min(l , j);
			r = max(r , j);
		}
		A[l] = r;
	}
    
	for(t=r=-1,i=0;i<n;i++){
		if(i > r) t++;
        r = max(r , A[i]);
    }
    
    for(i=0;i<n && p[i] == i; i++) a++;
    for(j=n-1;j>=0 && p[j] == j; j--) b++;
        
    if(i == n) return 0;
    else if(s < i) t -= b+s;
    else if(s > j) t -= a+n-1-s;
    else t -= a+b;
    return x + 2 * t;
    
}	
/*
int main(){
    cout << minimum_walk({1,0,2,3} , 2);
}
*/

Subtask #1

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	248 KB	Output is correct
2	Correct	1 ms	352 KB	Output is correct
3	Correct	1 ms	424 KB	Output is correct
4	Correct	2 ms	428 KB	Output is correct
5	Correct	2 ms	568 KB	Output is correct
6	Correct	1 ms	568 KB	Output is correct
7	Correct	2 ms	568 KB	Output is correct
8	Correct	1 ms	596 KB	Output is correct
9	Correct	2 ms	676 KB	Output is correct
10	Correct	1 ms	680 KB	Output is correct
11	Correct	1 ms	700 KB	Output is correct
12	Correct	1 ms	740 KB	Output is correct
13	Correct	1 ms	744 KB	Output is correct
14	Correct	2 ms	748 KB	Output is correct
15	Correct	1 ms	752 KB	Output is correct
16	Correct	1 ms	756 KB	Output is correct
17	Correct	1 ms	764 KB	Output is correct
18	Correct	1 ms	768 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	248 KB	Output is correct
2	Correct	1 ms	352 KB	Output is correct
3	Correct	1 ms	424 KB	Output is correct
4	Correct	2 ms	428 KB	Output is correct
5	Correct	2 ms	568 KB	Output is correct
6	Correct	1 ms	568 KB	Output is correct
7	Correct	2 ms	568 KB	Output is correct
8	Correct	1 ms	596 KB	Output is correct
9	Correct	2 ms	676 KB	Output is correct
10	Correct	1 ms	680 KB	Output is correct
11	Correct	1 ms	700 KB	Output is correct
12	Correct	1 ms	740 KB	Output is correct
13	Correct	1 ms	744 KB	Output is correct
14	Correct	2 ms	748 KB	Output is correct
15	Correct	1 ms	752 KB	Output is correct
16	Correct	1 ms	756 KB	Output is correct
17	Correct	1 ms	764 KB	Output is correct
18	Correct	1 ms	768 KB	Output is correct
19	Correct	1 ms	772 KB	Output is correct
20	Correct	2 ms	780 KB	Output is correct
21	Correct	2 ms	780 KB	Output is correct
22	Correct	1 ms	784 KB	Output is correct
23	Correct	2 ms	884 KB	Output is correct
24	Correct	1 ms	884 KB	Output is correct
25	Correct	2 ms	884 KB	Output is correct
26	Correct	1 ms	884 KB	Output is correct
27	Correct	2 ms	884 KB	Output is correct
28	Correct	1 ms	884 KB	Output is correct
29	Correct	2 ms	884 KB	Output is correct

Subtask #3

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	248 KB	Output is correct
2	Correct	1 ms	352 KB	Output is correct
3	Correct	1 ms	424 KB	Output is correct
4	Correct	2 ms	428 KB	Output is correct
5	Correct	2 ms	568 KB	Output is correct
6	Correct	1 ms	568 KB	Output is correct
7	Correct	2 ms	568 KB	Output is correct
8	Correct	1 ms	596 KB	Output is correct
9	Correct	2 ms	676 KB	Output is correct
10	Correct	1 ms	680 KB	Output is correct
11	Correct	1 ms	700 KB	Output is correct
12	Correct	1 ms	740 KB	Output is correct
13	Correct	1 ms	744 KB	Output is correct
14	Correct	2 ms	748 KB	Output is correct
15	Correct	1 ms	752 KB	Output is correct
16	Correct	1 ms	756 KB	Output is correct
17	Correct	1 ms	764 KB	Output is correct
18	Correct	1 ms	768 KB	Output is correct
19	Correct	1 ms	772 KB	Output is correct
20	Correct	2 ms	780 KB	Output is correct
21	Correct	2 ms	780 KB	Output is correct
22	Correct	1 ms	784 KB	Output is correct
23	Correct	2 ms	884 KB	Output is correct
24	Correct	1 ms	884 KB	Output is correct
25	Correct	2 ms	884 KB	Output is correct
26	Correct	1 ms	884 KB	Output is correct
27	Correct	2 ms	884 KB	Output is correct
28	Correct	1 ms	884 KB	Output is correct
29	Correct	2 ms	884 KB	Output is correct
30	Correct	213 ms	23164 KB	Output is correct
31	Correct	278 ms	30048 KB	Output is correct
32	Correct	164 ms	44504 KB	Output is correct
33	Correct	154 ms	51216 KB	Output is correct
34	Correct	152 ms	58032 KB	Output is correct
35	Correct	158 ms	64980 KB	Output is correct
36	Correct	153 ms	71520 KB	Output is correct
37	Correct	156 ms	78264 KB	Output is correct
38	Correct	166 ms	82508 KB	Output is correct
39	Correct	191 ms	88556 KB	Output is correct
40	Correct	178 ms	91840 KB	Output is correct
41	Correct	194 ms	97516 KB	Output is correct
42	Correct	198 ms	104504 KB	Output is correct
43	Correct	161 ms	118664 KB	Output is correct

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	118664 KB	3rd lines differ - on the 1st token, expected: '3304', found: '2744'
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	248 KB	Output is correct
2	Correct	1 ms	352 KB	Output is correct
3	Correct	1 ms	424 KB	Output is correct
4	Correct	2 ms	428 KB	Output is correct
5	Correct	2 ms	568 KB	Output is correct
6	Correct	1 ms	568 KB	Output is correct
7	Correct	2 ms	568 KB	Output is correct
8	Correct	1 ms	596 KB	Output is correct
9	Correct	2 ms	676 KB	Output is correct
10	Correct	1 ms	680 KB	Output is correct
11	Correct	1 ms	700 KB	Output is correct
12	Correct	1 ms	740 KB	Output is correct
13	Correct	1 ms	744 KB	Output is correct
14	Correct	2 ms	748 KB	Output is correct
15	Correct	1 ms	752 KB	Output is correct
16	Correct	1 ms	756 KB	Output is correct
17	Correct	1 ms	764 KB	Output is correct
18	Correct	1 ms	768 KB	Output is correct
19	Correct	1 ms	772 KB	Output is correct
20	Correct	2 ms	780 KB	Output is correct
21	Correct	2 ms	780 KB	Output is correct
22	Correct	1 ms	784 KB	Output is correct
23	Correct	2 ms	884 KB	Output is correct
24	Correct	1 ms	884 KB	Output is correct
25	Correct	2 ms	884 KB	Output is correct
26	Correct	1 ms	884 KB	Output is correct
27	Correct	2 ms	884 KB	Output is correct
28	Correct	1 ms	884 KB	Output is correct
29	Correct	2 ms	884 KB	Output is correct
30	Correct	213 ms	23164 KB	Output is correct
31	Correct	278 ms	30048 KB	Output is correct
32	Correct	164 ms	44504 KB	Output is correct
33	Correct	154 ms	51216 KB	Output is correct
34	Correct	152 ms	58032 KB	Output is correct
35	Correct	158 ms	64980 KB	Output is correct
36	Correct	153 ms	71520 KB	Output is correct
37	Correct	156 ms	78264 KB	Output is correct
38	Correct	166 ms	82508 KB	Output is correct
39	Correct	191 ms	88556 KB	Output is correct
40	Correct	178 ms	91840 KB	Output is correct
41	Correct	194 ms	97516 KB	Output is correct
42	Correct	198 ms	104504 KB	Output is correct
43	Correct	161 ms	118664 KB	Output is correct
44	Incorrect	1 ms	118664 KB	3rd lines differ - on the 1st token, expected: '3304', found: '2744'
45	Halted	0 ms	0 KB	-