Submission #974150

#	Time	Username	Problem	Language	Result	Execution time	Memory
974150		bachhoangxuan	Fun Tour (APIO20_fun)	C++17	100 / 100	250 ms	20680 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
/*
int hoursRequired(int X, int Y);

int attractionsBehind(int X, int Y);
*/

std::vector<int> createFunTour(int N, int Q) {
    vector<int> P(N);
    int X=0,Min=N;
    for(int i=0;i<N;i++){
        int sz=attractionsBehind(0,i);
        if(sz>N/2 && sz<Min) X=i,Min=sz;
    }
    vector<int> D(N),cc;
    for(int i=0;i<N;i++){
        D[i]=hoursRequired(X,i);
        if(D[i]==1) cc.push_back(i);
    }
    int S=(int)cc.size();
    vector<vector<int>> G(S);
    for(int i=0;i<N;i++){
        if(i==X) continue;
        int j=0;
        while(j+1<S && hoursRequired(cc[j],i)+D[cc[j]]!=D[i]) j++;
        G[j].push_back(i);
    }
    for(int i=0;i<S;i++){
        sort(G[i].begin(),G[i].end(),[&](int x,int y){
            return D[x]<D[y];
        });
    }
    G.resize(S=3);
    int c=-1,T=0;
    vector<int> p={0,1,2};
    sort(p.begin(),p.end(),[&](int x,int y){return (int)G[x].size()>(int)G[y].size();});
    while((int)G[p[0]].size()<(int)G[p[1]].size()+(int)G[p[2]].size()){
        sort(p.begin(),p.end(),[&](int x,int y){return D[G[x].back()]>D[G[y].back()];});
        int i=(p[0]==c);
        P[T++]=G[p[i]].back();
        G[p[i]].pop_back();c=p[i];
        sort(p.begin(),p.end(),[&](int x,int y){return (int)G[x].size()>(int)G[y].size();});
    }
    G[p[1]].insert(G[p[1]].end(),G[p[2]].begin(),G[p[2]].end());
    sort(G[p[1]].begin(),G[p[1]].end(),[&](int x,int y){return D[x]<D[y];});
    int t=0;
    if(T>1 && D[P[T-1]]<D[G[p[1]].back()]) t^=1;
    while(!G[p[t]].empty()){
        P[T++]=G[p[t]].back();
        G[p[t]].pop_back();t^=1;
    }
    P[T++]=X;
    return P;
}

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