# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
466645 | 2021-08-19T23:09:36 Z | flappybird | 즐거운 행로 (APIO20_fun) | C++14 | 282 ms | 21432 KB |
#include "fun.h" #include <bits/stdc++.h> #include <cassert> #define e(v) ( ( (v).empty() ) ? (pair<int, int>(-1, -1) ) : ( (v)[(v).size()-1] ) ) using namespace std; typedef int ll; vector<int> createFunTour(int N, int Q) { if (N == 2) { vector<ll> v; v.push_back(0); v.push_back(1); return v; } vector<ll> res; ll i; for (i = 0; i < N; i++) res.push_back(attractionsBehind(0, i)); ll c = 0; ll mn = 1010101010; for (i = 0; i < N; i++) { if (res[i] >= (N + 1) / 2) { if (mn > res[i]) mn = res[i], c = i; } } vector<pair<ll, ll>> dis; vector<vector<pair<ll, ll>>> subtree; subtree.resize(3); ll num; for (i = 0; i < N; i++) { if (i == c) continue; dis.push_back({ hoursRequired(i, c), i }); } sort(dis.begin(), dis.end()); num = 1; subtree[0].push_back(dis[0]); for (i = 1; i < dis.size(); i++) { ll j; for (j = 0; j < num; j++) { if (j == 2) break; if (hoursRequired(dis[i].second, subtree[j][0].second) != dis[i].first + subtree[j][0].first) break; } if (j == num) num++; subtree[j].push_back(dis[i]); } vector<ll> ans; assert(num >= 2); if (num == 2) { ll r = N; ll a; if (subtree[0].size() < subtree[1].size()) a = 1; else a = 0; while (r != 1) { ans.push_back(e(subtree[a]).second); subtree[a].pop_back(); a = !a; r--; } ans.push_back(c); } else { ll chk = 0; ll r = N; ll a; vector<ll> asdf(N); if (e(subtree[0]).first > e(subtree[1]).first) swap(subtree[0], subtree[1]); if (e(subtree[1]).first > e(subtree[2]).first) swap(subtree[1], subtree[2]); if (e(subtree[0]).first == e(subtree[1]).first && subtree[0].size() > subtree[1].size()) swap(subtree[0], subtree[1]); if (e(subtree[1]).first == e(subtree[2]).first && subtree[1].size() > subtree[2].size()) swap(subtree[1], subtree[2]); for (i = 0; i < 3; i++) { for (auto x : subtree[i]) { assert(!asdf[x.second]); asdf[x.second]++; } } for (i = 0; i < N; i++) { assert(asdf[i] <= 1); } a = 2; ll abc = c; ll memo = -1; ll chkchk = 0; if (2 * max({ subtree[0].size(), subtree[1].size(), subtree[2].size() }) >= N - 1) { chk = 1; ll mx = max({ subtree[0].size(), subtree[1].size(), subtree[2].size() }); ll na = a; if (a != 0 && mx == subtree[0].size()) na = 0; if (a != 1 && mx == subtree[1].size()) na = 1; if (a != 2 && mx == subtree[2].size()) na = 2; memo = na; a = na; chkchk = 1; } while (r != 1) { ll b, c; b = a + 1; c = a + 2; b %= 3; c %= 3; ll loc = subtree[a][subtree[a].size() - 1].second; ll d = subtree[a][subtree[a].size() - 1].first; //assert(asdf[loc] == a); ans.push_back(loc); subtree[a].pop_back(); if (chk || 2 * max({ subtree[0].size(), subtree[1].size(), subtree[2].size() }) >= (r)-2) { chk = 1; ll mx = max({ subtree[0].size(), subtree[1].size(), subtree[2].size() }); ll na = a; if (a != 0 && mx == subtree[0].size()) na = 0; if (a != 1 && mx == subtree[1].size()) na = 1; if (a != 2 && mx == subtree[2].size()) na = 2; if (memo == -1) memo = na; if (memo == a) { if (subtree[b].empty() && subtree[c].empty()) { if (subtree[a].size()) ans.push_back(e(subtree[a]).second); ans.push_back(abc); assert(ans.size() == N); return ans; } if (e(subtree[b]).first < e(subtree[c]).first) a = c; else if (e(subtree[b]).first == e(subtree[c]).first && (subtree[b].size() < subtree[c].size())) a = c; else a = b; } else if (chkchk) a = memo; else if (memo == b) { chkchk = 1; if (d < e(subtree[c]).first) a = c; else a = b; } else { chkchk = 1; if (d < e(subtree[b]).first) a = b; else a = c; } } else { if (e(subtree[b]).first < e(subtree[c]).first) a = c; else if (e(subtree[b]).first == e(subtree[c]).first && (subtree[b].size() < subtree[c].size())) a = c; else a = b; } r--; } for (i = 0; i < ans.size(); i++) assert(ans[i] != c); ans.push_back(c); } vector<ll> asdfsdf(N); for (i = 0; i < N; i++) asdfsdf[ans[i]] = 1; for (i = 0; i < N; i++) assert(asdfsdf[i]); return ans; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 1 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 | 1 ms | 204 KB | Output is correct |
8 | Correct | 0 ms | 204 KB | Output is correct |
9 | Correct | 0 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 | 1 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 | 0 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 |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 1 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 | 1 ms | 204 KB | Output is correct |
8 | Correct | 0 ms | 204 KB | Output is correct |
9 | Correct | 0 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 | 1 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 | 0 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 | 0 ms | 204 KB | Output is correct |
23 | Correct | 1 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 | 1 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 | 204 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 |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 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 | 0 ms | 204 KB | Output is correct |
9 | Correct | 0 ms | 204 KB | Output is correct |
10 | Correct | 0 ms | 204 KB | Output is correct |
11 | Correct | 1 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 | 1 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 | 139 ms | 16512 KB | Output is correct |
19 | Correct | 1 ms | 332 KB | Output is correct |
20 | Correct | 2 ms | 460 KB | Output is correct |
21 | Correct | 4 ms | 716 KB | Output is correct |
22 | Correct | 7 ms | 1356 KB | Output is correct |
23 | Correct | 13 ms | 2356 KB | Output is correct |
24 | Correct | 19 ms | 3144 KB | Output is correct |
25 | Correct | 78 ms | 9520 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 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 | 1 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 | 204 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 | 1800 KB | Output is correct |
15 | Correct | 146 ms | 16544 KB | Output is correct |
16 | Correct | 151 ms | 16324 KB | Output is correct |
17 | Correct | 27 ms | 4160 KB | Output is correct |
18 | Correct | 65 ms | 7724 KB | Output is correct |
19 | Correct | 115 ms | 13124 KB | Output is correct |
20 | Correct | 5 ms | 844 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 1 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 | 1 ms | 204 KB | Output is correct |
8 | Correct | 0 ms | 204 KB | Output is correct |
9 | Correct | 0 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 | 1 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 | 0 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 | 0 ms | 204 KB | Output is correct |
23 | Correct | 1 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 | 1 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 | 204 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 | 139 ms | 16512 KB | Output is correct |
45 | Correct | 1 ms | 332 KB | Output is correct |
46 | Correct | 2 ms | 460 KB | Output is correct |
47 | Correct | 4 ms | 716 KB | Output is correct |
48 | Correct | 7 ms | 1356 KB | Output is correct |
49 | Correct | 13 ms | 2356 KB | Output is correct |
50 | Correct | 19 ms | 3144 KB | Output is correct |
51 | Correct | 78 ms | 9520 KB | Output is correct |
52 | Correct | 1 ms | 332 KB | Output is correct |
53 | Correct | 11 ms | 1800 KB | Output is correct |
54 | Correct | 146 ms | 16544 KB | Output is correct |
55 | Correct | 151 ms | 16324 KB | Output is correct |
56 | Correct | 27 ms | 4160 KB | Output is correct |
57 | Correct | 65 ms | 7724 KB | Output is correct |
58 | Correct | 115 ms | 13124 KB | Output is correct |
59 | Correct | 5 ms | 844 KB | Output is correct |
60 | Correct | 197 ms | 16684 KB | Output is correct |
61 | Correct | 191 ms | 18488 KB | Output is correct |
62 | Correct | 197 ms | 16676 KB | Output is correct |
63 | Correct | 219 ms | 19956 KB | Output is correct |
64 | Correct | 242 ms | 19956 KB | Output is correct |
65 | Correct | 206 ms | 16924 KB | Output is correct |
66 | Correct | 211 ms | 18844 KB | Output is correct |
67 | Correct | 203 ms | 20348 KB | Output is correct |
68 | Correct | 235 ms | 19768 KB | Output is correct |
69 | Correct | 246 ms | 21316 KB | Output is correct |
70 | Correct | 227 ms | 16440 KB | Output is correct |
71 | Correct | 210 ms | 20408 KB | Output is correct |
72 | Correct | 207 ms | 19088 KB | Output is correct |
73 | Correct | 213 ms | 19776 KB | Output is correct |
74 | Correct | 282 ms | 21432 KB | Output is correct |
75 | Correct | 197 ms | 16824 KB | Output is correct |
76 | Correct | 209 ms | 19896 KB | Output is correct |
77 | Correct | 231 ms | 20516 KB | Output is correct |
78 | Correct | 198 ms | 19768 KB | Output is correct |
79 | Correct | 242 ms | 20728 KB | Output is correct |
80 | Correct | 245 ms | 21292 KB | Output is correct |
81 | Correct | 201 ms | 16452 KB | Output is correct |
82 | Correct | 199 ms | 16548 KB | Output is correct |
83 | Correct | 203 ms | 16784 KB | Output is correct |
84 | Correct | 77 ms | 7704 KB | Output is correct |