답안 #605673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
605673	2022-07-25T21:38:10 Z	dnass	고대 책들 (IOI17_books)	C++17	50 / 100	291 ms	133060 KB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;

lld n;

lld minimum_walk(vector<int> p, int s){
	n = (lld) p.size();
	lld ans = 0;
	for(lld i=0;i<n;i++) ans+=abs(p[i]-i);
	vector<bool> vis(n, false);
	vector<vector<lld>> cycles;
	vector<pair<lld,lld>> evs;
	for(lld i=0;i<n;i++){
		if(!vis[i]){
			vector<lld> tmp;
			lld x = i;
			while(true){
				if(vis[x]) break;
				tmp.push_back(x);
				vis[x] = true;
				x = p[x];
			}
			cycles.push_back(tmp);
			sort(tmp.begin(), tmp.end());
			evs.push_back({tmp[0], 0});
			evs.push_back({*tmp.rbegin(), 1});
		}
	}
	sort(evs.begin(), evs.end());
	lld op = 0;
	vector<pair<lld,lld>> blocks;
	lld beg = 0;
	for(lld i=0;i<(lld)evs.size();i++){
		if(evs[i].second==0){
			if(op==0) beg = evs[i].first;
			op++;
		}else{
			op--;
			if(op==0) blocks.push_back({beg,evs[i].first});
		}
	}
	while((lld)blocks.size()>0&&blocks.rbegin()->second==blocks.rbegin()->first) blocks.pop_back();
	for(lld i=1;i<(lld)blocks.size();i++){
		ans += 2*(blocks[i].first-blocks[i-1].second);
	}
	return ans;
}

Subtask #1

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	300 KB	Output is correct
9	Correct	1 ms	304 KB	Output is correct
10	Correct	0 ms	296 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	300 KB	Output is correct
9	Correct	1 ms	304 KB	Output is correct
10	Correct	0 ms	296 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	300 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	312 KB	Output is correct
23	Correct	1 ms	300 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	300 KB	Output is correct
27	Correct	1 ms	300 KB	Output is correct
28	Correct	1 ms	300 KB	Output is correct
29	Correct	1 ms	300 KB	Output is correct

Subtask #3

28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	300 KB	Output is correct
9	Correct	1 ms	304 KB	Output is correct
10	Correct	0 ms	296 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	300 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	312 KB	Output is correct
23	Correct	1 ms	300 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	300 KB	Output is correct
27	Correct	1 ms	300 KB	Output is correct
28	Correct	1 ms	300 KB	Output is correct
29	Correct	1 ms	300 KB	Output is correct
30	Correct	220 ms	27344 KB	Output is correct
31	Correct	209 ms	24572 KB	Output is correct
32	Correct	291 ms	133060 KB	Output is correct
33	Correct	248 ms	101724 KB	Output is correct
34	Correct	261 ms	101480 KB	Output is correct
35	Correct	257 ms	78852 KB	Output is correct
36	Correct	179 ms	47332 KB	Output is correct
37	Correct	136 ms	25948 KB	Output is correct
38	Correct	151 ms	23264 KB	Output is correct
39	Correct	137 ms	23136 KB	Output is correct
40	Correct	152 ms	22992 KB	Output is correct
41	Correct	175 ms	23572 KB	Output is correct
42	Correct	186 ms	23568 KB	Output is correct
43	Correct	278 ms	78808 KB	Output is correct

Subtask #4

0 / 20.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	300 KB	Output is correct
9	Correct	1 ms	304 KB	Output is correct
10	Correct	0 ms	296 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	300 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	312 KB	Output is correct
23	Correct	1 ms	300 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	300 KB	Output is correct
27	Correct	1 ms	300 KB	Output is correct
28	Correct	1 ms	300 KB	Output is correct
29	Correct	1 ms	300 KB	Output is correct
30	Correct	220 ms	27344 KB	Output is correct
31	Correct	209 ms	24572 KB	Output is correct
32	Correct	291 ms	133060 KB	Output is correct
33	Correct	248 ms	101724 KB	Output is correct
34	Correct	261 ms	101480 KB	Output is correct
35	Correct	257 ms	78852 KB	Output is correct
36	Correct	179 ms	47332 KB	Output is correct
37	Correct	136 ms	25948 KB	Output is correct
38	Correct	151 ms	23264 KB	Output is correct
39	Correct	137 ms	23136 KB	Output is correct
40	Correct	152 ms	22992 KB	Output is correct
41	Correct	175 ms	23572 KB	Output is correct
42	Correct	186 ms	23568 KB	Output is correct
43	Correct	278 ms	78808 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	-