Submission #735957

#	Time	Username	Problem	Language	Result	Execution time	Memory
735957		GusterGoose27	Fun Tour (APIO20_fun)	C++17	0 / 100	1 ms	212 KiB

fun

#include "fun.h"

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1e5;
int cent_dist[MAXN];
priority_queue<pii> bucket[3];
map<int, int> bucket_mx[3];
bool used[MAXN];
vector<int> ans;

int get_mx() {
    int bst = 0;
    for (int i = 1; i < 2; i++) {
        if (bucket[i].size() > bucket[bst].size()) bst = i;
    }
    return bst;
}

pii get_val(int i) {
    if (!bucket_mx[i].empty()) {
        return *bucket_mx[i].rbegin();
    }
    return pii(-1, 0);
}

void add(int i) {
    ans.push_back(bucket[i].top().second);
    bucket[i].pop();
    int v = bucket_mx[i].rbegin()->first;
    bucket_mx[i][v]--;
    if (bucket_mx[i][v] == 0) bucket_mx[i].erase(v);
}

vector<int> createFunTour(int n, int q) {
    if (n == 2) {
        vector<int> v(2);
        v[0] = 0; v[1] = 1;
        return v;
    }
    int cent = 0;
    int sz = n;
    for (int i = 1; i < n; i++) {
        int cur = attractionsBehind(0, i);
        if (cur < sz && cur >= (n+1)/2) {
            sz = cur;
            cent = i;
        }
    }
    vector<int> adj;
    for (int i = 0; i < n; i++) {
        if (i == cent) {
            cent_dist[i] = 0;
            continue;
        }
        cent_dist[i] = hoursRequired(i, cent);
        if (cent_dist[i] == 1) adj.push_back(i);
    }
    used[cent] = 1;
    assert(adj.size() >= 2);
    for (int i = 0; i < 2; i++) {
        bucket[i].push(pii(1, adj[i]));
        bucket_mx[i][1]++;
        for (int j = 0; j < n; j++) {
            if (cent_dist[j] < 2) continue;
            int d = hoursRequired(j, adj[i]);
            if (d == cent_dist[j]-1) {
                bucket[i].push(pii(cent_dist[j], j));
                bucket_mx[i][cent_dist[j]]++;
                used[j] = 1;
            }
        }
    }
    for (int i = 0; i < n; i++) if (!used[i]) {
        bucket[2].push(pii(cent_dist[i], i));
        bucket_mx[2][cent_dist[i]]++;
    }
    int p = -1;
    for (int i = 0; i < n-1; i++) {
        int mx = get_mx();
        if (2*bucket[mx].size() == n-i) {
            assert(p != mx);
            add(mx);
            p = mx;
        }
        else {
            int v = -1;
            for (int j = 0; j < 3; j++) {
                if (j == p) continue;
                if (v == -1 || get_val(j) > get_val(v)) v = j;
            }
            add(v);
            p = v;
        }
    }
    ans.push_back(cent);
    return ans;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:85:33: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   85 |         if (2*bucket[mx].size() == n-i) {
      |             ~~~~~~~~~~~~~~~~~~~~^~~~~~

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