답안 #468140

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
468140	2021-08-26T21:40:30 Z	nonsensenonsense1	즐거운 행로 (APIO20_fun)	C++17	100 / 100	284 ms	21816 KB

#include "fun.h"
#include <vector>
#include <algorithm>

const int N = 100000;
int size[N], dist[N];
std::vector<int> root, ans;
std::vector<std::pair<int, int> > sub[3];

int max_size() 
{
	return std::max(sub[0].size(), std::max(sub[1].size(), sub[2].size()));
}

int get_far(int cur) 
{
	int len = 0, from = -1;
	for (int i = 0; i < (int)root.size(); ++i) if (i != cur && !sub[i].empty() && sub[i].back().first > len) {
		len = sub[i].back().first;
		from = i;
	}
	return from;
}

void swap(int i, int j, int &cur) 
{
	if (cur == i) cur = j;
	else if (cur == j) cur = i;
	std::swap(sub[i], sub[j]);
}

void update_ans(int ind) 
{
	ans.push_back(sub[ind].back().second);
	sub[ind].pop_back();
}

std::vector<int> createFunTour(int n, int q) 
{
	int ind = 0;
	for (int i = 0; i < n; ++i) {
		size[i] = attractionsBehind(0, i);
		if (size[i] * 2 > n && size[i] < size[ind]) ind = i;
	}
	for (int i = 0; i < n; ++i) {
		dist[i] = hoursRequired(ind, i);
		if (dist[i] == 1) root.push_back(i);
	}
	for (int i = 0; i < n; ++i) if (i != ind) {
		std::pair<int, int> cur(dist[i], i);
		if (hoursRequired(i, root[0]) == dist[i] - 1) sub[0].push_back(cur);
		else if (hoursRequired(i, root[1]) == dist[i] - 1) sub[1].push_back(cur);
		else sub[2].push_back(cur);
	}
	for (int i = 0; i < 3; ++i) std::sort(sub[i].begin(), sub[i].end());
	int cur = -1;
	while (max_size() * 2 < n - 1) {
		cur = get_far(cur);
		update_ans(cur);
		--n;
	}
	int far_from = get_far(-1);
	if (cur != -1 && far_from != cur) {
		cur = far_from;
		update_ans(cur);
	}
	if (root.size() == 3) {
		if (sub[0].size() < sub[1].size()) swap(0, 1, cur);
		if (sub[1].size() < sub[2].size()) swap(1, 2, cur);
		if (sub[0].size() < sub[1].size()) swap(0, 1, cur);
		root.pop_back();
	}
	if (cur == 2) cur = 1;
	sub[1].insert(sub[1].end(), sub[2].begin(), sub[2].end());
	std::sort(sub[1].begin(), sub[1].end());
	while ((cur = get_far(cur)) != -1) update_ans(cur);
	ans.push_back(ind);
	if ((cur = get_far(cur)) != -1) update_ans(cur);
	return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	0 ms	204 KB	Output is correct
19	Correct	0 ms	204 KB	Output is correct
20	Correct	0 ms	204 KB	Output is correct
21	Correct	0 ms	204 KB	Output is correct
22	Correct	1 ms	204 KB	Output is correct
23	Correct	0 ms	204 KB	Output is correct
24	Correct	1 ms	332 KB	Output is correct
25	Correct	0 ms	204 KB	Output is correct
26	Correct	0 ms	204 KB	Output is correct
27	Correct	1 ms	204 KB	Output is correct
28	Correct	0 ms	204 KB	Output is correct
29	Correct	1 ms	332 KB	Output is correct
30	Correct	0 ms	204 KB	Output is correct
31	Correct	1 ms	204 KB	Output is correct
32	Correct	1 ms	332 KB	Output is correct
33	Correct	0 ms	204 KB	Output is correct
34	Correct	1 ms	332 KB	Output is correct
35	Correct	1 ms	332 KB	Output is correct
36	Correct	1 ms	332 KB	Output is correct
37	Correct	1 ms	204 KB	Output is correct
38	Correct	1 ms	332 KB	Output is correct
39	Correct	1 ms	332 KB	Output is correct
40	Correct	1 ms	332 KB	Output is correct
41	Correct	1 ms	204 KB	Output is correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	134 ms	17224 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	2 ms	460 KB	Output is correct
21	Correct	3 ms	716 KB	Output is correct
22	Correct	7 ms	1356 KB	Output is correct
23	Correct	13 ms	2432 KB	Output is correct
24	Correct	17 ms	3272 KB	Output is correct
25	Correct	75 ms	9928 KB	Output is correct

Subtask #4
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	11 ms	1876 KB	Output is correct
15	Correct	143 ms	16800 KB	Output is correct
16	Correct	150 ms	16732 KB	Output is correct
17	Correct	26 ms	4092 KB	Output is correct
18	Correct	65 ms	7832 KB	Output is correct
19	Correct	107 ms	13332 KB	Output is correct
20	Correct	5 ms	844 KB	Output is correct

Subtask #5
34.0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	0 ms	204 KB	Output is correct
19	Correct	0 ms	204 KB	Output is correct
20	Correct	0 ms	204 KB	Output is correct
21	Correct	0 ms	204 KB	Output is correct
22	Correct	1 ms	204 KB	Output is correct
23	Correct	0 ms	204 KB	Output is correct
24	Correct	1 ms	332 KB	Output is correct
25	Correct	0 ms	204 KB	Output is correct
26	Correct	0 ms	204 KB	Output is correct
27	Correct	1 ms	204 KB	Output is correct
28	Correct	0 ms	204 KB	Output is correct
29	Correct	1 ms	332 KB	Output is correct
30	Correct	0 ms	204 KB	Output is correct
31	Correct	1 ms	204 KB	Output is correct
32	Correct	1 ms	332 KB	Output is correct
33	Correct	0 ms	204 KB	Output is correct
34	Correct	1 ms	332 KB	Output is correct
35	Correct	1 ms	332 KB	Output is correct
36	Correct	1 ms	332 KB	Output is correct
37	Correct	1 ms	204 KB	Output is correct
38	Correct	1 ms	332 KB	Output is correct
39	Correct	1 ms	332 KB	Output is correct
40	Correct	1 ms	332 KB	Output is correct
41	Correct	1 ms	204 KB	Output is correct
42	Correct	1 ms	332 KB	Output is correct
43	Correct	1 ms	332 KB	Output is correct
44	Correct	134 ms	17224 KB	Output is correct
45	Correct	1 ms	332 KB	Output is correct
46	Correct	2 ms	460 KB	Output is correct
47	Correct	3 ms	716 KB	Output is correct
48	Correct	7 ms	1356 KB	Output is correct
49	Correct	13 ms	2432 KB	Output is correct
50	Correct	17 ms	3272 KB	Output is correct
51	Correct	75 ms	9928 KB	Output is correct
52	Correct	1 ms	332 KB	Output is correct
53	Correct	11 ms	1876 KB	Output is correct
54	Correct	143 ms	16800 KB	Output is correct
55	Correct	150 ms	16732 KB	Output is correct
56	Correct	26 ms	4092 KB	Output is correct
57	Correct	65 ms	7832 KB	Output is correct
58	Correct	107 ms	13332 KB	Output is correct
59	Correct	5 ms	844 KB	Output is correct
60	Correct	190 ms	16956 KB	Output is correct
61	Correct	235 ms	19384 KB	Output is correct
62	Correct	208 ms	17340 KB	Output is correct
63	Correct	213 ms	21184 KB	Output is correct
64	Correct	233 ms	20856 KB	Output is correct
65	Correct	213 ms	17088 KB	Output is correct
66	Correct	265 ms	19380 KB	Output is correct
67	Correct	232 ms	20840 KB	Output is correct
68	Correct	257 ms	20256 KB	Output is correct
69	Correct	275 ms	21564 KB	Output is correct
70	Correct	194 ms	17416 KB	Output is correct
71	Correct	201 ms	21060 KB	Output is correct
72	Correct	228 ms	19436 KB	Output is correct
73	Correct	227 ms	20060 KB	Output is correct
74	Correct	284 ms	21816 KB	Output is correct
75	Correct	188 ms	17212 KB	Output is correct
76	Correct	233 ms	21252 KB	Output is correct
77	Correct	220 ms	21224 KB	Output is correct
78	Correct	210 ms	20204 KB	Output is correct
79	Correct	280 ms	21552 KB	Output is correct
80	Correct	268 ms	21696 KB	Output is correct
81	Correct	209 ms	16828 KB	Output is correct
82	Correct	216 ms	17468 KB	Output is correct
83	Correct	232 ms	16968 KB	Output is correct
84	Correct	74 ms	7272 KB	Output is correct

답안 #468140

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 16.0 / 16.0

Subtask #3 21.0 / 21.0

Subtask #4 19.0 / 19.0

Subtask #5 34.0 / 34.0

Subtask #1
10.0 / 10.0

Subtask #2
16.0 / 16.0

Subtask #3
21.0 / 21.0

Subtask #4
19.0 / 19.0

Subtask #5
34.0 / 34.0