답안 #921301

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
921301	2024-02-03T16:43:27 Z	siewjh	고대 책들 (IOI17_books)	C++17	100 / 100	97 ms	26964 KB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1'000'005;
int cyc[MAXN], lc[MAXN], rc[MAXN];
void extend(int &cl, int &cr, int tl, int tr){
	while (cl > tl || cr < tr){
		if (cl > tl){
			cl--;
			tl = min(tl, lc[cyc[cl]]); tr = max(tr, rc[cyc[cl]]);
		}
		else{
			cr++;
			tl = min(tl, lc[cyc[cr]]); tr = max(tr, rc[cyc[cr]]);
		}
	}
}
ll minimum_walk(vector<int> p, int s) {
	int nums = p.size();
	int mn = s, mx = s;
	memset(cyc, -1, sizeof(cyc));
	ll ans = 0;
	for (int i = 0; i < nums; i++) ans += abs(i - p[i]);
	for (int i = 0; i < nums; i++)
		if (cyc[i] == -1){
			int curr = i, l = i, r = i;
			do{
				cyc[curr] = i; l = min(l, curr); r = max(r, curr);
				curr = p[curr];
			} while (curr != i);
			lc[i] = l; rc[i] = r;
			if (p[i] != i){
				mn = min(mn, l); mx = max(mx, r);
			}
		}
	int cl = s, cr = s;
	extend(cl, cr, lc[cyc[s]], rc[cyc[s]]);
	while (cl > mn || cr < mx){
		int lnl = cl, lnr = cr, le = 0;
		while (lnl > mn && lnr <= cr){
			extend(lnl, lnr, lnl - 1, lnr);
			le++;
		}
		int rnl = cl, rnr = cr, re = 0;
		while (rnr < mx && rnl >= cl){
			extend(rnl, rnr, rnl, rnr + 1);
			re++;
		}
		if (lnl == rnl && lnr == rnr){ // cross the middle
			ans += 2 * min(le, re);
			cl = lnl; cr = lnr;
		}
		else{
			ans += 2 * (le + re);
			cl = lnl; cr = rnr;
		}
	}
	return ans;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	7768 KB	Output is correct
2	Correct	2 ms	7772 KB	Output is correct
3	Correct	2 ms	7772 KB	Output is correct
4	Correct	2 ms	7772 KB	Output is correct
5	Correct	2 ms	7772 KB	Output is correct
6	Correct	2 ms	7772 KB	Output is correct
7	Correct	2 ms	7772 KB	Output is correct
8	Correct	2 ms	7772 KB	Output is correct
9	Correct	2 ms	7772 KB	Output is correct
10	Correct	2 ms	7772 KB	Output is correct
11	Correct	2 ms	7768 KB	Output is correct
12	Correct	2 ms	7768 KB	Output is correct
13	Correct	2 ms	7772 KB	Output is correct
14	Correct	2 ms	7772 KB	Output is correct
15	Correct	2 ms	7772 KB	Output is correct
16	Correct	2 ms	7768 KB	Output is correct
17	Correct	2 ms	7772 KB	Output is correct
18	Correct	2 ms	7772 KB	Output is correct
19	Correct	2 ms	7772 KB	Output is correct
20	Correct	2 ms	7772 KB	Output is correct
21	Correct	2 ms	7772 KB	Output is correct
22	Correct	2 ms	8028 KB	Output is correct
23	Correct	2 ms	7772 KB	Output is correct
24	Correct	2 ms	8024 KB	Output is correct
25	Correct	2 ms	7772 KB	Output is correct
26	Correct	2 ms	7772 KB	Output is correct
27	Correct	2 ms	7772 KB	Output is correct
28	Correct	2 ms	7772 KB	Output is correct
29	Correct	2 ms	7772 KB	Output is correct

Subtask #3
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	7768 KB	Output is correct
2	Correct	2 ms	7772 KB	Output is correct
3	Correct	2 ms	7772 KB	Output is correct
4	Correct	2 ms	7772 KB	Output is correct
5	Correct	2 ms	7772 KB	Output is correct
6	Correct	2 ms	7772 KB	Output is correct
7	Correct	2 ms	7772 KB	Output is correct
8	Correct	2 ms	7772 KB	Output is correct
9	Correct	2 ms	7772 KB	Output is correct
10	Correct	2 ms	7772 KB	Output is correct
11	Correct	2 ms	7768 KB	Output is correct
12	Correct	2 ms	7768 KB	Output is correct
13	Correct	2 ms	7772 KB	Output is correct
14	Correct	2 ms	7772 KB	Output is correct
15	Correct	2 ms	7772 KB	Output is correct
16	Correct	2 ms	7768 KB	Output is correct
17	Correct	2 ms	7772 KB	Output is correct
18	Correct	2 ms	7772 KB	Output is correct
19	Correct	2 ms	7772 KB	Output is correct
20	Correct	2 ms	7772 KB	Output is correct
21	Correct	2 ms	7772 KB	Output is correct
22	Correct	2 ms	8028 KB	Output is correct
23	Correct	2 ms	7772 KB	Output is correct
24	Correct	2 ms	8024 KB	Output is correct
25	Correct	2 ms	7772 KB	Output is correct
26	Correct	2 ms	7772 KB	Output is correct
27	Correct	2 ms	7772 KB	Output is correct
28	Correct	2 ms	7772 KB	Output is correct
29	Correct	2 ms	7772 KB	Output is correct
30	Correct	97 ms	26484 KB	Output is correct
31	Correct	92 ms	22356 KB	Output is correct
32	Correct	79 ms	26708 KB	Output is correct
33	Correct	85 ms	26472 KB	Output is correct
34	Correct	86 ms	26704 KB	Output is correct
35	Correct	90 ms	26580 KB	Output is correct
36	Correct	83 ms	26600 KB	Output is correct
37	Correct	78 ms	26708 KB	Output is correct
38	Correct	78 ms	26476 KB	Output is correct
39	Correct	81 ms	26444 KB	Output is correct
40	Correct	84 ms	26452 KB	Output is correct
41	Correct	87 ms	26472 KB	Output is correct
42	Correct	87 ms	26560 KB	Output is correct
43	Correct	85 ms	26472 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	7772 KB	Output is correct
2	Correct	2 ms	7868 KB	Output is correct
3	Correct	2 ms	7772 KB	Output is correct
4	Correct	2 ms	7772 KB	Output is correct
5	Correct	2 ms	7772 KB	Output is correct
6	Correct	2 ms	7772 KB	Output is correct
7	Correct	2 ms	7772 KB	Output is correct
8	Correct	2 ms	7772 KB	Output is correct
9	Correct	2 ms	7772 KB	Output is correct
10	Correct	2 ms	7772 KB	Output is correct
11	Correct	2 ms	7772 KB	Output is correct
12	Correct	2 ms	7772 KB	Output is correct
13	Correct	2 ms	8028 KB	Output is correct
14	Correct	2 ms	7772 KB	Output is correct
15	Correct	2 ms	7772 KB	Output is correct
16	Correct	2 ms	7772 KB	Output is correct
17	Correct	2 ms	7772 KB	Output is correct
18	Correct	2 ms	7856 KB	Output is correct
19	Correct	2 ms	7768 KB	Output is correct
20	Correct	2 ms	7768 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	7768 KB	Output is correct
2	Correct	2 ms	7772 KB	Output is correct
3	Correct	2 ms	7772 KB	Output is correct
4	Correct	2 ms	7772 KB	Output is correct
5	Correct	2 ms	7772 KB	Output is correct
6	Correct	2 ms	7772 KB	Output is correct
7	Correct	2 ms	7772 KB	Output is correct
8	Correct	2 ms	7772 KB	Output is correct
9	Correct	2 ms	7772 KB	Output is correct
10	Correct	2 ms	7772 KB	Output is correct
11	Correct	2 ms	7768 KB	Output is correct
12	Correct	2 ms	7768 KB	Output is correct
13	Correct	2 ms	7772 KB	Output is correct
14	Correct	2 ms	7772 KB	Output is correct
15	Correct	2 ms	7772 KB	Output is correct
16	Correct	2 ms	7768 KB	Output is correct
17	Correct	2 ms	7772 KB	Output is correct
18	Correct	2 ms	7772 KB	Output is correct
19	Correct	2 ms	7772 KB	Output is correct
20	Correct	2 ms	7772 KB	Output is correct
21	Correct	2 ms	7772 KB	Output is correct
22	Correct	2 ms	8028 KB	Output is correct
23	Correct	2 ms	7772 KB	Output is correct
24	Correct	2 ms	8024 KB	Output is correct
25	Correct	2 ms	7772 KB	Output is correct
26	Correct	2 ms	7772 KB	Output is correct
27	Correct	2 ms	7772 KB	Output is correct
28	Correct	2 ms	7772 KB	Output is correct
29	Correct	2 ms	7772 KB	Output is correct
30	Correct	97 ms	26484 KB	Output is correct
31	Correct	92 ms	22356 KB	Output is correct
32	Correct	79 ms	26708 KB	Output is correct
33	Correct	85 ms	26472 KB	Output is correct
34	Correct	86 ms	26704 KB	Output is correct
35	Correct	90 ms	26580 KB	Output is correct
36	Correct	83 ms	26600 KB	Output is correct
37	Correct	78 ms	26708 KB	Output is correct
38	Correct	78 ms	26476 KB	Output is correct
39	Correct	81 ms	26444 KB	Output is correct
40	Correct	84 ms	26452 KB	Output is correct
41	Correct	87 ms	26472 KB	Output is correct
42	Correct	87 ms	26560 KB	Output is correct
43	Correct	85 ms	26472 KB	Output is correct
44	Correct	2 ms	7772 KB	Output is correct
45	Correct	2 ms	7868 KB	Output is correct
46	Correct	2 ms	7772 KB	Output is correct
47	Correct	2 ms	7772 KB	Output is correct
48	Correct	2 ms	7772 KB	Output is correct
49	Correct	2 ms	7772 KB	Output is correct
50	Correct	2 ms	7772 KB	Output is correct
51	Correct	2 ms	7772 KB	Output is correct
52	Correct	2 ms	7772 KB	Output is correct
53	Correct	2 ms	7772 KB	Output is correct
54	Correct	2 ms	7772 KB	Output is correct
55	Correct	2 ms	7772 KB	Output is correct
56	Correct	2 ms	8028 KB	Output is correct
57	Correct	2 ms	7772 KB	Output is correct
58	Correct	2 ms	7772 KB	Output is correct
59	Correct	2 ms	7772 KB	Output is correct
60	Correct	2 ms	7772 KB	Output is correct
61	Correct	2 ms	7856 KB	Output is correct
62	Correct	2 ms	7768 KB	Output is correct
63	Correct	2 ms	7768 KB	Output is correct
64	Correct	80 ms	26492 KB	Output is correct
65	Correct	87 ms	26496 KB	Output is correct
66	Correct	80 ms	26704 KB	Output is correct
67	Correct	78 ms	26620 KB	Output is correct
68	Correct	10 ms	13432 KB	Output is correct
69	Correct	10 ms	13404 KB	Output is correct
70	Correct	11 ms	13552 KB	Output is correct
71	Correct	10 ms	13508 KB	Output is correct
72	Correct	10 ms	13404 KB	Output is correct
73	Correct	12 ms	11608 KB	Output is correct
74	Correct	83 ms	26708 KB	Output is correct
75	Correct	86 ms	26608 KB	Output is correct
76	Correct	91 ms	26964 KB	Output is correct
77	Correct	81 ms	26708 KB	Output is correct
78	Correct	82 ms	26708 KB	Output is correct
79	Correct	81 ms	26704 KB	Output is correct
80	Correct	74 ms	26704 KB	Output is correct
81	Correct	88 ms	26492 KB	Output is correct
82	Correct	79 ms	26708 KB	Output is correct
83	Correct	84 ms	26608 KB	Output is correct
84	Correct	83 ms	26492 KB	Output is correct
85	Correct	82 ms	26960 KB	Output is correct
86	Correct	79 ms	26708 KB	Output is correct
87	Correct	84 ms	26732 KB	Output is correct
88	Correct	93 ms	26704 KB	Output is correct
89	Correct	85 ms	26604 KB	Output is correct
90	Correct	78 ms	26708 KB	Output is correct
91	Correct	79 ms	26704 KB	Output is correct
92	Correct	81 ms	26488 KB	Output is correct

답안 #921301

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 10.0 / 10.0

Subtask #3 28.0 / 28.0

Subtask #4 20.0 / 20.0

Subtask #5 30.0 / 30.0

Subtask #1
12.0 / 12.0

Subtask #2
10.0 / 10.0

Subtask #3
28.0 / 28.0

Subtask #4
20.0 / 20.0

Subtask #5
30.0 / 30.0