# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
290916 |
2020-09-04T14:39:22 Z |
beso123 |
Fun Tour (APIO20_fun) |
C++14 |
|
333 ms |
22000 KB |
#include "fun.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
vector<int> get_pas(priority_queue<pii> s1,priority_queue<pii> s2){
vector<int> ans;
int d=1;
if(s2.size()>s1.size())
swap(s2,s1);
while(true){
pii v;
if(d==1){
v=s1.top();
s1.pop();
ans.push_back(v.y);
}
else{
v=s2.top();
s2.pop();
ans.push_back(v.y);
}
d=3-d;
if(s1.size()==0 && s2.size()==0)
break;
}
return ans;
}
vector<int> off(priority_queue<pii> s1,priority_queue<pii> s2,priority_queue<pii> s3,int cur){
vector<int> p,d;
if(cur==0){
while(!s2.empty()){
s1.push(s2.top());
s2.pop();
}
return get_pas(s3,s1);
}
if(cur==1 || cur==2){
pii f,s;
if(cur==1){
f=s2.top();
s=s3.top();
if(f.x>s.x){
p.push_back(f.y);
s2.pop();
}
}
else{
f=s1.top();
s=s3.top();
if(f.x>s.x){
p.push_back(f.y);
s1.pop();
}
}
while(!s2.empty()){
s1.push(s2.top());
s2.pop();
}
d=get_pas(s3,s1);
}
else{
while(!s2.empty()){
s1.push(s2.top());
s2.pop();
}
return get_pas(s1,s3);
}
for(int k=0;k<d.size();k++)
p.push_back(d[k]);
return p;
}
vector<int> createFunTour(int n,int Q1){
if(n==2){
return {0,1};
}
int cnt=0,csize=INT_MAX;
for(int k=1;k<n;k++){
int Size=attractionsBehind(0,k);
if((Size-1)>=(n/2)){
if(Size<csize){
csize=Size;
cnt=k;
}
}
}
vector<int> dist(n,0);
vector<int> P,al;
for(int k=0;k<n;k++){
if(k==cnt)
continue;
al.push_back(k);
dist[k]=hoursRequired(k,cnt);
if(dist[k]==1)
P.push_back(k);
}
priority_queue<pii> s1,s2,s3;
for(int k=0;k<al.size();k++){
int a=al[k];
if(dist[a]==hoursRequired(P[0],a)+1){
al[k]++;
al[k]*=-1;
s1.push({dist[a],a});
}
}
for(int k=0;k<al.size();k++){
if(al[k]<0)
continue;
int a=al[k];
if(dist[a]==hoursRequired(P[1],a)+1){
al[k]++;
al[k]*=-1;
s2.push({dist[a],a});
}
}
if(P.size()!=2){
for(int k=0;k<al.size();k++){
if(al[k]<0)
continue;
int a=al[k];
s3.push({dist[a],a});
}
}
vector<int> ans;
vector<int> p;
if(P.size()==2){
if(s1.top().x<s2.top().x)
swap(s1,s2);
ans=get_pas(s1,s2);
}
else{
int cur=0;
while(true){
int a=s1.size(),b=s2.size(),c=s3.size();
if(a+b==c){
p=off(s1,s2,s3,cur);
break;
}
if(c+b==a){
if(cur==1)
cur=3;
else if(cur==3)
cur=1;
p=off(s3,s2,s1,cur);
break;
}
if(a+c==b){
if(cur==3)
cur=2;
else if(cur==2)
cur=3;
p=off(s1,s3,s2,cur);
break;
}
pii v1=s1.top(),v2=s2.top(),v3=s3.top();
if(cur==1)
v1.x=-10;
if(cur==2)
v2.x=-10;
if(cur==3)
v3.x=-10;
int mn=max(v1.x,max(v2.x,v3.x));
if(mn==v1.x){
ans.push_back(v1.y);
cur=1;
s1.pop();
}
else
if(mn==v2.x){
ans.push_back(v2.y);
cur=2;
s2.pop();
}
else
if(mn==v3.x){
ans.push_back(v3.y);
cur=3;
s3.pop();
}
}
}
for(int k=0;k<p.size();k++)
ans.push_back(p[k]);
ans.push_back(cnt);
return ans;
}
Compilation message
fun.cpp: In function 'std::vector<int> off(std::priority_queue<std::pair<int, int> >, std::priority_queue<std::pair<int, int> >, std::priority_queue<std::pair<int, int> >, int)':
fun.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int k=0;k<d.size();k++)
| ~^~~~~~~~~
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:100:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for(int k=0;k<al.size();k++){
| ~^~~~~~~~~~
fun.cpp:108:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int k=0;k<al.size();k++){
| ~^~~~~~~~~~
fun.cpp:119:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(int k=0;k<al.size();k++){
| ~^~~~~~~~~~
fun.cpp:185:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
185 | for(int k=0;k<p.size();k++)
| ~^~~~~~~~~
# |
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 |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
0 ms |
256 KB |
Output is correct |
7 |
Correct |
0 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 |
0 ms |
256 KB |
Output is correct |
11 |
Correct |
0 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 |
288 KB |
Output is correct |
16 |
Correct |
1 ms |
256 KB |
Output is correct |
17 |
Correct |
0 ms |
256 KB |
Output is correct |
18 |
Correct |
0 ms |
256 KB |
Output is correct |
19 |
Correct |
0 ms |
256 KB |
Output is correct |
20 |
Correct |
0 ms |
256 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 |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
0 ms |
256 KB |
Output is correct |
7 |
Correct |
0 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 |
0 ms |
256 KB |
Output is correct |
11 |
Correct |
0 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 |
288 KB |
Output is correct |
16 |
Correct |
1 ms |
256 KB |
Output is correct |
17 |
Correct |
0 ms |
256 KB |
Output is correct |
18 |
Correct |
0 ms |
256 KB |
Output is correct |
19 |
Correct |
0 ms |
256 KB |
Output is correct |
20 |
Correct |
0 ms |
256 KB |
Output is correct |
21 |
Correct |
0 ms |
256 KB |
Output is correct |
22 |
Correct |
0 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 |
256 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
384 KB |
Output is correct |
28 |
Correct |
0 ms |
256 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
1 ms |
384 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 |
0 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 |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
0 ms |
256 KB |
Output is correct |
7 |
Correct |
0 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 |
0 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 |
256 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 |
150 ms |
15772 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
512 KB |
Output is correct |
21 |
Correct |
4 ms |
768 KB |
Output is correct |
22 |
Correct |
7 ms |
1280 KB |
Output is correct |
23 |
Correct |
15 ms |
2304 KB |
Output is correct |
24 |
Correct |
22 ms |
2944 KB |
Output is correct |
25 |
Correct |
83 ms |
9232 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 |
0 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 |
0 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 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 |
13 ms |
1920 KB |
Output is correct |
15 |
Correct |
157 ms |
16112 KB |
Output is correct |
16 |
Correct |
161 ms |
15604 KB |
Output is correct |
17 |
Correct |
29 ms |
3968 KB |
Output is correct |
18 |
Correct |
69 ms |
7360 KB |
Output is correct |
19 |
Correct |
118 ms |
12488 KB |
Output is correct |
20 |
Correct |
5 ms |
896 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 |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
0 ms |
256 KB |
Output is correct |
7 |
Correct |
0 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 |
0 ms |
256 KB |
Output is correct |
11 |
Correct |
0 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 |
288 KB |
Output is correct |
16 |
Correct |
1 ms |
256 KB |
Output is correct |
17 |
Correct |
0 ms |
256 KB |
Output is correct |
18 |
Correct |
0 ms |
256 KB |
Output is correct |
19 |
Correct |
0 ms |
256 KB |
Output is correct |
20 |
Correct |
0 ms |
256 KB |
Output is correct |
21 |
Correct |
0 ms |
256 KB |
Output is correct |
22 |
Correct |
0 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 |
256 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
384 KB |
Output is correct |
28 |
Correct |
0 ms |
256 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
1 ms |
384 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 |
0 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 |
150 ms |
15772 KB |
Output is correct |
45 |
Correct |
1 ms |
384 KB |
Output is correct |
46 |
Correct |
2 ms |
512 KB |
Output is correct |
47 |
Correct |
4 ms |
768 KB |
Output is correct |
48 |
Correct |
7 ms |
1280 KB |
Output is correct |
49 |
Correct |
15 ms |
2304 KB |
Output is correct |
50 |
Correct |
22 ms |
2944 KB |
Output is correct |
51 |
Correct |
83 ms |
9232 KB |
Output is correct |
52 |
Correct |
1 ms |
384 KB |
Output is correct |
53 |
Correct |
13 ms |
1920 KB |
Output is correct |
54 |
Correct |
157 ms |
16112 KB |
Output is correct |
55 |
Correct |
161 ms |
15604 KB |
Output is correct |
56 |
Correct |
29 ms |
3968 KB |
Output is correct |
57 |
Correct |
69 ms |
7360 KB |
Output is correct |
58 |
Correct |
118 ms |
12488 KB |
Output is correct |
59 |
Correct |
5 ms |
896 KB |
Output is correct |
60 |
Correct |
206 ms |
16512 KB |
Output is correct |
61 |
Correct |
262 ms |
19056 KB |
Output is correct |
62 |
Correct |
219 ms |
17776 KB |
Output is correct |
63 |
Correct |
272 ms |
21616 KB |
Output is correct |
64 |
Correct |
252 ms |
20464 KB |
Output is correct |
65 |
Correct |
238 ms |
17648 KB |
Output is correct |
66 |
Correct |
306 ms |
20080 KB |
Output is correct |
67 |
Correct |
251 ms |
21360 KB |
Output is correct |
68 |
Correct |
276 ms |
20848 KB |
Output is correct |
69 |
Correct |
333 ms |
22000 KB |
Output is correct |
70 |
Correct |
214 ms |
15984 KB |
Output is correct |
71 |
Correct |
259 ms |
19824 KB |
Output is correct |
72 |
Correct |
305 ms |
20336 KB |
Output is correct |
73 |
Incorrect |
205 ms |
20612 KB |
Tour is not fun |
74 |
Halted |
0 ms |
0 KB |
- |