Submission #1179087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179087		steveonalex	Fun Tour (APIO20_fun)	C++20	31 / 100	60 ms	15548 KiB

fun

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()

ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(abs(a), abs(b));}
ll lcm(ll a, ll b){return abs(a) / gcd(a, b) * abs(b);}

ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ull mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}

template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }

template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }

template <class T>
    void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }

template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

#include "fun.h"


// int hoursRequired(int x, int y){
//     return 0;
// }

// int attractionsBehind(int x, int y){
//     return 0;
// }

vector<int> createFunTour(int n, int q){
    if (n == 1){
        return {0};
    }
    if (n == 2){
        return {0, 1};
    }
    vector<int> ans;

    int root = 0;
    for(int i = 1; i < n; ++i) if (attractionsBehind(root, i) >= (n+1) / 2)
        root = i;

    vector<int> dis(n);
    for(int i = 0; i < n; ++i) if (i != root) dis[i] = hoursRequired(root, i);

    vector<int> direct_child;
    for(int i = 0; i < n; ++i) if (dis[i] == 1) direct_child.push_back(i);

    // cerr << "Centroid: " << root << "\n";
    // printArr(dis, " ", "\n", cerr);

    if (direct_child.size() == 2){
        vector<int> v1, v2;
        for(int i = 0; i < n; ++i) if (dis[i] >= 1){
            if (hoursRequired(i, direct_child[0]) == dis[i]-1) v1.push_back(i);
            else v2.push_back(i);
        }
        if (v1.size() > v2.size()) v2.push_back(root);
        else v1.push_back(root);
        if (v1.size() < v2.size()) swap(v1, v2);

        sort(ALL(v1), [&dis](int x, int y){return dis[x] < dis[y];});
        sort(ALL(v2), [&dis](int x, int y){return dis[x] < dis[y];});

        while(v2.size()){
            ans.push_back(v1.back()); ans.push_back(v2.back());
            v1.pop_back(); v2.pop_back();
        }
        if (v1.size()) ans.push_back(v1.back());
    }
    else{
        array<vector<int>, 3> v;
        vector<int> belong(n);
        for(int i= 0; i < n; ++i) if (dis[i] >= 1){
            for(int j = 0; j <= 2; ++j){
                if (j == 2 || hoursRequired(i, direct_child[j]) == dis[i]-1) {
                    v[j].push_back(i);
                    belong[i] = j + 1;
                    break;
                }
            }
        }

        for(int j = 0; j < 3; ++j) sort(ALL(v[j]), [&dis](int x, int y){return dis[x] < dis[y];});


        int u = -1, ma = -1;
        for(int j = 0; j < 3; ++j) if (maximize(ma, dis[v[j].back()])) u = j;

        while(true){
            if (v[0].size() + v[1].size() + v[2].size() <= max({v[0].size(), v[1].size(), v[2].size()}) * 2) break;
            ans.push_back(v[u].back());
            v[u].pop_back();


            int tmp = -1;
            ma = -1;
            for(int j = 0; j < 3; ++j) if (j != u){
                if (maximize(ma, dis[v[j].back()])) 
                    tmp = j;
            }
            u = tmp;
        }

        vector<int> v1, v2;
        int dihh = v[u].back();
        if (v[u].size() == max({v[0].size(), v[1].size(), v[2].size()})) {
            v1 = v[u];

            for(int j = 0; j < 3; ++j) if (j != u){
                for(int k: v[j]) v2.push_back(k);
            }
        }
        else{
            v1 = v[u];

            vector<vector<int>> vuto;
            for(int j = 0; j < 3; ++j) if (j != u){
                vuto.push_back(v[j]);
            }
            if (vuto[0].size() > vuto[1].size()) swap(vuto[0], vuto[1]);
            for(int i: vuto[0]) v1.push_back(i);
            v2 = vuto[1];            
        }

        if (v1.size() <= v2.size()) v1.push_back(root);
        else v2.push_back(root);

        sort(ALL(v1), [&dis, &dihh](int x, int y){
            if (x == dihh) return false;
            if (y == dihh) return true;
            return dis[x] < dis[y];
        });
        sort(ALL(v2), [&dis](int x, int y){return dis[x] < dis[y];});

        while(v2.size()){
            ans.push_back(v1.back()); ans.push_back(v2.back());
            v1.pop_back(); v2.pop_back();
        }
        if (v1.size()) ans.push_back(v1.back());

        // printArr(belong, " ", "\n", cerr);
        // printArr(ans, " ", "\n", cerr);
        // cerr.flush();
        for(int i = 1; i < n; ++i) if (belong[ans[i]] == belong[ans[i-1]])
            assert(false);
    }

    // printArr(ans, " ", "\n", cerr);


    return ans;
}


// int main(void){
//     ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

//     clock_t start = clock();


//     cerr << "Time elapsed: " << clock() - start << "ms!\n";
//     return 0;
// }

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