Submission #974037

#	Time	Username	Problem	Language	Result	Execution time	Memory
974037		bachhoangxuan	Fun Tour (APIO20_fun)	C++17	47 / 100	87 ms	14668 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;

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];
        });
    }
    P[0]=X;
    int T=1,c=-1;
    while(T<N){
        int Max=0;
        for(int i=0;i<S;i++) Max=max(Max,(int)G[i].size());
        if(2*Max==N-T) break;
        else if(2*Max>N-T){
            for(int i=0;i<S;i++) if((int)G[i].size()==Max){
                P[T++]=G[i].back();
                G[i].pop_back();c=i;
                break;
            }
            continue;
        }
        int u=-1;Min=N;
        for(int i=0;i<S;i++){
            if(c==i) continue;
            if(D[G[i].back()]<Min) Min=D[G[i].back()],u=i;
        }
        P[T++]=G[u].back();
        G[u].pop_back();c=u;
    }
    int u=-1;
    for(int i=0;i<S;i++) if(2*(int)G[i].size()==N-T) u=i;
    vector<int> A,B;
    for(int i=0;i<S;i++){
        if(u==i) A=G[i];
        else B.insert(B.end(),G[i].begin(),G[i].end());
    }
    if(c!=u) swap(A,B);
    sort(A.begin(),A.end(),[&](int x,int y){
        return D[x]>D[y];
    });
    sort(B.begin(),B.end(),[&](int x,int y){
        return D[x]>D[y];
    });
    while(!A.empty()){
        P[T++]=B.back();
        P[T++]=A.back();
        B.pop_back();
        A.pop_back();
    }
    reverse(P.begin(),P.end());
    return P;
}

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