답안 #625142

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
625142	2022-08-09T13:24:15 Z	SHZhang	고대 책들 (IOI17_books)	C++14	100 / 100	629 ms	124220 KB

books

#include "books.h"

#include <vector>

using namespace std;

#define ll long long

int n;
int p[1000005];
int cycle[1000005];
bool vis[1000005];
int minpos[1000005];
int maxpos[1000005];

int nextcycle = 0;

struct Segtree {
	int l, r;
	Segtree* lchild;
	Segtree* rchild;
	pair<int, int> bounds;
};

Segtree* root;

pair<int, int> merge_pair(pair<int, int> p1, pair<int, int> p2)
{
	return make_pair(min(p1.first, p2.first), max(p1.second, p2.second));
}

Segtree* build(int l, int r)
{
	Segtree* st = new Segtree;
	st->l = l; st->r = r;
	if (l == r) {
		st->lchild = st->rchild = NULL;
		st->bounds.first = minpos[cycle[l]];
		st->bounds.second = maxpos[cycle[l]];
	} else {
		st->lchild = build(l, (l + r) / 2);
		st->rchild = build((l + r) / 2 + 1, r);
		st->bounds = merge_pair(st->lchild->bounds, st->rchild->bounds);
	}
	return st;
}

pair<int, int> query(Segtree* st, int l, int r)
{
	if (st->r < l || r < st->l) return make_pair(n, -1);
	if (l <= st->l && st->r <= r) return st->bounds;
	return merge_pair(query(st->lchild, l, r), query(st->rchild, l, r));
}

pair<int, int> expand(pair<int, int> old)
{
	while (true) {
		pair<int, int> pair2 = query(root, old.first, old.second);
		if (pair2.first == old.first && pair2.second == old.second) return pair2;
		old = pair2;
	}
}

ll minimum_walk(vector<int> perm, int s) {
	n = perm.size();
	bool ans0 = true;
	for (int i = 0; i < n; i++) {
		p[i] = perm[i]; if (p[i] != i) ans0 = false;
	}
	if (ans0) return 0;
	int lbound = 0;
	int rbound = n - 1;
	while (p[lbound] == lbound) lbound++;
	while (p[rbound] == rbound) rbound--;
	for (int i = 0; i < n; i++) {
		if (vis[i]) continue;
		minpos[nextcycle] = n;
		maxpos[nextcycle] = -1;
		int cur = i;
		while (!vis[cur]) {
			cycle[cur] = nextcycle;
			vis[cur] = true;
			minpos[nextcycle] = min(minpos[nextcycle], cur);
			maxpos[nextcycle] = max(maxpos[nextcycle], cur);
			cur = p[cur];
		}
		nextcycle++;
	}
	//fprintf(stderr, "HERE");
	root = build(0, n - 1);
	pair<int, int> cur = expand(make_pair(s, s));
	int rounds = 0;
	//fprintf(stderr, "%d %d\n", cur.first, cur.second);
	while (cur.first > lbound || cur.second < rbound) {
		//fprintf(stderr, "!!!%d %d\n", cur.first, cur.second);
		if (cur.first <= lbound) {
			cur.second++; cur = expand(cur); rounds++;
		} else if (cur.second >= rbound) {
			cur.first--; cur = expand(cur); rounds++;
		} else {
			pair<int, int> left_intv = cur;
			int lcount = 0;
			while (left_intv.first > lbound && left_intv.second <= cur.second) {
				left_intv.first--; left_intv = expand(left_intv); lcount++;
			}
			pair<int, int> right_intv = cur;
			int rcount = 0;
			while (right_intv.second < rbound && right_intv.first >= cur.first) {
				right_intv.second++; right_intv = expand(right_intv); rcount++;
			}
			if (lcount < rcount) {
				cur = left_intv; rounds += lcount;
			} else {
				cur = right_intv; rounds += rcount;
			}
		}
	}
	ll ans = rounds * 2;
	for (int i = 0; i < n; i++) {
		ans += (ll)max(p[i] - i, i - p[i]);
	}
	return ans;
}

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	296 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	1 ms	224 KB	Output is correct
7	Correct	1 ms	300 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	220 KB	Output is correct
10	Correct	1 ms	224 KB	Output is correct
11	Correct	0 ms	224 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 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	0 ms	212 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	296 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	1 ms	224 KB	Output is correct
7	Correct	1 ms	300 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	220 KB	Output is correct
10	Correct	1 ms	224 KB	Output is correct
11	Correct	0 ms	224 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 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	0 ms	212 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	1 ms	424 KB	Output is correct
23	Correct	1 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	1 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct

