Submission #717656

#	Time	Username	Problem	Language	Result	Execution time	Memory
717656		qwerasdfzxcl	Fun Tour (APIO20_fun)	C++17	100 / 100	278 ms	21896 KiB

fun

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

using namespace std;
typedef long long ll;
int n, cent, D[100100], T[100100];
vector<int> V[4], ans;

int dist(int x, int y){
    --x, --y;
    return hoursRequired(x, y);
}

int query(int x, int y){
    --x, --y;
    return attractionsBehind(x, y);
}

void getCent(){
    cent = 1;
    for (int i=2;i<=n;i++) if (query(cent, i) * 2 > n){
        cent = i;
    }
}

void init(){
    ans.clear();
    for (int i=1;i<=3;i++) V[i].clear();
    fill(T+1, T+n+1, 0);

    vector<int> X;
    for (int i=1;i<=n;i++){
        D[i] = dist(cent, i);
        if (D[i]==1){
            X.push_back(i);
            V[X.size()].push_back(i);
            T[i] = X.size();
        } 
    } 

    for (int i=1;i<=n;i++) if (i!=cent && find(X.begin(), X.end(), i)==X.end()){
        int typ = (int)X.size()-1;

        for (int j=0;j<(int)X.size()-1;j++){
            if (query(i, X[j])*2 > n){
                typ = j;
                break;
            }
        }

        typ++;
        V[typ].push_back(i);
        T[i] = typ;
    }

    for (int i=1;i<=3;i++){
        assert((int)V[i].size() * 2 <= n);
        sort(V[i].begin(), V[i].end(), [&](int x, int y){return D[x] < D[y];});
    } 
    assert((int)V[1].size() + (int)V[2].size() + (int)V[3].size() + 1 == n);
}

bool chkPhase1(){
    for (int i=1;i<=3;i++) assert((int)V[i].size()*2 <= n);

    if (n%2==1) return 1;
    for (int i=1;i<=3;i++) if ((int)V[i].size()*2 == n) return 0;
    return 1;
}

void solve(){
    // printf("cent: %d\n", cent-1);
    // printf("phase 1:\n");

    int prv = -1;
    while(n>0 && chkPhase1()){
        assert(n>1);

        int mx = cent, typ = -1;
        for (int i=1;i<=3;i++) if (i!=prv && !V[i].empty()){
            if (D[mx] < D[V[i].back()]){
                mx = V[i].back();
                typ = i;
            }
        }

        assert(typ!=-1);
        ans.push_back(mx);
        V[typ].pop_back();
        --n;
        prv = typ;

        // printf("%d(%d) ", mx-1, D[mx]);
    }

    // printf("\nphase 2:\n");

    assert(n>1);
    assert(n%2==0);

    vector<int> L, R = {cent};
    for (int i=1;i<=3;i++){
        if ((int)V[i].size()==n/2){
            assert(i!=prv);
            assert(L.empty());
            L = V[i];
        }
        else{
            for (auto &x:V[i]) R.push_back(x);
        }
    } 

    assert(L.size()==R.size());
    sort(R.begin(), R.end(), [&](int x, int y){return D[x] < D[y];});

    if (D[L.back()] < D[R.back()] && T[R.back()]!=prv) swap(L, R);

    while(!L.empty()){
        // printf("%d(%d) %d(%d) ", L.back()-1, D[L.back()], R.back()-1, D[R.back()]);

        ans.push_back(L.back()); L.pop_back();
        ans.push_back(R.back()); R.pop_back();
    }
    // printf("\n");
}

std::vector<int> createFunTour(int N, int Q) {
    n = N;

    getCent();
    init();
    solve();

    for (auto &x:ans) --x;
    return ans;
}

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