# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
299019 |
2020-09-14T12:16:46 Z |
CaroLinda |
Fun Tour (APIO20_fun) |
C++14 |
|
445 ms |
20996 KB |
#include "fun.h"
#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
#define lp(i,a,b) for(int i = a; i < b ;i++)
#define all(x) x.begin(),x.end()
#define debug printf
#define mk make_pair
#define pii pair<int,int>
#define ss second
#define ff first
const int MAXN = 1e5+10 ;
using namespace std ;
vector<int> createFunTour(int n , int q )
{
int centroid = 0 , lastTaken = -1 ;
vector<int> ans , available(3) ;
vector<int> distCentroid(n,0) ;
vector<int> groups[3] ;
for(int i = 1 ; i < n ; i++ )
if(attractionsBehind(centroid,i) > n/2 ) centroid = i ;
for(int i = 0 ; i < n ; i++ )
if(i != centroid ) distCentroid[i] = hoursRequired( i, centroid ) ;
for(int i = 0 ; i < n ; i++ )
{
if(i == centroid ) continue ;
for(int j = 0 ; j < 3 ; j++ )
if( j == 2 || sz(groups[j]) == 0 || hoursRequired( groups[j][0] , i ) != (distCentroid[i] + distCentroid[ groups[j][0] ]) )
{
groups[j].push_back(i) ;
break ;
}
}
iota(all(available),0) ;
for(int i = 0 ; i < 3 ; i++ )
sort(all(groups[i]) , [&](int i, int j){ return distCentroid[i] < distCentroid[j]; } );
while(true)
{
sort(all(available) , [&](int i, int j) { return sz(groups[i]) > sz(groups[j]); } ) ;
if( sz( groups[ available[0] ] ) >= sz( groups[available[1]] ) + sz( groups[ available[2] ] ))
break ;
sort(all(available) , [&](int i, int j) { return distCentroid[ groups[i].back() ] > distCentroid[ groups[j].back() ] ;} ) ;
lastTaken = ( lastTaken == available[0] ) ? available[1] : available[0] ;
ans.push_back( groups[lastTaken].back() ) ;
groups[ lastTaken ].pop_back() ;
}
groups[ available[1] ].insert( groups[ available[1] ].end() , all( groups[ available[2] ] ) ) ;
sort( all( groups[ available[1] ] ) , [&](int i, int j) { return distCentroid[i] < distCentroid[j]; } );
int l = 0 ;
if( sz(ans) > 1 && distCentroid[ ans.back() ] < distCentroid[ groups[available[1]].back() ] )
l = 1 ;
for(; groups[available[l]].size(); l^=1) {
ans.push_back(groups[available[l]].back());
groups[available[l]].pop_back();
}
ans.push_back(centroid) ;
return ans ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
0 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
0 ms |
256 KB |
Output is correct |
11 |
Correct |
1 ms |
256 KB |
Output is correct |
12 |
Correct |
0 ms |
256 KB |
Output is correct |
13 |
Correct |
1 ms |
256 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
256 KB |
Output is correct |
16 |
Correct |
1 ms |
256 KB |
Output is correct |
17 |
Correct |
1 ms |
256 KB |
Output is correct |
18 |
Correct |
1 ms |
256 KB |
Output is correct |
19 |
Correct |
1 ms |
256 KB |
Output is correct |
20 |
Correct |
1 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
0 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
0 ms |
256 KB |
Output is correct |
11 |
Correct |
1 ms |
256 KB |
Output is correct |
12 |
Correct |
0 ms |
256 KB |
Output is correct |
13 |
Correct |
1 ms |
256 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
256 KB |
Output is correct |
16 |
Correct |
1 ms |
256 KB |
Output is correct |
17 |
Correct |
1 ms |
256 KB |
Output is correct |
18 |
Correct |
1 ms |
256 KB |
Output is correct |
19 |
Correct |
1 ms |
256 KB |
Output is correct |
20 |
Correct |
1 ms |
256 KB |
Output is correct |
21 |
Correct |
0 ms |
256 KB |
Output is correct |
22 |
Correct |
1 ms |
256 KB |
Output is correct |
23 |
Correct |
0 ms |
256 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
384 KB |
Output is correct |
28 |
Correct |
1 ms |
256 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
1 ms |
256 KB |
Output is correct |
31 |
Correct |
1 ms |
384 KB |
Output is correct |
32 |
Correct |
1 ms |
384 KB |
Output is correct |
33 |
Correct |
1 ms |
384 KB |
Output is correct |
34 |
Correct |
1 ms |
384 KB |
Output is correct |
35 |
Correct |
1 ms |
384 KB |
Output is correct |
36 |
Correct |
1 ms |
384 KB |
Output is correct |
37 |
Correct |
1 ms |
384 KB |
Output is correct |
38 |
Correct |
1 ms |
384 KB |
Output is correct |
39 |
Correct |
1 ms |
384 KB |
Output is correct |
40 |
Correct |
1 ms |
384 KB |
Output is correct |
41 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
0 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
256 KB |
Output is correct |
8 |
Correct |
0 ms |
256 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
1 ms |
256 KB |
Output is correct |
11 |
Correct |
0 ms |
256 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
152 ms |
16112 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
3 ms |
512 KB |
Output is correct |
21 |
Correct |
4 ms |
768 KB |
Output is correct |
22 |
Correct |
8 ms |
1280 KB |
Output is correct |
23 |
Correct |
14 ms |
2304 KB |
Output is correct |
24 |
Correct |
19 ms |
3072 KB |
Output is correct |
25 |
Correct |
81 ms |
9360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
256 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
12 ms |
1792 KB |
Output is correct |
15 |
Correct |
166 ms |
16168 KB |
Output is correct |
16 |
Correct |
158 ms |
15960 KB |
Output is correct |
17 |
Correct |
28 ms |
3968 KB |
Output is correct |
18 |
Correct |
71 ms |
7488 KB |
Output is correct |
19 |
Correct |
132 ms |
12764 KB |
Output is correct |
20 |
Correct |
5 ms |
816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
0 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
0 ms |
256 KB |
Output is correct |
11 |
Correct |
1 ms |
256 KB |
Output is correct |
12 |
Correct |
0 ms |
256 KB |
Output is correct |
13 |
Correct |
1 ms |
256 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
256 KB |
Output is correct |
16 |
Correct |
1 ms |
256 KB |
Output is correct |
17 |
Correct |
1 ms |
256 KB |
Output is correct |
18 |
Correct |
1 ms |
256 KB |
Output is correct |
19 |
Correct |
1 ms |
256 KB |
Output is correct |
20 |
Correct |
1 ms |
256 KB |
Output is correct |
21 |
Correct |
0 ms |
256 KB |
Output is correct |
22 |
Correct |
1 ms |
256 KB |
Output is correct |
23 |
Correct |
0 ms |
256 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
384 KB |
Output is correct |
28 |
Correct |
1 ms |
256 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
1 ms |
256 KB |
Output is correct |
31 |
Correct |
1 ms |
384 KB |
Output is correct |
32 |
Correct |
1 ms |
384 KB |
Output is correct |
33 |
Correct |
1 ms |
384 KB |
Output is correct |
34 |
Correct |
1 ms |
384 KB |
Output is correct |
35 |
Correct |
1 ms |
384 KB |
Output is correct |
36 |
Correct |
1 ms |
384 KB |
Output is correct |
37 |
Correct |
1 ms |
384 KB |
Output is correct |
38 |
Correct |
1 ms |
384 KB |
Output is correct |
39 |
Correct |
1 ms |
384 KB |
Output is correct |
40 |
Correct |
1 ms |
384 KB |
Output is correct |
41 |
Correct |
1 ms |
384 KB |
Output is correct |
42 |
Correct |
1 ms |
384 KB |
Output is correct |
43 |
Correct |
1 ms |
384 KB |
Output is correct |
44 |
Correct |
152 ms |
16112 KB |
Output is correct |
45 |
Correct |
2 ms |
384 KB |
Output is correct |
46 |
Correct |
3 ms |
512 KB |
Output is correct |
47 |
Correct |
4 ms |
768 KB |
Output is correct |
48 |
Correct |
8 ms |
1280 KB |
Output is correct |
49 |
Correct |
14 ms |
2304 KB |
Output is correct |
50 |
Correct |
19 ms |
3072 KB |
Output is correct |
51 |
Correct |
81 ms |
9360 KB |
Output is correct |
52 |
Correct |
1 ms |
384 KB |
Output is correct |
53 |
Correct |
12 ms |
1792 KB |
Output is correct |
54 |
Correct |
166 ms |
16168 KB |
Output is correct |
55 |
Correct |
158 ms |
15960 KB |
Output is correct |
56 |
Correct |
28 ms |
3968 KB |
Output is correct |
57 |
Correct |
71 ms |
7488 KB |
Output is correct |
58 |
Correct |
132 ms |
12764 KB |
Output is correct |
59 |
Correct |
5 ms |
816 KB |
Output is correct |
60 |
Correct |
239 ms |
16148 KB |
Output is correct |
61 |
Correct |
275 ms |
18544 KB |
Output is correct |
62 |
Correct |
235 ms |
16308 KB |
Output is correct |
63 |
Correct |
260 ms |
20244 KB |
Output is correct |
64 |
Correct |
261 ms |
20176 KB |
Output is correct |
65 |
Correct |
248 ms |
16280 KB |
Output is correct |
66 |
Correct |
272 ms |
18668 KB |
Output is correct |
67 |
Correct |
261 ms |
20336 KB |
Output is correct |
68 |
Correct |
272 ms |
19440 KB |
Output is correct |
69 |
Correct |
365 ms |
20848 KB |
Output is correct |
70 |
Correct |
240 ms |
16256 KB |
Output is correct |
71 |
Correct |
301 ms |
20112 KB |
Output is correct |
72 |
Correct |
270 ms |
18840 KB |
Output is correct |
73 |
Correct |
270 ms |
19288 KB |
Output is correct |
74 |
Correct |
396 ms |
20996 KB |
Output is correct |
75 |
Correct |
255 ms |
16368 KB |
Output is correct |
76 |
Correct |
270 ms |
20208 KB |
Output is correct |
77 |
Correct |
294 ms |
20204 KB |
Output is correct |
78 |
Correct |
284 ms |
19420 KB |
Output is correct |
79 |
Correct |
445 ms |
20840 KB |
Output is correct |
80 |
Correct |
398 ms |
20992 KB |
Output is correct |
81 |
Correct |
265 ms |
16152 KB |
Output is correct |
82 |
Correct |
242 ms |
16112 KB |
Output is correct |
83 |
Correct |
262 ms |
16344 KB |
Output is correct |
84 |
Correct |
92 ms |
6992 KB |
Output is correct |