Submission #1106624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106624		salmon	Fun Tour (APIO20_fun)	C++14	47 / 100	109 ms	20300 KiB

fun

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

vector<int> createFunTour(int N, int Q){

    int lst[N + 1];
    int d[N + 1];
    int d1[N + 2][2];
    set<pair<int,int>,greater<pair<int,int>>> sat[3];

    for(int i = 0; i < N; i++){
        lst[i] = attractionsBehind(0,i);
    }

    pair<int,int> ii = {N + 90,-1};
    for(int i = 0; i < N; i++){
        if(lst[i] >= (N+1)/2 ) ii = min(ii,{lst[i],i});
    }

    int it = ii.second;

    for(int i = 0; i < N; i++){
        d[i] = hoursRequired(it,i);
    }

    vector<int> tee;

    for(int i = 0; i < N; i++){
        if(d[i] == 1) tee.push_back(i);
    }

    if(tee.size() == 1){
        return {0,1};
    }
    else{
        for(int i = 0; i < N; i++){
            d1[i][0] = hoursRequired(i,tee[0]);
            d1[i][1] = hoursRequired(i,tee[1]);
        }

        for(int i = 0; i < N; i++){
            if(i == it) continue;
            if(d1[i][0] < d[i]){
                sat[0].insert({d[i],i});
            }
            else if(d1[i][1] < d[i]){
                sat[1].insert({d[i],i});
            }
            else sat[2].insert({d[i],i});
        }

        int prev = -1;

        vector<int> ans = {};

        while(max(max(sat[0].size(),sat[1].size() ), sat[2].size()) < (N/2) ){
            assert (!(sat[0].empty()) && !(sat[1].empty()) && !(sat[2].empty()));
            if(prev == -1){
                pair<int,int> ii = {-10,-1};
                for(int i = 0; i < 3; i++) ii = max(ii, {sat[i].begin() -> first,i});

                prev = ii.second;
                ans.push_back(sat[prev].begin() -> second);
                sat[prev].erase(sat[prev].begin());
                N--;
            }
            else{
                pair<int,int> ii = {-10,-1};
                for(int i = 0; i < 3; i++) if(i != prev) ii = max(ii, {sat[i].begin() -> first,i});

                prev = ii.second;
                ans.push_back(sat[prev].begin() -> second);
                sat[prev].erase(sat[prev].begin());
                N--;
            }
        }

        pair<int,int> ii = {-10,-1};
        for(int i = 0; i < 3; i++) ii = max(ii, {sat[i].size(),i});

        int fat = ii.second;
        bool die = false;

        while(sat[0].size() + sat[1].size() + sat[2].size() > 0){
            if(prev != fat){
                prev = fat;
                ans.push_back(sat[prev].begin() -> second);
                sat[prev].erase(sat[prev].begin());
                N--;
            }
            else{
                ii = {-10,-1};
                for(int i = 0; i < 3; i++) if(i != prev && !sat[i].empty())ii = max(ii, {sat[i].begin() -> first,i});

                if(ii.second == -1){
                    ans.push_back(it);
                    ans.push_back(sat[fat].begin() -> second);
                    break;
                }

                prev = ii.second;
                ans.push_back(sat[prev].begin() -> second);
                sat[prev].erase(sat[prev].begin());
                N--;
            }
        }

        if(!die) ans.push_back(it);

        return ans;
    }
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:57:69: warning: comparison of integer expressions of different signedness: 'const long unsigned int' and 'int' [-Wsign-compare]
   57 |         while(max(max(sat[0].size(),sat[1].size() ), sat[2].size()) < (N/2) ){
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~

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