Submission #736492

#	Time	Username	Problem	Language	Result	Execution time	Memory
736492		GusterGoose27	Fun Tour (APIO20_fun)	C++17	100 / 100	244 ms	21756 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];
int assign[MAXN];
bool used[MAXN];
vector<int> ans;
int p;
pii curv;
 
int get_mx() {
    int bst = 0;
    for (int i = 1; i < 3; i++) {
        if (bucket[i].size() > bucket[bst].size()) bst = i;
    }
    return bst;
}
 
void add(int i) {
    if (i == -1) {
        cout << "-1 query\n";
        assert(false);
    }
    assert(i != p);
    p = i;
    ans.push_back(bucket[i].top().second);
    assert(assign[bucket[i].top().second] == i);
    curv = bucket[i].top();
    bucket[i].pop();
}
 
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]));
        assign[adj[i]] = i;
        used[adj[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));
                assign[j] = i;
                used[j] = 1;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            bucket[2].push(pii(cent_dist[i], i));
            assign[i] = 2;
        }
    }
    p = -1;
    curv = pii(n, 0);
    for (int i = 0; i < n-1; i++) {
        int mx = get_mx();
        if (mx != p && 2*bucket[mx].size() >= n-1-i) { // if we are not at the mx we need to get ther
            int v = -1;
            for (int j = 0; j < 3; j++) {
                if (j == p) continue;
                if (!bucket[j].empty() && (v == -1 || bucket[j].top() > bucket[v].top())) v = j;
            }
            if (v == mx || curv > bucket[v].top()) add(mx);
            else {
                assert(2*bucket[mx].size() == n-1-i);
                add(v);
            }
        }
        else {
            int v = -1;
            for (int j = 0; j < 3; j++) {
                if (j == p) continue;
                if (!bucket[j].empty() && (v == -1 || bucket[j].top() > bucket[v].top())) v = j;
            }
            add(v);
        }
    }
    ans.push_back(cent);
    assign[cent] = -1;
    p = n;
    for (int i = 0; i < n-1; i++) {
        // assert(cent_dist[ans[i]]+cent_dist[ans[i+1]] <= p);
        p = cent_dist[ans[i]]+cent_dist[ans[i+1]];
        assert(assign[ans[i]] != assign[ans[i+1]]);
    }
    return ans;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:89:44: 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]
   89 |         if (mx != p && 2*bucket[mx].size() >= n-1-i) { // if we are not at the mx we need to get ther
      |                        ~~~~~~~~~~~~~~~~~~~~^~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from fun.cpp:3:
fun.cpp:97:44: 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]
   97 |                 assert(2*bucket[mx].size() == n-1-i);
      |                        ~~~~~~~~~~~~~~~~~~~~^~~~~~~~

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