Submission #974044

#	Time	Username	Problem	Language	Result	Execution time	Memory
974044		bachhoangxuan	Fun Tour (APIO20_fun)	C++17	47 / 100	106 ms	15880 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);
        //cout << j << ' ' << i << '\n';
    }
    for(int i=0;i<S;i++){
        sort(G[i].begin(),G[i].end(),[&](int x,int y){
            return D[x]<D[y];
        });
    }
    //cout << X << '\n';
    int T=0;
    vector<int> A,B;
    if(S==2){
        A=G[0];B=G[1];
        if((int)A.size()>(int)B.size()) swap(A,B);
    }
    else{
        int c=-1;
        while(T<N-1){
            int Max=0;
            for(int i=0;i<S;i++) Max=max(Max,(int)G[i].size());
            if(2*Max==N-T-1) break;
            int u=-1;Max=0;
            for(int i=0;i<S;i++){
                if(c==i) continue;
                if(D[G[i].back()]>Max) Max=D[G[i].back()],u=i;
            }
            assert(u!=-1);
            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-1) u=i;
        assert(u!=-1);

        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];
        });
        assert((int)A.size()==(int)B.size());
    }
    while(!A.empty() || !B.empty()){
        if(!B.empty()) P[T++]=B.back(),B.pop_back();
        if(!A.empty()) P[T++]=A.back(),A.pop_back();
    }
    P[T++]=X;
    //for(int i=0;i<N;i++) cout << P[i] << ' ';
    //cout << '\n';
    return P;
}

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