Submission #355461

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
355461	2021-01-22T13:59:33 Z	amunduzbaev	Ancient Books (IOI17_books)	C++14	42 / 100	266 ms	12780 KB

books

#include "books.h"
 
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
 
#define ll long long
#define sz(x) (int)x.size()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
 
const ll inf = 1e9+7;
const int N = 1e3+5;
const int mod = 1e9+7;
 
int n, dp[N][N], used[N], last, L[N], R[N], in[N];
int endL, endR;

pii ext(int l, int r){
	int new_l = min(L[in[l]], L[in[r]]), new_r = max(R[in[r]], R[in[l]]);
	while(1){
		if(new_l < l) new_l = min(L[in[--l]], new_l), new_r = max(R[in[l]], new_r);
		else if(new_r > r) new_l = min(L[in[++r]], new_l), new_r = max(R[in[r]], new_r);
		else break;
	}return {new_l, new_r};
}

ll fun(int l, int r){
	if(l < endL || r > endR || l < 0 || r > n) return inf;
	//cout<<l<<" "<<r<<"\n";
	pii tt = ext(l, r);
	l = tt.ff, r = tt.ss;
	if(l == endL && r == endR) return 0;
	int &res = dp[l][r];
	if(res != -1) return res;
	res = min(fun(l-1, r), fun(l, r+1)) + 2;
	return res; 
}

ll minimum_walk(vector<int> p, int s) {
	memset(dp, -1, sizeof dp);
	ll res = 0;
	endL = s, endR = s, n = sz(p);
	
	for(int i=0;i<n;i++){
		if(!used[i]){
			int u = i;
			L[last] = u, R[last] = u;
			do{
				used[u] = 1;
				in[u] = last;
				L[last] = min(L[last], u);
				R[last] = max(R[last], u);
				res += abs(p[u] - u);
				u = p[u];
			}while(u != i);
			if(L[last] != R[last]){
				endL = min(L[last], endL);
				endR = max(R[last], endR);
			}
			last++;
		}
	}
	
	return fun(s, s) + res;
}

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4332 KB	Output is correct
2	Correct	3 ms	4332 KB	Output is correct
3	Correct	3 ms	4332 KB	Output is correct
4	Correct	3 ms	4332 KB	Output is correct
5	Correct	3 ms	4332 KB	Output is correct
6	Correct	3 ms	4332 KB	Output is correct
7	Correct	3 ms	4332 KB	Output is correct
8	Correct	3 ms	4332 KB	Output is correct
9	Correct	3 ms	4332 KB	Output is correct
10	Correct	3 ms	4332 KB	Output is correct
11	Correct	3 ms	4332 KB	Output is correct
12	Correct	3 ms	4332 KB	Output is correct
13	Correct	3 ms	4332 KB	Output is correct
14	Correct	3 ms	4332 KB	Output is correct
15	Correct	3 ms	4332 KB	Output is correct
16	Correct	3 ms	4332 KB	Output is correct
17	Correct	3 ms	4332 KB	Output is correct
18	Correct	3 ms	4332 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4332 KB	Output is correct
2	Correct	3 ms	4332 KB	Output is correct
3	Correct	3 ms	4332 KB	Output is correct
4	Correct	3 ms	4332 KB	Output is correct
5	Correct	3 ms	4332 KB	Output is correct
6	Correct	3 ms	4332 KB	Output is correct
7	Correct	3 ms	4332 KB	Output is correct
8	Correct	3 ms	4332 KB	Output is correct
9	Correct	3 ms	4332 KB	Output is correct
10	Correct	3 ms	4332 KB	Output is correct
11	Correct	3 ms	4332 KB	Output is correct
12	Correct	3 ms	4332 KB	Output is correct
13	Correct	3 ms	4332 KB	Output is correct
14	Correct	3 ms	4332 KB	Output is correct
15	Correct	3 ms	4332 KB	Output is correct
16	Correct	3 ms	4332 KB	Output is correct
17	Correct	3 ms	4332 KB	Output is correct
18	Correct	3 ms	4332 KB	Output is correct
19	Correct	3 ms	4332 KB	Output is correct
20	Correct	3 ms	4332 KB	Output is correct
21	Correct	3 ms	4332 KB	Output is correct
22	Correct	3 ms	4332 KB	Output is correct
23	Correct	4 ms	4332 KB	Output is correct
24	Correct	3 ms	4332 KB	Output is correct
25	Correct	3 ms	4332 KB	Output is correct
26	Correct	3 ms	4332 KB	Output is correct
27	Correct	3 ms	4332 KB	Output is correct
28	Correct	3 ms	4332 KB	Output is correct
29	Correct	3 ms	4332 KB	Output is correct

