Submission #569614

#	Time	Username	Problem	Language	Result	Execution time	Memory
569614		alontanay	Fun Tour (APIO20_fun)	C++14	47 / 100	136 ms	17488 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define lll __int_128t
#define ll long long
#define ld long double
#define pi pair<int,int>
#define pl pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define f first
#define s second
#define vvi vector<vi>
#define vvl vector<vl>

#define setind DEBUG_INDENT = 
#define enl "\n";
#define debug(k) for(int _ = 0; _ < DEBUG_INDENT; _ ++) { cout << "  "; } cout << #k << ": " << k << enl;

const int MOD = 1e9 + 7;
const ll MODL = 1e9 + 7;

using namespace std;
using namespace __gnu_pbds;

typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> pbds;

int DEBUG_INDENT = 0;

std::vector<int> createFunTour(int N, int Q) {
    if(N == 2) {
        return {0,1};
    }
    vector<pi> subs(N);
    subs[0] = {N,0};
    for(int i = 1; i < N; i ++) {
        subs[i] = {attractionsBehind(0,i),i};
    }
    sort(subs.begin(),subs.end());
    int idx =0;
    while(subs[idx].f < (N+1) / 2) {
        idx ++;
    }
    int cen = subs[idx].s;
    vector<int> dis(N);
    vector<int> cs;
    for(int i = 0; i < N; i ++) {
        dis[i] = hoursRequired(cen,i);
        if(dis[i] == 1) {
            cs.push_back(i);
        }
    }
    if(cs.size() == 2) {
        int a = cs[0];
        int b = cs[1];
        vector<pi> as;
        vector<pi> bs;
        for(int i = 0; i < N; i ++) {
            if(i == cen) { continue; }
            if(hoursRequired(b,i) < dis[i]) {
                bs.push_back({dis[i],i});
            } else {
                as.push_back({dis[i],i});
            }
        }
        sort(as.begin(),as.end());
        sort(bs.begin(),bs.end());
        bool CA = as.size() > bs.size();
        vector<int> res;
        int ia, ib;
        if(CA) {
            res = {as[as.size()-1].s};
            ia = as.size()-2;
            ib = bs.size()-1;
        } else {
            res = {bs[bs.size()-1].s};
            ia = as.size()-1;
            ib = bs.size()-2;
        }
        for(int i = 2; i < N; i ++) {
            if(CA) {
                res.push_back(bs[ib--].s);
            } else {
                res.push_back(as[ia--].s);
            }
            CA = !CA;
        }
        res.push_back(cen);
        // for(int r : res) {
        //     cout << r << " ";
        // }
        // cout << endl;
        return res;
    }
    vector<vector<pi>> ps(3);
    for(int i = 0; i < N; i ++) {
        if(i == cen) { continue; }
        if(hoursRequired(cs[0],i) < dis[i]) {
            ps[0].push_back({dis[i],i});
        } else if(hoursRequired(cs[1],i) < dis[i]) {
            ps[1].push_back({dis[i],i});
        } else {
            ps[2].push_back({dis[i],i});
        }
    }
    sort(ps[0].begin(),ps[0].end());
    sort(ps[1].begin(),ps[1].end());
    sort(ps[2].begin(),ps[2].end());
    int cur = -20;
    vector<int> ids(3);
    ids[0] = ps[0].size() - 1;
    ids[1] = ps[1].size() - 1;
    ids[2] = ps[2].size() - 1;
    vector<int> res;
    int c = 0;
    while((ids[0] + ids[1] >= ids[2]) && (ids[0] + ids[2] >= ids[1]) && (ids[2] + ids[1] >= ids[0])) {
        c ++;
        pair<int,pi> nxt = {0,{-1,-1}};
        for(int i = 0; i < 3; i ++) {
          if(i == cur) { continue; }
          pi node = ps[i][ids[i]];
          nxt = max(nxt,{node.f,{node.s,i}});
        }
        res.push_back(nxt.s.f);
        // cout << nxt.s.f << endl;
        ids[nxt.s.s] --;
        cur = nxt.s.s;
    }
    // cout << "done" << endl;
    if(ids[0] + ids[1] < ids[2]) {
        if(cur < 0) { cur = 0; }
        while(c < N - 1) {
            c ++;
            pair<int,pi> nxt = {0,{-1,-1}};
            for(int i = 0; i < 3; i ++) {
                if(i == cur || (i + cur == 1) || ids[i] < 0) { continue; }
                pi node = ps[i][ids[i]];
                nxt = max(nxt,{node.f,{node.s,i}});
            }
            res.push_back(nxt.s.f);
            ids[nxt.s.s] --;
            cur = nxt.s.s;
        }
    } else if(ids[0] + ids[2] < ids[1]) {
        if(cur < 0) { cur = 0; }
        while(c < N - 1) {
            c ++;
            pair<int,pi> nxt = {0,{-1,-1}};
            for(int i = 0; i < 3; i ++) {
                if(i == cur || (i + cur == 2) || ids[i] < 0) { continue; }
                pi node = ps[i][ids[i]];
                nxt = max(nxt,{node.f,{node.s,i}});
            }
            res.push_back(nxt.s.f);
            ids[nxt.s.s] --;
            cur = nxt.s.s;
        }
    } else {
        if(cur < 0) { cur = 2; }
        while(c < N - 1) {
            c ++;
            pair<int,pi> nxt = {0,{-1,-1}};
            for(int i = 0; i < 3; i ++) {
                if(i == cur || (i + cur == 3) || ids[i] < 0) { continue; }
                pi node = ps[i][ids[i]];
                nxt = max(nxt,{node.f,{node.s,i}});
            }
            res.push_back(nxt.s.f);
            ids[nxt.s.s] --;
            cur = nxt.s.s;
        }
    }
    // cout << "C E " << cen << endl;
    res.push_back(cen);
    // for(int r : res) {
    //     cout << r << endl;
    // }
    // cout << "\n";
    return res;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:55:13: warning: unused variable 'a' [-Wunused-variable]
   55 |         int a = cs[0];
      |             ^

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