# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
736492 | 2023-05-05T18:30:16 Z | GusterGoose27 | 즐거운 행로 (APIO20_fun) | C++17 | 244 ms | 21756 KB |
#include "fun.h" #include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; const int MAXN = 1e5; int cent_dist[MAXN]; priority_queue<pii> bucket[3]; int assign[MAXN]; bool used[MAXN]; vector<int> ans; int p; pii curv; int get_mx() { int bst = 0; for (int i = 1; i < 3; i++) { if (bucket[i].size() > bucket[bst].size()) bst = i; } return bst; } void add(int i) { if (i == -1) { cout << "-1 query\n"; assert(false); } assert(i != p); p = i; ans.push_back(bucket[i].top().second); assert(assign[bucket[i].top().second] == i); curv = bucket[i].top(); bucket[i].pop(); } vector<int> createFunTour(int n, int q) { if (n == 2) { vector<int> v(2); v[0] = 0; v[1] = 1; return v; } int cent = 0; int sz = n; for (int i = 1; i < n; i++) { int cur = attractionsBehind(0, i); if (cur < sz && cur >= (n+1)/2) { sz = cur; cent = i; } } vector<int> adj; for (int i = 0; i < n; i++) { if (i == cent) { cent_dist[i] = 0; continue; } cent_dist[i] = hoursRequired(i, cent); if (cent_dist[i] == 1) adj.push_back(i); } used[cent] = 1; assert(adj.size() >= 2); for (int i = 0; i < 2; i++) { bucket[i].push(pii(1, adj[i])); assign[adj[i]] = i; used[adj[i]] = 1; for (int j = 0; j < n; j++) { if (cent_dist[j] < 2) continue; int d = hoursRequired(j, adj[i]); if (d == cent_dist[j]-1) { bucket[i].push(pii(cent_dist[j], j)); assign[j] = i; used[j] = 1; } } } for (int i = 0; i < n; i++) { if (!used[i]) { bucket[2].push(pii(cent_dist[i], i)); assign[i] = 2; } } p = -1; curv = pii(n, 0); for (int i = 0; i < n-1; i++) { int mx = get_mx(); if (mx != p && 2*bucket[mx].size() >= n-1-i) { // if we are not at the mx we need to get ther int v = -1; for (int j = 0; j < 3; j++) { if (j == p) continue; if (!bucket[j].empty() && (v == -1 || bucket[j].top() > bucket[v].top())) v = j; } if (v == mx || curv > bucket[v].top()) add(mx); else { assert(2*bucket[mx].size() == n-1-i); add(v); } } else { int v = -1; for (int j = 0; j < 3; j++) { if (j == p) continue; if (!bucket[j].empty() && (v == -1 || bucket[j].top() > bucket[v].top())) v = j; } add(v); } } ans.push_back(cent); assign[cent] = -1; p = n; for (int i = 0; i < n-1; i++) { // assert(cent_dist[ans[i]]+cent_dist[ans[i+1]] <= p); p = cent_dist[ans[i]]+cent_dist[ans[i+1]]; assert(assign[ans[i]] != assign[ans[i+1]]); } return ans; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | 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 | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 0 ms | 212 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 0 ms | 212 KB | Output is correct |
11 | Correct | 0 ms | 212 KB | Output is correct |
12 | Correct | 0 ms | 212 KB | Output is correct |
13 | Correct | 0 ms | 212 KB | Output is correct |
14 | Correct | 1 ms | 212 KB | Output is correct |
15 | Correct | 0 ms | 212 KB | Output is correct |
16 | Correct | 0 ms | 212 KB | Output is correct |
17 | Correct | 0 ms | 212 KB | Output is correct |
18 | Correct | 0 ms | 212 KB | Output is correct |
19 | Correct | 0 ms | 212 KB | Output is correct |
20 | Correct | 0 ms | 212 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | 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 | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 0 ms | 212 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 0 ms | 212 KB | Output is correct |
11 | Correct | 0 ms | 212 KB | Output is correct |
12 | Correct | 0 ms | 212 KB | Output is correct |
13 | Correct | 0 ms | 212 KB | Output is correct |
14 | Correct | 1 ms | 212 KB | Output is correct |
15 | Correct | 0 ms | 212 KB | Output is correct |
16 | Correct | 0 ms | 212 KB | Output is correct |
17 | Correct | 0 ms | 212 KB | Output is correct |
18 | Correct | 0 ms | 212 KB | Output is correct |
19 | Correct | 0 ms | 212 KB | Output is correct |
20 | Correct | 0 ms | 212 KB | Output is correct |
21 | Correct | 0 ms | 212 KB | Output is correct |
22 | Correct | 1 ms | 212 KB | Output is correct |
23 | Correct | 0 ms | 212 KB | Output is correct |
24 | Correct | 1 ms | 340 KB | Output is correct |
25 | Correct | 1 ms | 212 KB | Output is correct |
26 | Correct | 0 ms | 212 KB | Output is correct |
27 | Correct | 1 ms | 340 KB | Output is correct |
28 | Correct | 1 ms | 212 KB | Output is correct |
29 | Correct | 1 ms | 340 KB | Output is correct |
30 | Correct | 0 ms | 212 KB | Output is correct |
31 | Correct | 1 ms | 340 KB | Output is correct |
32 | Correct | 1 ms | 340 KB | Output is correct |
33 | Correct | 0 ms | 212 KB | Output is correct |
34 | Correct | 1 ms | 340 KB | Output is correct |
35 | Correct | 1 ms | 340 KB | Output is correct |
36 | Correct | 1 ms | 340 KB | Output is correct |
37 | Correct | 0 ms | 212 KB | Output is correct |
38 | Correct | 1 ms | 364 KB | Output is correct |
39 | Correct | 1 ms | 340 KB | Output is correct |
40 | Correct | 1 ms | 340 KB | Output is correct |
41 | Correct | 1 ms | 212 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 0 ms | 212 KB | Output is correct |
7 | Correct | 0 ms | 212 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 1 ms | 212 KB | Output is correct |
11 | Correct | 0 ms | 212 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
13 | Correct | 1 ms | 212 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 1 ms | 340 KB | Output is correct |
16 | Correct | 1 ms | 340 KB | Output is correct |
17 | Correct | 1 ms | 340 KB | Output is correct |
18 | Correct | 119 ms | 15852 KB | Output is correct |
19 | Correct | 1 ms | 340 KB | Output is correct |
20 | Correct | 2 ms | 468 KB | Output is correct |
21 | Correct | 3 ms | 724 KB | Output is correct |
22 | Correct | 6 ms | 1260 KB | Output is correct |
23 | Correct | 11 ms | 2312 KB | Output is correct |
24 | Correct | 16 ms | 3020 KB | Output is correct |
25 | Correct | 67 ms | 9296 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | 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 | 340 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 0 ms | 212 KB | Output is correct |
13 | Correct | 1 ms | 340 KB | Output is correct |
14 | Correct | 9 ms | 1748 KB | Output is correct |
15 | Correct | 123 ms | 15816 KB | Output is correct |
16 | Correct | 129 ms | 15688 KB | Output is correct |
17 | Correct | 22 ms | 3916 KB | Output is correct |
18 | Correct | 57 ms | 7360 KB | Output is correct |
19 | Correct | 93 ms | 12384 KB | Output is correct |
20 | Correct | 4 ms | 852 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | 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 | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 0 ms | 212 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 0 ms | 212 KB | Output is correct |
11 | Correct | 0 ms | 212 KB | Output is correct |
12 | Correct | 0 ms | 212 KB | Output is correct |
13 | Correct | 0 ms | 212 KB | Output is correct |
14 | Correct | 1 ms | 212 KB | Output is correct |
15 | Correct | 0 ms | 212 KB | Output is correct |
16 | Correct | 0 ms | 212 KB | Output is correct |
17 | Correct | 0 ms | 212 KB | Output is correct |
18 | Correct | 0 ms | 212 KB | Output is correct |
19 | Correct | 0 ms | 212 KB | Output is correct |
20 | Correct | 0 ms | 212 KB | Output is correct |
21 | Correct | 0 ms | 212 KB | Output is correct |
22 | Correct | 1 ms | 212 KB | Output is correct |
23 | Correct | 0 ms | 212 KB | Output is correct |
24 | Correct | 1 ms | 340 KB | Output is correct |
25 | Correct | 1 ms | 212 KB | Output is correct |
26 | Correct | 0 ms | 212 KB | Output is correct |
27 | Correct | 1 ms | 340 KB | Output is correct |
28 | Correct | 1 ms | 212 KB | Output is correct |
29 | Correct | 1 ms | 340 KB | Output is correct |
30 | Correct | 0 ms | 212 KB | Output is correct |
31 | Correct | 1 ms | 340 KB | Output is correct |
32 | Correct | 1 ms | 340 KB | Output is correct |
33 | Correct | 0 ms | 212 KB | Output is correct |
34 | Correct | 1 ms | 340 KB | Output is correct |
35 | Correct | 1 ms | 340 KB | Output is correct |
36 | Correct | 1 ms | 340 KB | Output is correct |
37 | Correct | 0 ms | 212 KB | Output is correct |
38 | Correct | 1 ms | 364 KB | Output is correct |
39 | Correct | 1 ms | 340 KB | Output is correct |
40 | Correct | 1 ms | 340 KB | Output is correct |
41 | Correct | 1 ms | 212 KB | Output is correct |
42 | Correct | 1 ms | 340 KB | Output is correct |
43 | Correct | 1 ms | 340 KB | Output is correct |
44 | Correct | 119 ms | 15852 KB | Output is correct |
45 | Correct | 1 ms | 340 KB | Output is correct |
46 | Correct | 2 ms | 468 KB | Output is correct |
47 | Correct | 3 ms | 724 KB | Output is correct |
48 | Correct | 6 ms | 1260 KB | Output is correct |
49 | Correct | 11 ms | 2312 KB | Output is correct |
50 | Correct | 16 ms | 3020 KB | Output is correct |
51 | Correct | 67 ms | 9296 KB | Output is correct |
52 | Correct | 1 ms | 340 KB | Output is correct |
53 | Correct | 9 ms | 1748 KB | Output is correct |
54 | Correct | 123 ms | 15816 KB | Output is correct |
55 | Correct | 129 ms | 15688 KB | Output is correct |
56 | Correct | 22 ms | 3916 KB | Output is correct |
57 | Correct | 57 ms | 7360 KB | Output is correct |
58 | Correct | 93 ms | 12384 KB | Output is correct |
59 | Correct | 4 ms | 852 KB | Output is correct |
60 | Correct | 167 ms | 15676 KB | Output is correct |
61 | Correct | 198 ms | 18212 KB | Output is correct |
62 | Correct | 169 ms | 15796 KB | Output is correct |
63 | Correct | 198 ms | 19680 KB | Output is correct |
64 | Correct | 197 ms | 20808 KB | Output is correct |
65 | Correct | 177 ms | 17084 KB | Output is correct |
66 | Correct | 211 ms | 19368 KB | Output is correct |
67 | Correct | 184 ms | 20996 KB | Output is correct |
68 | Correct | 202 ms | 19984 KB | Output is correct |
69 | Correct | 236 ms | 21672 KB | Output is correct |
70 | Correct | 152 ms | 17096 KB | Output is correct |
71 | Correct | 177 ms | 20940 KB | Output is correct |
72 | Correct | 188 ms | 19432 KB | Output is correct |
73 | Correct | 202 ms | 20124 KB | Output is correct |
74 | Correct | 227 ms | 21656 KB | Output is correct |
75 | Correct | 172 ms | 17172 KB | Output is correct |
76 | Correct | 197 ms | 20952 KB | Output is correct |
77 | Correct | 189 ms | 20764 KB | Output is correct |
78 | Correct | 188 ms | 20372 KB | Output is correct |
79 | Correct | 220 ms | 21608 KB | Output is correct |
80 | Correct | 244 ms | 21756 KB | Output is correct |
81 | Correct | 162 ms | 17068 KB | Output is correct |
82 | Correct | 172 ms | 17220 KB | Output is correct |
83 | Correct | 181 ms | 16984 KB | Output is correct |
84 | Correct | 72 ms | 7320 KB | Output is correct |