# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1030496 |
2024-07-22T05:55:38 Z |
vjudge1 |
Fun Tour (APIO20_fun) |
C++17 |
|
91 ms |
16588 KB |
#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#define S(A) sort(A.begin(),A.end())
typedef vector<pair<int,int>> VP;
vector<int>ans;
#define PB push_back
void makedouble(VP a,VP b){
S(b),S(a);
while(a.size()||b.size()){
ans.PB(b.back().second);
b.pop_back();
swap(a,b);
}
}
VP concat(VP a,VP b){
for(auto i:b)
a.PB(i);
return a;
}
void stuff(VP W[3],int a,int b,int c,int k){
if(k-a) makedouble(concat(W[b],W[c]),W[a]);
else makedouble(W[a],concat(W[b],W[c]));
}
vector<int> createFunTour(int N, int Q) {
ans.clear();
if(N==2) return{0,1};
pair<int,int>centroid{N,0};
for(int i=1;i<N;i++) {
int k=attractionsBehind(0,i);
if(k>=(N+1)/2)
centroid=min(centroid,{k,i});
}
int k=centroid.second;
vector<int>subtreez;
VP W[3];
for(int i=0;i<N;i++){
if(i==k) continue;
int C=hoursRequired(k,i);
if(!subtreez.size()){
subtreez.PB(i);
W[0].PB({C,i});
} else if(subtreez.size()==1){
if(W[0][0].first+C-hoursRequired(W[0][0].second,i))
W[0].PB({C,i});
else subtreez.PB(i),W[1].PB({C,i});
} else {
if(W[0][0].first+C-hoursRequired(W[0][0].second,i))
W[0].PB({C,i});
else if(W[1][0].first+C-hoursRequired(W[1][0].second,i))
W[1].PB({C,i});
else W[2].PB({C,i});
}
}
S(W[0]),S(W[1]),S(W[2]);
sort(W,W+3,[](VP &a,VP &b){
return a.size()>b.size();
});
if(W[2].empty()){
makedouble(W[1],W[0]);
} else if(W[0].size()>=W[1].size()+W[2].size()){
makedouble(concat(W[1],W[2]), W[0]);
} else {
sort(W,W+3,[](VP &a,VP &b){
return a.back()>b.back();
});
int prv=0;
ans.PB(W[0].back().second);
W[0].pop_back();
while(1){
int A=W[0].size(),B=W[1].size(),C=W[2].size();
if(A+B==C){
stuff(W,2,0,1,prv);
break;
} else if (A+C==B){
stuff(W,1,2,0,prv);
break;
} else if (B+C==A){
stuff(W,0,1,2,prv);
break;
}
pair<int,int>s{0,0};
for(int i=0;i<3;i++)if(i-prv)
s=max(s,{W[i].back().first,i});
prv=s.second;
ans.PB(W[prv].back().second);
W[prv].pop_back();
}
}
ans.PB(k);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
432 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 |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
432 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 |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
1 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 |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
1 ms |
348 KB |
Output is correct |
32 |
Correct |
1 ms |
348 KB |
Output is correct |
33 |
Correct |
0 ms |
604 KB |
Output is correct |
34 |
Correct |
1 ms |
348 KB |
Output is correct |
35 |
Correct |
1 ms |
348 KB |
Output is correct |
36 |
Correct |
1 ms |
344 KB |
Output is correct |
37 |
Correct |
1 ms |
348 KB |
Output is correct |
38 |
Correct |
1 ms |
348 KB |
Output is correct |
39 |
Correct |
1 ms |
344 KB |
Output is correct |
40 |
Correct |
1 ms |
348 KB |
Output is correct |
41 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
432 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 |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 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 |
77 ms |
16588 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
2 ms |
604 KB |
Output is correct |
21 |
Correct |
2 ms |
860 KB |
Output is correct |
22 |
Correct |
3 ms |
1372 KB |
Output is correct |
23 |
Correct |
8 ms |
2396 KB |
Output is correct |
24 |
Correct |
13 ms |
3108 KB |
Output is correct |
25 |
Correct |
46 ms |
9600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
344 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 |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
6 ms |
1884 KB |
Output is correct |
15 |
Correct |
91 ms |
16132 KB |
Output is correct |
16 |
Correct |
84 ms |
16080 KB |
Output is correct |
17 |
Correct |
14 ms |
3932 KB |
Output is correct |
18 |
Correct |
45 ms |
7452 KB |
Output is correct |
19 |
Correct |
67 ms |
12660 KB |
Output is correct |
20 |
Incorrect |
2 ms |
860 KB |
Tour is not fun |
21 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
432 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 |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
1 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 |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
1 ms |
348 KB |
Output is correct |
32 |
Correct |
1 ms |
348 KB |
Output is correct |
33 |
Correct |
0 ms |
604 KB |
Output is correct |
34 |
Correct |
1 ms |
348 KB |
Output is correct |
35 |
Correct |
1 ms |
348 KB |
Output is correct |
36 |
Correct |
1 ms |
344 KB |
Output is correct |
37 |
Correct |
1 ms |
348 KB |
Output is correct |
38 |
Correct |
1 ms |
348 KB |
Output is correct |
39 |
Correct |
1 ms |
344 KB |
Output is correct |
40 |
Correct |
1 ms |
348 KB |
Output is correct |
41 |
Correct |
1 ms |
344 KB |
Output is correct |
42 |
Correct |
1 ms |
348 KB |
Output is correct |
43 |
Correct |
1 ms |
344 KB |
Output is correct |
44 |
Correct |
77 ms |
16588 KB |
Output is correct |
45 |
Correct |
1 ms |
348 KB |
Output is correct |
46 |
Correct |
2 ms |
604 KB |
Output is correct |
47 |
Correct |
2 ms |
860 KB |
Output is correct |
48 |
Correct |
3 ms |
1372 KB |
Output is correct |
49 |
Correct |
8 ms |
2396 KB |
Output is correct |
50 |
Correct |
13 ms |
3108 KB |
Output is correct |
51 |
Correct |
46 ms |
9600 KB |
Output is correct |
52 |
Correct |
1 ms |
348 KB |
Output is correct |
53 |
Correct |
6 ms |
1884 KB |
Output is correct |
54 |
Correct |
91 ms |
16132 KB |
Output is correct |
55 |
Correct |
84 ms |
16080 KB |
Output is correct |
56 |
Correct |
14 ms |
3932 KB |
Output is correct |
57 |
Correct |
45 ms |
7452 KB |
Output is correct |
58 |
Correct |
67 ms |
12660 KB |
Output is correct |
59 |
Incorrect |
2 ms |
860 KB |
Tour is not fun |
60 |
Halted |
0 ms |
0 KB |
- |