Submission #1030240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030240		vjudge1	Fun Tour (APIO20_fun)	C++17	66 / 100	118 ms	38116 KiB

fun

#include "fun.h"

#include <bits/stdc++.h>
using namespace std;
int N_;
std::vector<int> createFunTour(int N, int Q) {
    if(N==2) return{0,1};
    pair<int,int>centroid{N,0};
    for(int i=1;i<N;i++) {
        int k=attractionsBehind(0,i);
        if(k>=(N+1)/2)
            centroid=min(centroid,{k,i});
    }
    int k=centroid.second;
    vector<int>subtreez;
    vector<pair<int,int>> why[3];
    for(int i=0;i<N;i++){
        if(i==k) continue;
        int C=hoursRequired(k,i);
        if(!subtreez.size()){
            subtreez.push_back(i);
            why[0].push_back({C,i});
        } else if(subtreez.size()==1){
            if(why[0][0].first+C-hoursRequired(why[0][0].second,i))
                why[0].push_back({C,i});
            else subtreez.push_back(i),why[1].push_back({C,i});
        } else {
            if(why[0][0].first+C-hoursRequired(why[0][0].second,i))
                why[0].push_back({C,i});
            else if(why[1][0].first+C-hoursRequired(why[1][0].second,i))
                why[1].push_back({C,i});
            else why[2].push_back({C,i});
        }
    }
    sort(why[0].begin(),why[0].end());
    sort(why[1].begin(),why[1].end());
    sort(why[2].begin(),why[2].end());
    sort(why,why+3,[](vector<pair<int,int>>&a,vector<pair<int,int>>&b){
        if(a.empty()||b.empty()) return !a.empty();
        if(a.size()==(N_+1)/2) return true;
        if(b.size()==(N_+1)/2) return false;
        return a.back().first>b.back().first;
    });
    vector<int>ans{why[0].back().second};
    int prevdep=1e9,curdep=why[0].back().first,cursub=0;
    why[0].pop_back();
    while(ans.size()<N-1){
        vector<int>compatible;
        for(int i=0;i<3;i++)
            if(why[i].size()&&i-cursub&&why[i].back().first<=prevdep)
                compatible.push_back(i);
        if(compatible.size()==1){
            int c=compatible[0];
            prevdep=curdep;cursub=c;
            curdep=why[c].back().first;
            ans.push_back(why[c].back().second);
            why[c].pop_back();
        } else {
            int A=compatible[0];
            int B=compatible[1];
            int tot=why[0].size()+why[1].size()+why[2].size();
            if(why[A].size()<why[B].size())
                swap(A,B);
            if(why[A].size()==why[B].size()){
                if(why[A].back().first<why[B].back().first){
                    prevdep=curdep;cursub=B;
                    curdep=why[B].back().first;
                    ans.push_back(why[B].back().second);
                    why[B].pop_back();
                } else {
                    prevdep=curdep;cursub=A;
                    curdep=why[A].back().first;
                    ans.push_back(why[A].back().second);
                    why[A].pop_back();
                }
            } else if(why[A].size()>=tot/2){
                prevdep=curdep;cursub=A;
                curdep=why[A].back().first;
                ans.push_back(why[A].back().second);
                why[A].pop_back();
            } else if(why[B].size()>=tot/2){
                prevdep=curdep;cursub=B;
                curdep=why[B].back().first;
                ans.push_back(why[B].back().second);
                why[B].pop_back();
            } else if(why[A].back().first<why[B].back().first){
                prevdep=curdep;cursub=B;
                curdep=why[B].back().first;
                ans.push_back(why[B].back().second);
                why[B].pop_back();
            } else {
                prevdep=curdep;cursub=A;
                curdep=why[A].back().first;
                ans.push_back(why[A].back().second);
                why[A].pop_back();
            }
        }
    }
    ans.push_back(k);
    return ans;
}

Compilation message (stderr)

fun.cpp: In lambda function:
fun.cpp:40:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |         if(a.size()==(N_+1)/2) return true;
      |            ~~~~~~~~^~~~~~~~~~
fun.cpp:41:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |         if(b.size()==(N_+1)/2) return false;
      |            ~~~~~~~~^~~~~~~~~~
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:47:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |     while(ans.size()<N-1){
      |           ~~~~~~~~~~^~~~
fun.cpp:76:36: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   76 |             } else if(why[A].size()>=tot/2){
      |                       ~~~~~~~~~~~~~^~~~~~~
fun.cpp:81:36: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |             } else if(why[B].size()>=tot/2){
      |                       ~~~~~~~~~~~~~^~~~~~~

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