Submission #430073

#	Time	Username	Problem	Language	Result	Execution time	Memory
430073		Peti	Fun Tour (APIO20_fun)	C++14	100 / 100	402 ms	22280 KiB

fun

#include <bits/stdc++.h>
#include "fun.h"

using namespace std;

bool check(vector<pair<int, int>> &v1, vector<pair<int, int>> &v2, vector<pair<int, int>> &v3, int d){
    return max(d, (v3.empty() ? 0 : v3.back().first)) >= max((v1.empty() ? 0 : v1.back().first), (v2.empty() ? 0 : v2.back().first));
}

void combine(vector<pair<int, int>> &v1, vector<pair<int, int>> &v2, vector<pair<int, int>> &v3, int &last, int d){
    if(v3.size() == 0) return;
    if(v1.size() + v2.size() <= v3.size() && (last == 3 || check(v1, v2, v3, d))){
        for(auto p : v2)
            v1.push_back(p);
        sort(v1.begin(), v1.end());
        swap(v2, v3);
        v3.clear();
        if(last == 2)
            last = 1;
        else if(last == 3)
            last = 2;
    } else if(v1.size() + v3.size() <= v2.size() && (last == 2 || check(v1, v3, v2, d))){
        for(auto p : v3)
            v1.push_back(p);
        sort(v1.begin(), v1.end());
        v3.clear();
        if(last == 3)
            last = 1;
    } else if(v2.size() + v3.size() <= v1.size() && (last == 1 || check(v2, v3, v1, d))){
        for(auto p : v3)
            v2.push_back(p);
        sort(v2.begin(), v2.end());
        v3.clear();
        if(last == 3)
            last = 2;
    }
}

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

    int c = 0;
    for(int i = 1; i < N; i++){
        int ans = attractionsBehind(c, i);
        if(ans*2 > N)
            c = i;
    }

    //cout<<"centroid: "<<c<<"\n";

    vector<int> tavC(N), inds;
    for(int i = 0; i < N; i++){
        tavC[i] = hoursRequired(c, i);
        if(tavC[i] == 1)
            inds.push_back(i);
    }

    if(inds.size() < 2)
        return {0, 1};

    vector<int> tav1(N), tav2(N);
    for(int i = 0; i < N; i++)
        tav1[i] = hoursRequired(inds[0], i);
    for(int i = 0; i < N; i++)
        tav2[i] = hoursRequired(inds[1], i);

    vector<pair<int, int>> v1, v2, v3;
    for(int i = 0; i < N; i++){
        if(i == c) continue;
        if(tav1[i] < tav2[i] && tav1[i] < tavC[i])
            v1.push_back(make_pair(tavC[i], i));
        else if(tav2[i] < tav1[i] && tav2[i] < tavC[i])
            v2.push_back(make_pair(tavC[i], i));
        else
            v3.push_back(make_pair(tavC[i], i));
    }

    if(v1.size() <= v2.size() && v1.size() <= v3.size())
        v1.push_back(make_pair(0, c));
    else if(v2.size() <= v1.size() && v2.size() <= v3.size())
        v2.push_back(make_pair(0, c));
    else
        v3.push_back(make_pair(0, c));
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    sort(v3.begin(), v3.end());

    /*cout<<"csop1\n";
    for(auto p : v1)
        cout<<p.first<<" "<<p.second<<"\n";

    cout<<"csop2\n";
    for(auto p : v2)
        cout<<p.first<<" "<<p.second<<"\n";

    cout<<"csop3\n";
    for(auto p : v3)
        cout<<p.first<<" "<<p.second<<"\n";*/

    int last = 0, d = (int)1e9;
    combine(v1, v2, v3, last, d);

    if(v3.size() == 0){
        last = 2;
        if(v2.size() > v1.size())
            last = 1;
    } else{
        last = 1;
        if(v2.back().first > v1.back().first)
            last = 2;
        if(v3.back().first > v2.back().first && v3.back().first > v1.back().first)
            last = 3;
        last++;
        if(last == 4)
            last = 1;
    }

    vector<int> ret;
    while(!v1.empty() || !v2.empty() || !v3.empty()){
        if(v3.empty()){
            if(last == 1){
                if(v2.empty()) return ret;
                ret.push_back(v2.back().second);
                last = 2;
                v2.pop_back();
            } else{
                if(v1.empty()) return ret;
                ret.push_back(v1.back().second);
                last = 1;
                v1.pop_back();
            }
        } else{
            if(last == 1){
                if(v2.empty() || v3.empty()) return {};
                if(v2.back().first > v3.back().first){
                    ret.push_back(v2.back().second);
                    last = 2;
                    d = v2.back().first;
                    v2.pop_back();
                } else{
                    ret.push_back(v3.back().second);
                    last = 3;
                    d = v3.back().first;
                    v3.pop_back();
                }
            } else if(last == 2){
                if(v2.empty() || v3.empty()) return {};
                if(v1.back().first > v3.back().first){
                    ret.push_back(v1.back().second);
                    last = 1;
                    d = v1.back().first;
                    v1.pop_back();
                } else{
                    ret.push_back(v3.back().second);
                    last = 3;
                    d = v3.back().first;
                    v3.pop_back();
                }
            } else{
                if(v1.empty() || v2.empty()) return {};
                if(v1.back().first > v2.back().first){
                    ret.push_back(v1.back().second);
                    last = 1;
                    d = v1.back().first;
                    v1.pop_back();
                } else{
                    ret.push_back(v2.back().second);
                    last = 2;
                    d = v2.back().first;
                    v2.pop_back();
                }
            }
            combine(v1, v2, v3, last, d);
        }
    }

    return ret;
}

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