Submission #403450

#	Time	Username	Problem	Language	Result	Execution time	Memory
403450		danielcm585	Fun Tour (APIO20_fun)	C++14	0 / 100	1 ms	296 KiB

fun

#include "fun.h"

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

#define fi first
#define se second

typedef pair<int,int> ii;

const int INF = 1e9;

vector<int> createFunTour(int N, int Q) {
    vector<int> dep(N);
    vector<ii> dis;
    for (int i = 0; i < N; i++) {
        dep[i] = hoursRequired(0,i);
        dis.push_back(ii(dep[i],i));
    }
    int cent = 0;
    vector<int> brch;
    sort(dis.begin(),dis.end());
    for (auto i : dis) {
        if (dep[i.se] == dep[cent]+1) {
            brch.push_back(i.se);
            if (attractionsBehind(0,i.se)*2 >= N) {
                cent = i.se;
                brch.clear();
            }
        }
    }
    // cout << ">> " << cent << '\n';
    int sz[3] = {0,0,0};
    vector<ii> lst[3];
    if (!cent) {
        for (int i = N-1; i >= 1; i--) {
            for (int j : {0,1,2}) {
                if (hoursRequired(brch[j],dis[i].se) == dep[dis[i].se]-1) {
                    lst[j].push_back(dis[i]); sz[j]++;
                    break;
                }
            }
        }
    }
    else {
        for (int i = N-1; i >= 0; i--) {
            if (dis[i].se == cent) continue;
            bool done = 0;
            for (int j : {0,1}) {
                if (hoursRequired(brch[j],dis[i].se) == dep[dis[i].se]-dep[brch[j]]) {
                    lst[j].push_back(dis[i]); sz[j]++;
                    done = 1;
                    break;
                }
            }
            if (done) continue;
            lst[2].push_back(ii(hoursRequired(cent,dis[i].se),dis[i].se));
            sz[2]++;
        }
        sort(lst[2].rbegin(),lst[2].rend());
    }
    int ls;
    vector<ii> res;
    res.push_back(ii(0,cent)); N--;
    if (sz[0]*2 < N && sz[1]*2 < N && sz[2]*2 < N) {
        ls = 0;
        while (sz[(ls+1)%3]*2 < N && sz[(ls+2)%3]*2 < N) {
            int a = (ls+1)%3, b = (ls+2)%3;
            if (!sz[b] || sz[a] && lst[a].back() < lst[b].back()) ls = a;
            else ls = b;
            res.push_back(lst[ls].back());
            lst[ls].pop_back(); sz[ls]--;
            N--;
        }
        int a = (ls+1)%3, b = (ls+2)%3;
        if (sz[b]*2 >= N && sz[a] && lst[a].back().fi < res.back().fi) {
            ls = a;
            res.push_back(lst[ls].back());
            lst[ls].pop_back(); sz[ls]--;
            N--;
        }
        else if (sz[a]*2 >= N && sz[b] && lst[b].back().fi < res.back().fi) {
            ls = b;
            res.push_back(lst[ls].back());
            lst[ls].pop_back(); sz[ls]--;
            N--;
        }
    }
    int best = 0;
    ls = -1;
    for (int i : {0,1,2}) {
        if (sz[i] > sz[best]) best = i;
    }
    while (N) {
        int a = (ls+1)%3, b = (ls+2)%3;
        if (ls != best) ls = best;
        else if (!sz[b] || sz[a] && lst[a].back() < lst[b].back()) ls = a;
        else ls = b;
        res.push_back(lst[ls].back());
        lst[ls].pop_back(); sz[ls]--;
        N--;
    }
    vector<int> ans;
    while (!res.empty()) {
        ans.push_back(res.back().se);
        res.pop_back();
    }
    return ans;
}

/*
7 400000
0 1 
0 5
0 6
1 2
1 4
2 3
*/

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:69:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   69 |             if (!sz[b] || sz[a] && lst[a].back() < lst[b].back()) ls = a;
      |                           ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fun.cpp:97:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   97 |         else if (!sz[b] || sz[a] && lst[a].back() < lst[b].back()) ls = a;
      |                            ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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