| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 892039 | Mihailo | Fun Tour (APIO20_fun) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "fun.h"
#define mp make_pair
using namespace std;
long long c, d[200000], l[4], k[200000], x, p[200000], M, m, ctr;
priority_queue<pair<long long, long long> > q[4];
vector<int> createFunTour(long long n, long long Q) {
c=1;
for(int i=2; i<=n; i++) {
if(attractionsBehind(c, i)>=n/2) c=i;
}
x=1;
for(int i=1; i<=n; i++) {
if(i!=c) d[i]=hoursRequired(c, i);
if(d[i]==1) {l[x]=i;k[i]=x;x++;}
}
for(int i=1; i<=n; i++) {
if(k[i]==0&&i!=c) {
if(hoursRequired(i, l[1])<d[i]) k[i]=1;
else if(hoursRequired(i, l[2])<d[i]) k[i]=2;
else k[i]=3;
}
}
for(int i=1; i<=n; i++) {
q[k[i]].push(mp(d[i], i));
}
x=0;
ctr=1;
while(2*max(max(q[1].size(), q[2].size()), q[3].size())<q[1].size()+q[2].size()+q[3].size()) {
m=0;
for(int i=1; i<=3; i++) {
if(i!=x) {
if(m<q[i].top().first) {
m=q[i].top().first;
M=i;
}
}
}
x=M;
p[ctr]=q[x].top().second;
ctr++;
q[x].pop();
}
for(int i=1; i<=3; i++) {
if(q[i].size()==max(max(q[1].size(), q[2].size()), q[3].size())) M=i;
}
for(int i=1; i<=3; i++) {
if(x!=i&&q[i].size()!=max(max(q[1].size(), q[2].size()), q[3].size())&&q[i].top().first==max(max(q[1].top().first, q[2].top().first), q[3].top().first)) {
p[ctr]=q[i].top().second;
ctr++;
q[i].pop();
x=i;
}
}
if(M!=x) {
p[ctr]=q[M].top().second;
ctr++;
q[M].pop();
x=M;
}
while(2*max(max(q[1].size(), q[2].size()), q[3].size())>0) {
m=0;
if(x==M)
for(int i=1; i<=3; i++) {
if(i!=M) {
if(m<q[i].top().first) {
m=q[i].top().first;
x=i;
}
}
}
else x=M;
p[ctr]=q[x].top().second;
ctr++;
q[x].pop();
}
p[ctr]=c;
vector<int> v;
for(int i=1; i<=ctr; i++) v.push_back(p[i]);
return v;
}