답안 #790922

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
790922	2023-07-23T09:26:45 Z	fatemetmhr	고대 책들 (IOI17_books)	C++17	50 / 100	141 ms	28660 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 = s;
	for(int i = 0; i < n; i++){
		per[i] = p[i];
		if(i != per[i]){
			s = min(s, i);
			mx = max(mx, i);
		}
	}
	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]++;
	}
	//cout << s << ' ' << mx << endl;
	return ans + 2 *  get(s, mx - 1);
}

Compilation message

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

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 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	0 ms	340 KB	Output is correct
9	Correct	0 ms	224 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 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	0 ms	340 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 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	0 ms	340 KB	Output is correct
9	Correct	0 ms	224 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 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	0 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	0 ms	340 KB	Output is correct
29	Correct	0 ms	340 KB	Output is correct

Subtask #3
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 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	0 ms	340 KB	Output is correct
9	Correct	0 ms	224 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 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	0 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	0 ms	340 KB	Output is correct
29	Correct	0 ms	340 KB	Output is correct
30	Correct	127 ms	28564 KB	Output is correct
31	Correct	141 ms	28608 KB	Output is correct
32	Correct	111 ms	28544 KB	Output is correct
33	Correct	119 ms	28548 KB	Output is correct
34	Correct	113 ms	28656 KB	Output is correct
35	Correct	113 ms	28660 KB	Output is correct
36	Correct	119 ms	28656 KB	Output is correct
37	Correct	106 ms	28544 KB	Output is correct
38	Correct	115 ms	28540 KB	Output is correct
39	Correct	120 ms	28656 KB	Output is correct
40	Correct	111 ms	28596 KB	Output is correct
41	Correct	120 ms	28592 KB	Output is correct
42	Correct	119 ms	28544 KB	Output is correct
43	Correct	122 ms	28660 KB	Output is correct

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 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

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 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	0 ms	340 KB	Output is correct
9	Correct	0 ms	224 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 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	0 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	0 ms	340 KB	Output is correct
29	Correct	0 ms	340 KB	Output is correct
30	Correct	127 ms	28564 KB	Output is correct
31	Correct	141 ms	28608 KB	Output is correct
32	Correct	111 ms	28544 KB	Output is correct
33	Correct	119 ms	28548 KB	Output is correct
34	Correct	113 ms	28656 KB	Output is correct
35	Correct	113 ms	28660 KB	Output is correct
36	Correct	119 ms	28656 KB	Output is correct
37	Correct	106 ms	28544 KB	Output is correct
38	Correct	115 ms	28540 KB	Output is correct
39	Correct	120 ms	28656 KB	Output is correct
40	Correct	111 ms	28596 KB	Output is correct
41	Correct	120 ms	28592 KB	Output is correct
42	Correct	119 ms	28544 KB	Output is correct
43	Correct	122 ms	28660 KB	Output is correct
44	Incorrect	0 ms	340 KB	3rd lines differ - on the 1st token, expected: '3304', found: '2744'
45	Halted	0 ms	0 KB	-

답안 #790922

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