Subtask #3
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	296 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	1 ms	224 KB	Output is correct
7	Correct	1 ms	300 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	220 KB	Output is correct
10	Correct	1 ms	224 KB	Output is correct
11	Correct	0 ms	224 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 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	0 ms	212 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	1 ms	424 KB	Output is correct
23	Correct	1 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	1 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	292 ms	117468 KB	Output is correct
31	Correct	238 ms	117480 KB	Output is correct
32	Correct	88 ms	18660 KB	Output is correct
33	Correct	376 ms	123000 KB	Output is correct
34	Correct	295 ms	122968 KB	Output is correct
35	Correct	327 ms	121948 KB	Output is correct
36	Correct	228 ms	119512 KB	Output is correct
37	Correct	185 ms	117852 KB	Output is correct
38	Correct	212 ms	117580 KB	Output is correct
39	Correct	192 ms	117572 KB	Output is correct
40	Correct	282 ms	117552 KB	Output is correct
41	Correct	210 ms	117496 KB	Output is correct
42	Correct	208 ms	117480 KB	Output is correct
43	Correct	183 ms	123356 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	428 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	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	428 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	424 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	296 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	1 ms	224 KB	Output is correct
7	Correct	1 ms	300 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	220 KB	Output is correct
10	Correct	1 ms	224 KB	Output is correct
11	Correct	0 ms	224 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 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	0 ms	212 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	1 ms	424 KB	Output is correct
23	Correct	1 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	1 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	292 ms	117468 KB	Output is correct
31	Correct	238 ms	117480 KB	Output is correct
32	Correct	88 ms	18660 KB	Output is correct
33	Correct	376 ms	123000 KB	Output is correct
34	Correct	295 ms	122968 KB	Output is correct
35	Correct	327 ms	121948 KB	Output is correct
36	Correct	228 ms	119512 KB	Output is correct
37	Correct	185 ms	117852 KB	Output is correct
38	Correct	212 ms	117580 KB	Output is correct
39	Correct	192 ms	117572 KB	Output is correct
40	Correct	282 ms	117552 KB	Output is correct
41	Correct	210 ms	117496 KB	Output is correct
42	Correct	208 ms	117480 KB	Output is correct
43	Correct	183 ms	123356 KB	Output is correct
44	Correct	1 ms	340 KB	Output is correct
45	Correct	1 ms	428 KB	Output is correct
46	Correct	1 ms	340 KB	Output is correct
47	Correct	1 ms	340 KB	Output is correct
48	Correct	1 ms	340 KB	Output is correct
49	Correct	1 ms	340 KB	Output is correct
50	Correct	1 ms	340 KB	Output is correct
51	Correct	1 ms	340 KB	Output is correct
52	Correct	1 ms	428 KB	Output is correct
53	Correct	1 ms	212 KB	Output is correct
54	Correct	1 ms	340 KB	Output is correct
55	Correct	1 ms	340 KB	Output is correct
56	Correct	1 ms	424 KB	Output is correct
57	Correct	1 ms	340 KB	Output is correct
58	Correct	1 ms	340 KB	Output is correct
59	Correct	0 ms	340 KB	Output is correct
60	Correct	1 ms	340 KB	Output is correct
61	Correct	1 ms	340 KB	Output is correct
62	Correct	1 ms	340 KB	Output is correct
63	Correct	1 ms	340 KB	Output is correct
64	Correct	222 ms	123292 KB	Output is correct
65	Correct	190 ms	123896 KB	Output is correct
66	Correct	177 ms	117912 KB	Output is correct
67	Correct	195 ms	117644 KB	Output is correct
68	Correct	19 ms	12084 KB	Output is correct
69	Correct	18 ms	11988 KB	Output is correct
70	Correct	17 ms	12148 KB	Output is correct
71	Correct	18 ms	12364 KB	Output is correct
72	Correct	19 ms	12512 KB	Output is correct
73	Correct	20 ms	11848 KB	Output is correct
74	Correct	524 ms	122984 KB	Output is correct
75	Correct	477 ms	123088 KB	Output is correct
76	Correct	196 ms	123296 KB	Output is correct
77	Correct	192 ms	123256 KB	Output is correct
78	Correct	204 ms	122416 KB	Output is correct
79	Correct	183 ms	122532 KB	Output is correct
80	Correct	86 ms	18660 KB	Output is correct
81	Correct	629 ms	121596 KB	Output is correct
82	Correct	587 ms	121508 KB	Output is correct
83	Correct	310 ms	120540 KB	Output is correct
84	Correct	283 ms	120028 KB	Output is correct
85	Correct	258 ms	118732 KB	Output is correct
86	Correct	187 ms	118012 KB	Output is correct
87	Correct	574 ms	124220 KB	Output is correct
88	Correct	466 ms	123212 KB	Output is correct
89	Correct	369 ms	121164 KB	Output is correct
90	Correct	176 ms	117744 KB	Output is correct
91	Correct	175 ms	117640 KB	Output is correct
92	Correct	205 ms	117480 KB	Output is correct

답안 #625142

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