Submission #790942

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
790942	2023-07-23T09:38:31 Z	fatemetmhr	Ancient Books (IOI17_books)	C++17	50 / 100	143 ms	28664 KB

books

//  ~ Be Name Khoda ~  //

#include "books.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  1e6   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

ll ans = 0;
int per[maxn5], req[maxn5], cmp[maxn5], ps[maxn5];
int num = 0, av[maxn5], cnt = 0;
bool mark[maxn5];


void dfs(int v){
	mark[v] = true;
	req[min(v, per[v])]++;
	req[max(v, per[v])]--;
	ans += abs(v - per[v]);
	cnt++;
	cmp[v] = num;
	if(!mark[per[v]])
		dfs(per[v]);
}

int get(int l, int r){
	if(l > r)
		return 0;
	return ps[r] - (l ? ps[l - 1] : 0);
}


long long minimum_walk(std::vector<int> p, int s) {
	int n = p.size();
	int mx = 0, mn = n;
	for(int i = 0; i < n; i++){
		per[i] = p[i];
		if(i != per[i]){
			mn = min(mn, i);
			mx = max(mx, i);
		}
	}
	if(mn == n)
		return 0;
	int good = 0;
	fill(av, av + n + 5, n + 10);
	for(int i = 0; i < n; i++) if(!mark[i]){
		cnt = 0;
		dfs(i);
		if(cnt > 1)
			good++;
		num++;
	}
	int emp = 0, cur = 0;
	for(int i = 0; i < n; i++){
		cur += req[i];
		if(i)
			ps[i] = ps[i - 1];
		if(!cur)
			ps[i]++;
	}
	int add = 2 * n;
	for(int i = 0; i < n; i++) if(i != p[i])
		add = min(add, abs(i - s) * 2);
	if(mn > s || mx < s)
		add = min(abs(mx - s), abs(mn - s)) * 2;
	//cout << s << ' ' << mx << endl;
	return ans + 2 *  get(mn, mx - 1) + add;
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:71:6: warning: unused variable 'emp' [-Wunused-variable]
   71 |  int emp = 0, cur = 0;
      |      ^~~

Subtask #1
12.0 / 12.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	1 ms	384 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	0 ms	340 KB	Output is correct
25	Correct	0 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	296 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	0 ms	340 KB	Output is correct
30	Correct	123 ms	28660 KB	Output is correct
31	Correct	143 ms	28540 KB	Output is correct
32	Correct	72 ms	12028 KB	Output is correct
33	Correct	95 ms	28656 KB	Output is correct
34	Correct	102 ms	28596 KB	Output is correct
35	Correct	96 ms	28544 KB	Output is correct
36	Correct	97 ms	28656 KB	Output is correct
37	Correct	88 ms	28656 KB	Output is correct
38	Correct	89 ms	28660 KB	Output is correct
39	Correct	110 ms	28540 KB	Output is correct
40	Correct	91 ms	28544 KB	Output is correct
41	Correct	105 ms	28620 KB	Output is correct
42	Correct	109 ms	28540 KB	Output is correct
43	Correct	98 ms	28664 KB	Output is correct

Subtask #4
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	340 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	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	1 ms	384 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	0 ms	340 KB	Output is correct
25	Correct	0 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	296 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	0 ms	340 KB	Output is correct
30	Correct	123 ms	28660 KB	Output is correct
31	Correct	143 ms	28540 KB	Output is correct
32	Correct	72 ms	12028 KB	Output is correct
33	Correct	95 ms	28656 KB	Output is correct
34	Correct	102 ms	28596 KB	Output is correct
35	Correct	96 ms	28544 KB	Output is correct
36	Correct	97 ms	28656 KB	Output is correct
37	Correct	88 ms	28656 KB	Output is correct
38	Correct	89 ms	28660 KB	Output is correct
39	Correct	110 ms	28540 KB	Output is correct
40	Correct	91 ms	28544 KB	Output is correct
41	Correct	105 ms	28620 KB	Output is correct
42	Correct	109 ms	28540 KB	Output is correct
43	Correct	98 ms	28664 KB	Output is correct
44	Incorrect	1 ms	340 KB	3rd lines differ - on the 1st token, expected: '3304', found: '2744'
45	Halted	0 ms	0 KB	-

Submission #790942

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