Submission #1106578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106578		salmon	Fun Tour (APIO20_fun)	C++14	0 / 100	2071 ms	336 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) ){
            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;

        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{
                for(int i = 0; i < 3; i++) if(i != prev && !sat[i].empty())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--;
            }
        }

        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: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34