# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
466523 | 2021-08-19T14:42:46 Z | zigui | Fun Tour (APIO20_fun) | C++17 | 263 ms | 42496 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; while (r != 1) { assert(subtree[a].size() >= 1); ll loc = subtree[a][subtree[a].size() - 1].second; //assert(asdf[loc] == a); ans.push_back(loc); subtree[a].pop_back(); ll b, c; b = a + 1; c = a + 2; b %= 3; c %= 3; if (max({ subtree[0].size(), subtree[1].size(), subtree[2].size() }) == (r - 1) / 2) { chk = 1; ll mx = max({ subtree[0].size(), subtree[1].size(), subtree[2].size() }); ll na; if (mx == subtree[0].size()) na = 0; if (mx == subtree[1].size()) na = 1; if (mx == subtree[2].size()) na = 2; if (na == a) { 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 a = na; } 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); } assert(!(subtree[0].size() + subtree[1].size() + subtree[2].size())); assert(ans.size() == N); return ans; }
Compilation message
# | Verdict | Execution time | Memory | 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 | 1 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 | 292 KB | Output is correct |
9 | Correct | 1 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 | 1 ms | 204 KB | Output is correct |
13 | Correct | 0 ms | 204 KB | Output is correct |
14 | Correct | 1 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 | 1 ms | 204 KB | Output is correct |
19 | Correct | 1 ms | 204 KB | Output is correct |
20 | Correct | 0 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | 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 | 1 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 | 292 KB | Output is correct |
9 | Correct | 1 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 | 1 ms | 204 KB | Output is correct |
13 | Correct | 0 ms | 204 KB | Output is correct |
14 | Correct | 1 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 | 1 ms | 204 KB | Output is correct |
19 | Correct | 1 ms | 204 KB | Output is correct |
20 | Correct | 0 ms | 204 KB | Output is correct |
21 | Correct | 1 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 | 1 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 | 1 ms | 204 KB | Output is correct |
29 | Correct | 1 ms | 332 KB | Output is correct |
30 | Correct | 1 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 | 1 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 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 1 ms | 204 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 0 ms | 204 KB | Output is correct |
7 | Correct | 1 ms | 292 KB | Output is correct |
8 | Correct | 1 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 | 1 ms | 204 KB | Output is correct |
12 | Correct | 1 ms | 332 KB | Output is correct |
13 | Correct | 1 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 | 145 ms | 17624 KB | Output is correct |
19 | Correct | 2 ms | 332 KB | Output is correct |
20 | Correct | 2 ms | 588 KB | Output is correct |
21 | Correct | 4 ms | 716 KB | Output is correct |
22 | Correct | 7 ms | 1356 KB | Output is correct |
23 | Correct | 14 ms | 2484 KB | Output is correct |
24 | Correct | 23 ms | 3288 KB | Output is correct |
25 | Correct | 84 ms | 10240 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 1 ms | 204 KB | Output is correct |
5 | Correct | 1 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 | 1 ms | 332 KB | Output is correct |
9 | Correct | 1 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 | 1 ms | 204 KB | Output is correct |
13 | Correct | 1 ms | 420 KB | Output is correct |
14 | Correct | 14 ms | 1868 KB | Output is correct |
15 | Correct | 151 ms | 17732 KB | Output is correct |
16 | Correct | 172 ms | 17468 KB | Output is correct |
17 | Correct | 28 ms | 4392 KB | Output is correct |
18 | Correct | 73 ms | 8240 KB | Output is correct |
19 | Correct | 111 ms | 13932 KB | Output is correct |
20 | Correct | 5 ms | 844 KB | Output is correct |
# | Verdict | Execution time | Memory | 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 | 1 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 | 292 KB | Output is correct |
9 | Correct | 1 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 | 1 ms | 204 KB | Output is correct |
13 | Correct | 0 ms | 204 KB | Output is correct |
14 | Correct | 1 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 | 1 ms | 204 KB | Output is correct |
19 | Correct | 1 ms | 204 KB | Output is correct |
20 | Correct | 0 ms | 204 KB | Output is correct |
21 | Correct | 1 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 | 1 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 | 1 ms | 204 KB | Output is correct |
29 | Correct | 1 ms | 332 KB | Output is correct |
30 | Correct | 1 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 | 1 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 | 145 ms | 17624 KB | Output is correct |
45 | Correct | 2 ms | 332 KB | Output is correct |
46 | Correct | 2 ms | 588 KB | Output is correct |
47 | Correct | 4 ms | 716 KB | Output is correct |
48 | Correct | 7 ms | 1356 KB | Output is correct |
49 | Correct | 14 ms | 2484 KB | Output is correct |
50 | Correct | 23 ms | 3288 KB | Output is correct |
51 | Correct | 84 ms | 10240 KB | Output is correct |
52 | Correct | 1 ms | 420 KB | Output is correct |
53 | Correct | 14 ms | 1868 KB | Output is correct |
54 | Correct | 151 ms | 17732 KB | Output is correct |
55 | Correct | 172 ms | 17468 KB | Output is correct |
56 | Correct | 28 ms | 4392 KB | Output is correct |
57 | Correct | 73 ms | 8240 KB | Output is correct |
58 | Correct | 111 ms | 13932 KB | Output is correct |
59 | Correct | 5 ms | 844 KB | Output is correct |
60 | Correct | 198 ms | 17448 KB | Output is correct |
61 | Correct | 194 ms | 19620 KB | Output is correct |
62 | Correct | 205 ms | 17352 KB | Output is correct |
63 | Correct | 215 ms | 21092 KB | Output is correct |
64 | Correct | 231 ms | 21176 KB | Output is correct |
65 | Correct | 219 ms | 18080 KB | Output is correct |
66 | Correct | 211 ms | 19896 KB | Output is correct |
67 | Correct | 208 ms | 21588 KB | Output is correct |
68 | Correct | 230 ms | 20976 KB | Output is correct |
69 | Correct | 253 ms | 22484 KB | Output is correct |
70 | Correct | 195 ms | 17592 KB | Output is correct |
71 | Correct | 207 ms | 21572 KB | Output is correct |
72 | Correct | 203 ms | 20280 KB | Output is correct |
73 | Correct | 259 ms | 20920 KB | Output is correct |
74 | Correct | 263 ms | 22456 KB | Output is correct |
75 | Correct | 211 ms | 17848 KB | Output is correct |
76 | Correct | 210 ms | 21124 KB | Output is correct |
77 | Runtime error | 203 ms | 42496 KB | Execution killed with signal 6 |
78 | Halted | 0 ms | 0 KB | - |