제출 #735962

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
735962		GusterGoose27	즐거운 행로 (APIO20_fun)	C++17	21 / 100	119 ms	15892 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;
 
int get_mx() {
    int bst = 0;
    for (int i = 1; i < 2; i++) {
        if (bucket[i].size() > bucket[bst].size()) bst = i;
    }
    return bst;
}
 
void add(int i) {
    assert(i != p);
    p = i;
    ans.push_back(bucket[i].top().second);
    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;
        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;
    for (int i = 0; i < n-1; i++) {
        int mx = get_mx();
        if (2*bucket[mx].size() == n-i) {
            add(mx);
        }
        else {
            int v = -1;
            for (int j = 0; j < 3; j++) {
                if (j == p) continue;
                if (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;
}

컴파일 시 표준 에러 (stderr) 메시지

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:78: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]
   78 |         if (2*bucket[mx].size() == n-i) {
      |             ~~~~~~~~~~~~~~~~~~~~^~~~~~

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