# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
598263 | ogibogi2004 | 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 "fun.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5;
int st[MAXN];
int dep[MAXN];
vector<int> createFunTour(int N, int Q) {
for(int i=1;i<N;i++)
{
st[i]=attractionsBehind(i,0);
}
st[0]=N;
int centr=0,minst=N;
for(int i=1;i<N;i++)
{
if(st[i]>=N/2)
{
if(st[i]<minst)
{
minst=st[i];
centr=i;
}
}
}
vector<int>dep1;
vector<pair<int,int> >buckets[3];
for(int i=0;i<N;i++)
{
dep[i]=hoursRequired(i,centr);
if(dep[i]==1)dep1.push_back(i);
}
for(int j=0;j<dep1.size();j++)buckets[j].push_back({1,dep1[j]});
for(int i=0;i<N;i++)
{
if(dep[i]<=1)continue;
for(int j=0;j<dep1.size();j++)
{
if(dep[i]==hoursRequired(dep1[j],i)+1)
{
buckets[j].push_back({dep[i],i});
break;
}
}
}
if(dep1.size()==1)
{
vector<int>v;
for(int i=0;i<N;i++)v.push_back(i);
return v;
}
vector<int>ans;
if(dep1.size()==2)
{
sort(buckets[0].rbegin(),buckets[0].rend());
sort(buckets[1].rbegin(),buckets[1].rend());
if(buckets[0].size()<buckets[1].size())swap(buckets[0],buckets[1]);
for(int i=0;i<buckets[1].size();i++)
{
ans.push_back(buckets[0][i].second);
ans.push_back(buckets[1][i].second);
}
if(buckets[0].size()>buckets[1].size())
{
ans.push_back(buckets[0].back().second);
}
ans.push_back(centr);
return ans;
}
else
{
if(buckets[1].size()>buckets[0].size())swap(buckets[0],buckets[1]);
if(buckets[2].size()>buckets[0].size())swap(buckets[0],buckets[2]);
if(buckets[2].size()>buckets[1].size())swap(buckets[1],buckets[2]);
int t=0;
sort(buckets[0].begin(),buckets[0].end());
sort(buckets[1].begin(),buckets[1].end());
sort(buckets[2].begin(),buckets[2].end());
while(buckets[0].size()!=buckets[1].size()+buckets[2].size())
{
ans.push_back(buckets[t].back().second);
buckets[t].pop_back();
t++;t%=3;
}
if(t==2)t=0;
for(auto xd:buckets[2])buckets[1].push_back(xd);
sort(buckets[1].rbegin(),buckets[1].rend());
sort(buckets[0].rbegin(),buckets[0].rend());
if(t==1)swap(buckets[0],buckets[1]);
for(int j=0;j<buckets[0].size();j++)
{
ans.push_back(buckets[0][j].second);
ans.push_back(buckets[1][j].second);
}
ans.push_back(centr);
if(ans.size()!+N)assert(false);
return ans;
}
}