제출 #1326233

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326233		eysbutno	Circus (Balkan15_CIRCUS)	C++20	100 / 100	771 ms	15900 KiB

circus

#include <bits/stdc++.h>

using ll = long long;

constexpr int INF = 1e9;

std::map<int, int> best_f, best_r;

void init(int n, int m, int p[]) {
    std::sort(p, p + n);

    // dist[i] = {dist from left, dist from right}
    std::vector<std::array<int, 2>> dist(n, {INF, INF});
    std::priority_queue<std::array<int, 3>> pq;
    for (int i = 0; i < n; i++) {
        // initialize left dist with jump from m
        pq.push({-(m - p[i]), i, 0});
    }

    while (!pq.empty()) {
        auto [t, u, f] = pq.top();
        pq.pop();
        t *= -1;
        if (dist[u][f] <= t) continue;
        dist[u][f] = t;

        // use 'ghost edge'
        if (f == 0 && u > 0) {
            pq.push({-(t + p[u] - p[u - 1]), u - 1, 0});
        } else if (f == 1 && u + 1 < n) {
            pq.push({-(t + p[u + 1] - p[u]), u + 1, 1});
        }

        // jump forward by t
        int nxt = std::lower_bound(p, p + n, p[u] + t) - p;
        if (nxt < n) {
            pq.push({-(p[nxt] - p[u]), nxt, 1});
        }

        // jump backwards by t
        nxt = std::upper_bound(p, p + n, p[u] - t) - p - 1;
        if (nxt >= 0) {
            pq.push({-(p[u] - p[nxt]), nxt, 0});
        }
    }

    for (int i = 0; i < n; i++) {
        dist[i][0] = std::min(dist[i][0], dist[i][1]);
    }

    std::vector<int> ord(n);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(), [&](int x, int y) -> bool {
        return p[x] - dist[x][0] > p[y] - dist[y][0];
    });

    int best = INF;
    for (int i : ord) {
        best = std::min(best, p[i]);
        best_f[p[i] - dist[i][0]] = best;
    }

    best = -INF;
    std::sort(ord.begin(), ord.end(), [&](int x, int y) -> bool {
        return p[x] + dist[x][0] < p[y] + dist[y][0];
    });

    for (int i : ord) {
        best = std::max(best, p[i]);
        best_r[p[i] + dist[i][0]] = best;
    }

    best_f[m] = m;
}

int minLength(int d) {
    int best = INF;

    auto it = best_f.lower_bound(d);
    if (it != best_f.end()) {
        best = std::min(best, (it->second) - d);
    }

    it = best_r.upper_bound(d);
    if (it != best_r.begin()) {
        --it;
        best = std::min(best, d - (it->second));
    }

    return best;
}

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

grader.cpp: In function 'int main()':
grader.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%d%d", &N, &M);
      |         ~~~~~^~~~~~~~~~~~~~~~
grader.cpp:18:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |                 scanf("%d", &P[i]);
      |                 ~~~~~^~~~~~~~~~~~~
grader.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf("%d", &Q);
      |         ~~~~~^~~~~~~~~~
grader.cpp:23:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |                 scanf("%d", &d);
      |                 ~~~~~^~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 23 / 23
• Subtask 4: 9 / 9
• Subtask 5: 31 / 31
• Subtask 6: 9 / 9