Submission #348649

#	Time	Username	Problem	Language	Result	Execution time	Memory
348649		denkendoemeer	Fun Tour (APIO20_fun)	C++14	100 / 100	340 ms	21220 KiB

fun

#include<bits/stdc++.h>
#include "fun.h"
using namespace std;
vector<int>ans,av(3),dist,grup[3];
int cmp(int a,int b)
{
    return dist[a]<dist[b];
}
int cmp2(int a,int b)
{
    return grup[a].size()>grup[b].size();
}
int cmp3(int a,int b)
{
    return dist[grup[a].back()]>dist[grup[b].back()];
}
vector<int>createFunTour(int n,int q)
{
    dist.resize(n);
    int cent=0,last=-1,i,j;
    for(i=1;i<n;i++)
        if (attractionsBehind(cent,i)>n/2)
            cent=i;
    for(i=0;i<n;i++)
        if (i!=cent)
            dist[i]=hoursRequired(i,cent);
    for(i=0;i<n;i++)
        if (i!=cent){
            for(j=0;j<3;j++)
                if (j==2 || grup[j].size()==0 || hoursRequired(grup[j][0],i)!=(dist[i]+dist[grup[j][0]])){
                    grup[j].push_back(i);
                    break;
                }
        }
    av[0]=0;
    av[1]=1;
    av[2]=2;
    for(i=0;i<3;i++)
        sort(grup[i].begin(),grup[i].end(),cmp);
    while(1){
        sort(av.begin(),av.end(),cmp2);
        if (grup[av[0]].size()>=grup[av[1]].size()+grup[av[2]].size())
            break;
        sort(av.begin(),av.end(),cmp3);
        if (last==av[0])
            last=av[1];
        else
            last=av[0];
        ans.push_back(grup[last].back());
        grup[last].pop_back();
    }
    grup[av[1]].insert(grup[av[1]].end(),grup[av[2]].begin(),grup[av[2]].end());
    sort(grup[av[1]].begin(),grup[av[1]].end(),cmp);
    int aux=0;
    if (ans.size()>1 && dist[ans.back()]<dist[grup[av[1]].back()])
        aux=1;
    while(grup[av[aux]].size()){
        ans.push_back(grup[av[aux]].back());
        grup[av[aux]].pop_back();
        aux=aux^1;
    }
    ans.push_back(cent);
    return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 34 / 34