# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
741743 |
2023-05-14T18:16:29 Z |
myrcella |
Fun Tour (APIO20_fun) |
C++17 |
|
260 ms |
23500 KB |
//by szh
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
#include "fun.h"
const int maxn = 1e5+10;
int n;
int val[maxn];
int dis[maxn];
vector <int> rt;
vector <pii> node[3];
vector <int> solve(vector<vector <pii> > nodee) {
vector <int> ans;
int cur = 0;
if (SZ(nodee[1])>SZ(nodee[0])) cur = 1;
while (!nodee[cur].empty()) {
ans.pb(nodee[cur].back().se);
nodee[cur].pop_back();
cur ^= 1;
}
return ans;
}
std::vector<int> createFunTour(int N, int Q) {
if (N==2) {
vector <int> tmp = {0,1};
return tmp;
}
int cent = -1;
n = N;
rep(i,0,n) {
val[i] = attractionsBehind(0,i);
if (val[i]*2>=N)
if (cent==-1 or val[i]<val[cent]) cent=i;
}
rep(i,0,n) if (cent!=i) {
dis[i] = hoursRequired(cent,i);
if (dis[i]==1) rt.pb(i);
}
rep(i,0,n) if (cent!=i) {
bool ok = false;
rep(j,0,SZ(rt)-1) if (hoursRequired(rt[j],i)+1==dis[i]) {
ok = true;
node[j].pb({dis[i],i});
break;
}
if (ok==false) node[SZ(rt)-1].pb({dis[i],i});
}
sort(ALL(node[0]));sort(ALL(node[1]));
vector <int> ans;
// debug(cent);
//for (auto it:node[1]) debug(it.se);
if (SZ(rt)==2) {
ans = solve({node[0],node[1]});
}
else {
sort(ALL(node[2]));
bool ok = false;
int lst,lstrt = -1;
rep(i,0,3) {
if (SZ(node[i])>=SZ(node[0])+SZ(node[1])+SZ(node[2]) - SZ(node[i])) {
vector <pii> small;
rep(j,0,3) if (i!=j) while (!node[j].empty()) small.pb(node[j].back()),node[j].pop_back();
sort(ALL(small));
vector <int> hmm = solve({small,node[i]});
for (auto it:hmm) ans.pb(it);
ok = true;
break;
}
}
if (ok==false) while (1) {
int tmp = -1;
if (lstrt!=0 and (tmp==-1 or node[1].back().fi > node[tmp].back().fi)) tmp = 0;
if (lstrt!=1 and (tmp==-1 or node[1].back().fi > node[tmp].back().fi)) tmp = 1;
if (lstrt!=2 and (tmp==-1 or node[2].back().fi > node[tmp].back().fi)) tmp = 2;
ans.pb(node[tmp].back().se);
lst = node[tmp].back().fi;
lstrt = tmp;
node[tmp].pop_back();
ok = false;
rep(i,0,3) {
if (SZ(node[i])==SZ(node[0])+SZ(node[1])+SZ(node[2]) - SZ(node[i])) {
vector <pii> small;
rep(j,0,3) if (i!=j) while (!node[j].empty()) small.pb(node[j].back()),node[j].pop_back();
sort(ALL(small));
if (small.back().fi>lst) {
ans.pb(small.back().se);
small.pop_back();
}
vector <int> hmm = solve({node[i],small});
for (auto it:hmm) ans.pb(it);
ok = true;
break;
}
}
if (ok) break;
}
}
ans.pb(cent);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
260 KB |
Output is correct |
14 |
Correct |
1 ms |
312 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
312 KB |
Output is correct |
20 |
Correct |
1 ms |
308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
260 KB |
Output is correct |
14 |
Correct |
1 ms |
312 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
312 KB |
Output is correct |
20 |
Correct |
1 ms |
308 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
312 KB |
Output is correct |
25 |
Correct |
1 ms |
312 KB |
Output is correct |
26 |
Correct |
1 ms |
308 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
0 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
212 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
1 ms |
308 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
1 ms |
340 KB |
Output is correct |
40 |
Correct |
1 ms |
340 KB |
Output is correct |
41 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
312 KB |
Output is correct |
13 |
Correct |
1 ms |
312 KB |
Output is correct |
14 |
Correct |
1 ms |
308 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
99 ms |
17024 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
2 ms |
560 KB |
Output is correct |
21 |
Correct |
3 ms |
724 KB |
Output is correct |
22 |
Correct |
5 ms |
1364 KB |
Output is correct |
23 |
Correct |
12 ms |
2372 KB |
Output is correct |
24 |
Correct |
13 ms |
3152 KB |
Output is correct |
25 |
Correct |
60 ms |
9824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
260 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
10 ms |
1876 KB |
Output is correct |
15 |
Correct |
116 ms |
16652 KB |
Output is correct |
16 |
Correct |
124 ms |
16408 KB |
Output is correct |
17 |
Correct |
23 ms |
4180 KB |
Output is correct |
18 |
Correct |
52 ms |
7828 KB |
Output is correct |
19 |
Correct |
88 ms |
13136 KB |
Output is correct |
20 |
Correct |
4 ms |
980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
260 KB |
Output is correct |
14 |
Correct |
1 ms |
312 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
312 KB |
Output is correct |
20 |
Correct |
1 ms |
308 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
312 KB |
Output is correct |
25 |
Correct |
1 ms |
312 KB |
Output is correct |
26 |
Correct |
1 ms |
308 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
0 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
212 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
1 ms |
308 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
1 ms |
340 KB |
Output is correct |
40 |
Correct |
1 ms |
340 KB |
Output is correct |
41 |
Correct |
1 ms |
340 KB |
Output is correct |
42 |
Correct |
1 ms |
340 KB |
Output is correct |
43 |
Correct |
1 ms |
340 KB |
Output is correct |
44 |
Correct |
99 ms |
17024 KB |
Output is correct |
45 |
Correct |
1 ms |
340 KB |
Output is correct |
46 |
Correct |
2 ms |
560 KB |
Output is correct |
47 |
Correct |
3 ms |
724 KB |
Output is correct |
48 |
Correct |
5 ms |
1364 KB |
Output is correct |
49 |
Correct |
12 ms |
2372 KB |
Output is correct |
50 |
Correct |
13 ms |
3152 KB |
Output is correct |
51 |
Correct |
60 ms |
9824 KB |
Output is correct |
52 |
Correct |
1 ms |
340 KB |
Output is correct |
53 |
Correct |
10 ms |
1876 KB |
Output is correct |
54 |
Correct |
116 ms |
16652 KB |
Output is correct |
55 |
Correct |
124 ms |
16408 KB |
Output is correct |
56 |
Correct |
23 ms |
4180 KB |
Output is correct |
57 |
Correct |
52 ms |
7828 KB |
Output is correct |
58 |
Correct |
88 ms |
13136 KB |
Output is correct |
59 |
Correct |
4 ms |
980 KB |
Output is correct |
60 |
Correct |
152 ms |
18372 KB |
Output is correct |
61 |
Correct |
184 ms |
20876 KB |
Output is correct |
62 |
Correct |
151 ms |
18504 KB |
Output is correct |
63 |
Correct |
159 ms |
22348 KB |
Output is correct |
64 |
Correct |
160 ms |
22256 KB |
Output is correct |
65 |
Correct |
183 ms |
18868 KB |
Output is correct |
66 |
Correct |
186 ms |
21260 KB |
Output is correct |
67 |
Correct |
174 ms |
22744 KB |
Output is correct |
68 |
Correct |
195 ms |
22264 KB |
Output is correct |
69 |
Correct |
252 ms |
23500 KB |
Output is correct |
70 |
Correct |
150 ms |
17200 KB |
Output is correct |
71 |
Correct |
181 ms |
20932 KB |
Output is correct |
72 |
Correct |
187 ms |
21472 KB |
Output is correct |
73 |
Correct |
215 ms |
21956 KB |
Output is correct |
74 |
Correct |
226 ms |
21904 KB |
Output is correct |
75 |
Correct |
188 ms |
19132 KB |
Output is correct |
76 |
Correct |
158 ms |
22468 KB |
Output is correct |
77 |
Correct |
244 ms |
22816 KB |
Output is correct |
78 |
Correct |
196 ms |
22268 KB |
Output is correct |
79 |
Correct |
228 ms |
22996 KB |
Output is correct |
80 |
Correct |
260 ms |
23312 KB |
Output is correct |
81 |
Correct |
168 ms |
16868 KB |
Output is correct |
82 |
Correct |
166 ms |
17204 KB |
Output is correct |
83 |
Correct |
187 ms |
16936 KB |
Output is correct |
84 |
Correct |
63 ms |
7388 KB |
Output is correct |