# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
430073 |
2021-06-16T11:18:56 Z |
Peti |
Fun Tour (APIO20_fun) |
C++14 |
|
402 ms |
22280 KB |
#include <bits/stdc++.h>
#include "fun.h"
using namespace std;
bool check(vector<pair<int, int>> &v1, vector<pair<int, int>> &v2, vector<pair<int, int>> &v3, int d){
return max(d, (v3.empty() ? 0 : v3.back().first)) >= max((v1.empty() ? 0 : v1.back().first), (v2.empty() ? 0 : v2.back().first));
}
void combine(vector<pair<int, int>> &v1, vector<pair<int, int>> &v2, vector<pair<int, int>> &v3, int &last, int d){
if(v3.size() == 0) return;
if(v1.size() + v2.size() <= v3.size() && (last == 3 || check(v1, v2, v3, d))){
for(auto p : v2)
v1.push_back(p);
sort(v1.begin(), v1.end());
swap(v2, v3);
v3.clear();
if(last == 2)
last = 1;
else if(last == 3)
last = 2;
} else if(v1.size() + v3.size() <= v2.size() && (last == 2 || check(v1, v3, v2, d))){
for(auto p : v3)
v1.push_back(p);
sort(v1.begin(), v1.end());
v3.clear();
if(last == 3)
last = 1;
} else if(v2.size() + v3.size() <= v1.size() && (last == 1 || check(v2, v3, v1, d))){
for(auto p : v3)
v2.push_back(p);
sort(v2.begin(), v2.end());
v3.clear();
if(last == 3)
last = 2;
}
}
vector<int> createFunTour(int N, int Q) {
int c = 0;
for(int i = 1; i < N; i++){
int ans = attractionsBehind(c, i);
if(ans*2 > N)
c = i;
}
//cout<<"centroid: "<<c<<"\n";
vector<int> tavC(N), inds;
for(int i = 0; i < N; i++){
tavC[i] = hoursRequired(c, i);
if(tavC[i] == 1)
inds.push_back(i);
}
if(inds.size() < 2)
return {0, 1};
vector<int> tav1(N), tav2(N);
for(int i = 0; i < N; i++)
tav1[i] = hoursRequired(inds[0], i);
for(int i = 0; i < N; i++)
tav2[i] = hoursRequired(inds[1], i);
vector<pair<int, int>> v1, v2, v3;
for(int i = 0; i < N; i++){
if(i == c) continue;
if(tav1[i] < tav2[i] && tav1[i] < tavC[i])
v1.push_back(make_pair(tavC[i], i));
else if(tav2[i] < tav1[i] && tav2[i] < tavC[i])
v2.push_back(make_pair(tavC[i], i));
else
v3.push_back(make_pair(tavC[i], i));
}
if(v1.size() <= v2.size() && v1.size() <= v3.size())
v1.push_back(make_pair(0, c));
else if(v2.size() <= v1.size() && v2.size() <= v3.size())
v2.push_back(make_pair(0, c));
else
v3.push_back(make_pair(0, c));
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
sort(v3.begin(), v3.end());
/*cout<<"csop1\n";
for(auto p : v1)
cout<<p.first<<" "<<p.second<<"\n";
cout<<"csop2\n";
for(auto p : v2)
cout<<p.first<<" "<<p.second<<"\n";
cout<<"csop3\n";
for(auto p : v3)
cout<<p.first<<" "<<p.second<<"\n";*/
int last = 0, d = (int)1e9;
combine(v1, v2, v3, last, d);
if(v3.size() == 0){
last = 2;
if(v2.size() > v1.size())
last = 1;
} else{
last = 1;
if(v2.back().first > v1.back().first)
last = 2;
if(v3.back().first > v2.back().first && v3.back().first > v1.back().first)
last = 3;
last++;
if(last == 4)
last = 1;
}
vector<int> ret;
while(!v1.empty() || !v2.empty() || !v3.empty()){
if(v3.empty()){
if(last == 1){
if(v2.empty()) return ret;
ret.push_back(v2.back().second);
last = 2;
v2.pop_back();
} else{
if(v1.empty()) return ret;
ret.push_back(v1.back().second);
last = 1;
v1.pop_back();
}
} else{
if(last == 1){
if(v2.empty() || v3.empty()) return {};
if(v2.back().first > v3.back().first){
ret.push_back(v2.back().second);
last = 2;
d = v2.back().first;
v2.pop_back();
} else{
ret.push_back(v3.back().second);
last = 3;
d = v3.back().first;
v3.pop_back();
}
} else if(last == 2){
if(v2.empty() || v3.empty()) return {};
if(v1.back().first > v3.back().first){
ret.push_back(v1.back().second);
last = 1;
d = v1.back().first;
v1.pop_back();
} else{
ret.push_back(v3.back().second);
last = 3;
d = v3.back().first;
v3.pop_back();
}
} else{
if(v1.empty() || v2.empty()) return {};
if(v1.back().first > v2.back().first){
ret.push_back(v1.back().second);
last = 1;
d = v1.back().first;
v1.pop_back();
} else{
ret.push_back(v2.back().second);
last = 2;
d = v2.back().first;
v2.pop_back();
}
}
combine(v1, v2, v3, last, d);
}
}
return ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 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 |
2 ms |
204 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 |
204 KB |
Output is correct |
17 |
Correct |
1 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 |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 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 |
2 ms |
204 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 |
204 KB |
Output is correct |
17 |
Correct |
1 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 |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 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 |
204 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 |
384 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 |
204 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
41 |
Correct |
2 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 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 |
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 |
162 ms |
16372 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 |
8 ms |
1272 KB |
Output is correct |
23 |
Correct |
16 ms |
2344 KB |
Output is correct |
24 |
Correct |
19 ms |
3040 KB |
Output is correct |
25 |
Correct |
83 ms |
9388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
2 ms |
204 KB |
Output is correct |
6 |
Correct |
1 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 |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
2 ms |
332 KB |
Output is correct |
14 |
Correct |
16 ms |
1760 KB |
Output is correct |
15 |
Correct |
167 ms |
16060 KB |
Output is correct |
16 |
Correct |
193 ms |
15820 KB |
Output is correct |
17 |
Correct |
30 ms |
3884 KB |
Output is correct |
18 |
Correct |
70 ms |
7480 KB |
Output is correct |
19 |
Correct |
120 ms |
12676 KB |
Output is correct |
20 |
Correct |
27 ms |
784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 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 |
2 ms |
204 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 |
204 KB |
Output is correct |
17 |
Correct |
1 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 |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 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 |
204 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 |
384 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 |
204 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
41 |
Correct |
2 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 |
162 ms |
16372 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 |
8 ms |
1272 KB |
Output is correct |
49 |
Correct |
16 ms |
2344 KB |
Output is correct |
50 |
Correct |
19 ms |
3040 KB |
Output is correct |
51 |
Correct |
83 ms |
9388 KB |
Output is correct |
52 |
Correct |
2 ms |
332 KB |
Output is correct |
53 |
Correct |
16 ms |
1760 KB |
Output is correct |
54 |
Correct |
167 ms |
16060 KB |
Output is correct |
55 |
Correct |
193 ms |
15820 KB |
Output is correct |
56 |
Correct |
30 ms |
3884 KB |
Output is correct |
57 |
Correct |
70 ms |
7480 KB |
Output is correct |
58 |
Correct |
120 ms |
12676 KB |
Output is correct |
59 |
Correct |
27 ms |
784 KB |
Output is correct |
60 |
Correct |
233 ms |
16044 KB |
Output is correct |
61 |
Correct |
385 ms |
18496 KB |
Output is correct |
62 |
Correct |
232 ms |
16572 KB |
Output is correct |
63 |
Correct |
262 ms |
20500 KB |
Output is correct |
64 |
Correct |
323 ms |
19888 KB |
Output is correct |
65 |
Correct |
303 ms |
16284 KB |
Output is correct |
66 |
Correct |
325 ms |
18468 KB |
Output is correct |
67 |
Correct |
298 ms |
20268 KB |
Output is correct |
68 |
Correct |
338 ms |
19576 KB |
Output is correct |
69 |
Correct |
375 ms |
20796 KB |
Output is correct |
70 |
Correct |
248 ms |
16392 KB |
Output is correct |
71 |
Correct |
298 ms |
20208 KB |
Output is correct |
72 |
Correct |
347 ms |
18708 KB |
Output is correct |
73 |
Correct |
311 ms |
19368 KB |
Output is correct |
74 |
Correct |
402 ms |
21044 KB |
Output is correct |
75 |
Correct |
239 ms |
16608 KB |
Output is correct |
76 |
Correct |
239 ms |
20388 KB |
Output is correct |
77 |
Correct |
251 ms |
21640 KB |
Output is correct |
78 |
Correct |
245 ms |
20624 KB |
Output is correct |
79 |
Correct |
375 ms |
21936 KB |
Output is correct |
80 |
Correct |
332 ms |
22280 KB |
Output is correct |
81 |
Correct |
248 ms |
17200 KB |
Output is correct |
82 |
Correct |
267 ms |
17528 KB |
Output is correct |
83 |
Correct |
245 ms |
17296 KB |
Output is correct |
84 |
Correct |
86 ms |
7324 KB |
Output is correct |