# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
965217 |
2024-04-18T08:26:10 Z |
Pannda |
Fun Tour (APIO20_fun) |
C++17 |
|
114 ms |
15804 KB |
#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> createFunTour(int n, int _400000) {
if (n <= 500) {
auto findFurthest = [&](int u, set<int> dom) {
int v = u;
int dv = 0;
for (int x : dom) {
int dx = hoursRequired(u, x);
if (dx > dv) {
v = x;
dv = dx;
}
}
return v;
};
set<int> rem;
for (int u = 0; u < n; u++) rem.insert(u);
int u = findFurthest(0, rem);
vector<int> res;
for (int i = 0; i < n; i++) {
res.push_back(u);
rem.erase(u);
u = findFurthest(u, rem);
}
return res;
}
int centroid = [&]() -> int {
int res = 0;
int siz = n;
for (int v = 0; v < n; v++) {
int get = attractionsBehind(0, v);
if (get > n / 2 && get < siz) {
res = v;
siz = get;
}
}
return res;
}();
vector<int> dist(n);
for (int u = 0; u < n; u++) dist[u] = hoursRequired(centroid, u);
int d0 = max_element(dist.begin(), dist.end()) - dist.begin();
vector<int> dist0(n);
for (int u = 0; u < n; u++) dist0[u] = hoursRequired(d0, u);
int d1 = max_element(dist0.begin(), dist0.end()) - dist0.begin();
vector<int> dist1(n);
for (int u = 0; u < n; u++) dist1[u] = hoursRequired(d1, u);
array<vector<int>, 3> dom;
for (int u = 0; u < n; u++) {
if (u == centroid) continue;
if (dist0[u] == dist[u] + dist[d0] && dist1[u] == dist[u] + dist[d1]) {
dom[2].push_back(u);
} else if (dist0[u] == dist[u] + dist[d0]) {
dom[1].push_back(u);
} else {
dom[0].push_back(u);
}
}
for (int i = 0; i < 3; i++) {
sort(dom[i].begin(), dom[i].end(), [&](int u, int v) { return dist[u] > dist[v]; });
}
vector<int> order = {0, 1, 2};
sort(order.begin(), order.end(), [&](int i, int j) { return dom[i].size() < dom[j].size(); });
vector<int> res = { centroid };
int last = -1;
while (dom[order[2]].size() < dom[order[0]].size() + dom[order[1]].size()) {
int i0;
int d = n;
for (int ii = 2; ii >= 0; ii--) {
int i = order[ii];
if (i == last) continue;
if (dom[i].empty()) continue;
if (dist[res.back()] + dist[dom[i].back()] < d) {
d = dist[res.back()] + dist[dom[i].back()];
i0 = i;
}
}
res.push_back(dom[i0].back());
if (res.size() >= 3) {
assert(dist[res.end()[-1]] + dist[res.end()[-2]] >= dist[res.end()[-2]] + dist[res.end()[-3]]);
}
dom[i0].pop_back();
last = i0;
sort(order.begin(), order.end(), [&](int i, int j) { return dom[i].size() < dom[j].size(); });
}
bool big = last != order[2];
while (res.size() < n) {
int i0;
if (big) {
i0 = order[2];
} else {
if (dom[order[0]].empty()) i0 = order[1];
else if (dom[order[1]].empty()) i0 = order[0];
else i0 = dist[dom[order[0]].back()] < dist[dom[order[1]].back()] ? order[0] : order[1];
}
res.push_back(dom[i0].back());
if (res.size() >= 3) {
assert(dist[res.end()[-1]] + dist[res.end()[-2]] >= dist[res.end()[-2]] + dist[res.end()[-3]]);
}
dom[i0].pop_back();
big = !big;
}
reverse(res.begin(), res.end());
return res;
}
Compilation message
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:97:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
97 | while (res.size() < n) {
| ~~~~~~~~~~~^~~
fun.cpp:96:31: warning: 'i0' may be used uninitialized in this function [-Wmaybe-uninitialized]
96 | bool big = last != order[2];
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
344 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
344 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
344 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
13 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
344 KB |
Output is correct |
27 |
Correct |
2 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
11 ms |
532 KB |
Output is correct |
30 |
Correct |
1 ms |
344 KB |
Output is correct |
31 |
Correct |
3 ms |
348 KB |
Output is correct |
32 |
Correct |
4 ms |
348 KB |
Output is correct |
33 |
Correct |
2 ms |
348 KB |
Output is correct |
34 |
Correct |
9 ms |
600 KB |
Output is correct |
35 |
Correct |
11 ms |
348 KB |
Output is correct |
36 |
Correct |
12 ms |
528 KB |
Output is correct |
37 |
Correct |
1 ms |
348 KB |
Output is correct |
38 |
Correct |
11 ms |
528 KB |
Output is correct |
39 |
Correct |
4 ms |
348 KB |
Output is correct |
40 |
Correct |
8 ms |
348 KB |
Output is correct |
41 |
Correct |
2 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
13 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
2 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
114 ms |
15804 KB |
Output is correct |
19 |
Correct |
1 ms |
344 KB |
Output is correct |
20 |
Correct |
2 ms |
600 KB |
Output is correct |
21 |
Correct |
4 ms |
604 KB |
Output is correct |
22 |
Correct |
7 ms |
1384 KB |
Output is correct |
23 |
Correct |
10 ms |
2392 KB |
Output is correct |
24 |
Correct |
16 ms |
2904 KB |
Output is correct |
25 |
Correct |
62 ms |
9064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
11 ms |
532 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
3 ms |
348 KB |
Output is correct |
11 |
Correct |
4 ms |
348 KB |
Output is correct |
12 |
Correct |
2 ms |
348 KB |
Output is correct |
13 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
344 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
344 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
13 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
344 KB |
Output is correct |
27 |
Correct |
2 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
11 ms |
532 KB |
Output is correct |
30 |
Correct |
1 ms |
344 KB |
Output is correct |
31 |
Correct |
3 ms |
348 KB |
Output is correct |
32 |
Correct |
4 ms |
348 KB |
Output is correct |
33 |
Correct |
2 ms |
348 KB |
Output is correct |
34 |
Correct |
9 ms |
600 KB |
Output is correct |
35 |
Correct |
11 ms |
348 KB |
Output is correct |
36 |
Correct |
12 ms |
528 KB |
Output is correct |
37 |
Correct |
1 ms |
348 KB |
Output is correct |
38 |
Correct |
11 ms |
528 KB |
Output is correct |
39 |
Correct |
4 ms |
348 KB |
Output is correct |
40 |
Correct |
8 ms |
348 KB |
Output is correct |
41 |
Correct |
2 ms |
348 KB |
Output is correct |
42 |
Correct |
1 ms |
348 KB |
Output is correct |
43 |
Correct |
1 ms |
344 KB |
Output is correct |
44 |
Correct |
114 ms |
15804 KB |
Output is correct |
45 |
Correct |
1 ms |
344 KB |
Output is correct |
46 |
Correct |
2 ms |
600 KB |
Output is correct |
47 |
Correct |
4 ms |
604 KB |
Output is correct |
48 |
Correct |
7 ms |
1384 KB |
Output is correct |
49 |
Correct |
10 ms |
2392 KB |
Output is correct |
50 |
Correct |
16 ms |
2904 KB |
Output is correct |
51 |
Correct |
62 ms |
9064 KB |
Output is correct |
52 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
53 |
Halted |
0 ms |
0 KB |
- |