Submission #925818

#	Time	Username	Problem	Language	Result	Execution time	Memory
925818		adhityamv	Fun Tour (APIO20_fun)	C++17	100 / 100	176 ms	21448 KiB

fun

#include <bits/stdc++.h>
#include <fun.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
int n;
vector<int> dist;
int get_centroid(){
    int ind=0,val=n;
    for(int i=1;i<n;i++){
        int num=attractionsBehind(0,i);
        if(num>=(n+1)/2){
            if(ind==-1 || val>num){
                ind=i;
                val=num;
            }
        }
    }
    return ind;
}
vector<int> deg2(int c,int x,int y){
    vector<pii> part1;
    vector<pii> part2;
    for(int i=0;i<n;i++){
        if(i==c) continue;
        if(attractionsBehind(i,x)>n/2){
            part1.push_back(mp(dist[i],i));
        } else part2.push_back(mp(dist[i],i));
    }
    if(part1.size()<=part2.size()) part1.push_back(mp(0,c));
    else part2.push_back(mp(0,c));
    sort(part1.begin(),part1.end());
    sort(part2.begin(),part2.end());
    int ind1=part1.size()-1;
    int ind2=part2.size()-1;
    vector<int> ans;
    for(int i=0;i<n;i++){
        if(i%2==0){
            ans.push_back(part1[ind1].se);
            ind1--;
        } else{
            ans.push_back(part2[ind2].se);
            ind2--;
        }
    }
    return ans;
}
vector<int> deg3(int c,int x,int y,int z){
    vector<int> ans;
    vector<pii> part[3];
    for(int i=0;i<n;i++){
        if(i==c) continue;
        if(attractionsBehind(i,x)>n/2){
            part[0].push_back(mp(dist[i],i));
        } else if(attractionsBehind(i,y)>n/2){
            part[1].push_back(mp(dist[i],i));
        } else part[2].push_back(mp(dist[i],i));
    }
    int siz[3];
    for(int i=0;i<3;i++) siz[i]=part[i].size();
    int mnind=0;
    for(int i=1;i<3;i++) if(siz[i]<siz[mnind]) mnind=i;
    part[mnind].push_back(mp(0,c));
    siz[mnind]++;
    for(int i=0;i<3;i++) sort(part[i].begin(),part[i].end());
    int prev=-1;
    while(siz[0]!=siz[1]+siz[2] && siz[1]!=siz[2]+siz[0] && siz[2]!=siz[0]+siz[1]){
        int mx=0;
        int ind;
        for(int i=0;i<3;i++){
            if(i==prev) continue;
            if(part[i][siz[i]-1].fi>mx){
                mx=part[i][siz[i]-1].fi;
                ind=i;
            }
        }
        ans.push_back(part[ind][siz[ind]-1].se);
        siz[ind]--;
        prev=ind;
    }
    for(int i=0;i<3;i++){
        if(2*siz[i]==siz[0]+siz[1]+siz[2]){
            vector<pii> u,v;
            for(int j=0;j<siz[i];j++) u.push_back(part[i][j]);
            for(int k=0;k<3;k++){
                if(k==i) continue;
                for(int j=0;j<siz[k];j++) v.push_back(part[k][j]);
            }
            sort(u.begin(),u.end());
            sort(v.begin(),v.end());
            bool swu=true;
            if(prev==i || prev==-1) swu=false;
            else{
                for(int j=0;j<3;j++){
                    if(j==prev) continue;
                    if(j==i) continue;
                    if(part[j][siz[j]-1].fi>part[prev][siz[prev]].fi) swu=false;
                }
            }
            for(int j=siz[i]-1;j>=0;j--){
                if(!swu){
                    ans.push_back(v[j].se);
                    ans.push_back(u[j].se);
                } else{
                    ans.push_back(u[j].se);
                    ans.push_back(v[j].se);
                }
            }
            return ans;
        }
    }
}
vector<int> createFunTour(int nn, int q){
    n=nn;
    int c=get_centroid();
    for(int i=0;i<n;i++){
        if(i==c) dist.push_back(0);
        else dist.push_back(hoursRequired(c,i));
    }
    int cnt=0;
    vector<int> roots;
    for(int i=0;i<n;i++) if(dist[i]==1){
        cnt++;
        roots.push_back(i);
    }
    if(cnt==1) return {0,1};
    if(cnt==2) return deg2(c,roots[0],roots[1]);
    else return deg3(c,roots[0],roots[1],roots[2]);
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> deg3(int, int, int, int)':
fun.cpp:115:1: warning: control reaches end of non-void function [-Wreturn-type]
  115 | }
      | ^
fun.cpp:81:17: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |         siz[ind]--;
      |         ~~~~~~~~^~

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