Subtask #3
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4332 KB	Output is correct
2	Correct	3 ms	4332 KB	Output is correct
3	Correct	3 ms	4332 KB	Output is correct
4	Correct	3 ms	4332 KB	Output is correct
5	Correct	3 ms	4332 KB	Output is correct
6	Correct	3 ms	4332 KB	Output is correct
7	Correct	3 ms	4332 KB	Output is correct
8	Correct	3 ms	4332 KB	Output is correct
9	Correct	3 ms	4332 KB	Output is correct
10	Correct	3 ms	4332 KB	Output is correct
11	Correct	3 ms	4332 KB	Output is correct
12	Correct	3 ms	4332 KB	Output is correct
13	Correct	3 ms	4332 KB	Output is correct
14	Correct	3 ms	4332 KB	Output is correct
15	Correct	3 ms	4332 KB	Output is correct
16	Correct	3 ms	4332 KB	Output is correct
17	Correct	3 ms	4332 KB	Output is correct
18	Correct	3 ms	4332 KB	Output is correct
19	Correct	3 ms	4332 KB	Output is correct
20	Correct	3 ms	4332 KB	Output is correct
21	Correct	3 ms	4332 KB	Output is correct
22	Correct	3 ms	4332 KB	Output is correct
23	Correct	4 ms	4332 KB	Output is correct
24	Correct	3 ms	4332 KB	Output is correct
25	Correct	3 ms	4332 KB	Output is correct
26	Correct	3 ms	4332 KB	Output is correct
27	Correct	3 ms	4332 KB	Output is correct
28	Correct	3 ms	4332 KB	Output is correct
29	Correct	3 ms	4332 KB	Output is correct
30	Incorrect	266 ms	12780 KB	3rd lines differ - on the 1st token, expected: '333035179244', found: '588985632636'
31	Halted	0 ms	0 KB	-

Subtask #4
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	4332 KB	Output is correct
2	Correct	3 ms	4332 KB	Output is correct
3	Correct	4 ms	4332 KB	Output is correct
4	Correct	6 ms	4332 KB	Output is correct
5	Correct	6 ms	4332 KB	Output is correct
6	Correct	3 ms	4332 KB	Output is correct
7	Correct	3 ms	4332 KB	Output is correct
8	Correct	3 ms	4332 KB	Output is correct
9	Correct	3 ms	4332 KB	Output is correct
10	Correct	3 ms	4332 KB	Output is correct
11	Correct	3 ms	4332 KB	Output is correct
12	Correct	3 ms	4460 KB	Output is correct
13	Correct	3 ms	4332 KB	Output is correct
14	Correct	3 ms	4332 KB	Output is correct
15	Correct	3 ms	4332 KB	Output is correct
16	Correct	3 ms	4332 KB	Output is correct
17	Correct	3 ms	4332 KB	Output is correct
18	Correct	3 ms	4332 KB	Output is correct
19	Correct	3 ms	4332 KB	Output is correct
20	Correct	3 ms	4332 KB	Output is correct

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4332 KB	Output is correct
2	Correct	3 ms	4332 KB	Output is correct
3	Correct	3 ms	4332 KB	Output is correct
4	Correct	3 ms	4332 KB	Output is correct
5	Correct	3 ms	4332 KB	Output is correct
6	Correct	3 ms	4332 KB	Output is correct
7	Correct	3 ms	4332 KB	Output is correct
8	Correct	3 ms	4332 KB	Output is correct
9	Correct	3 ms	4332 KB	Output is correct
10	Correct	3 ms	4332 KB	Output is correct
11	Correct	3 ms	4332 KB	Output is correct
12	Correct	3 ms	4332 KB	Output is correct
13	Correct	3 ms	4332 KB	Output is correct
14	Correct	3 ms	4332 KB	Output is correct
15	Correct	3 ms	4332 KB	Output is correct
16	Correct	3 ms	4332 KB	Output is correct
17	Correct	3 ms	4332 KB	Output is correct
18	Correct	3 ms	4332 KB	Output is correct
19	Correct	3 ms	4332 KB	Output is correct
20	Correct	3 ms	4332 KB	Output is correct
21	Correct	3 ms	4332 KB	Output is correct
22	Correct	3 ms	4332 KB	Output is correct
23	Correct	4 ms	4332 KB	Output is correct
24	Correct	3 ms	4332 KB	Output is correct
25	Correct	3 ms	4332 KB	Output is correct
26	Correct	3 ms	4332 KB	Output is correct
27	Correct	3 ms	4332 KB	Output is correct
28	Correct	3 ms	4332 KB	Output is correct
29	Correct	3 ms	4332 KB	Output is correct
30	Incorrect	266 ms	12780 KB	3rd lines differ - on the 1st token, expected: '333035179244', found: '588985632636'
31	Halted	0 ms	0 KB	-

Submission #355461

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 28.0

Subtask #4 20.0 / 20.0

Subtask #5 0 / 30.0

Subtask #1
12.0 / 12.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 28.0

Subtask #4
20.0 / 20.0

Subtask #5
0 / 30.0