제출 #1262540

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1262540		imann	Circus (Balkan15_CIRCUS)	C++20	0 / 100	68 ms	4820 KiB

circus

#include <iostream>
#include <array>
#include <queue>
#include <algorithm>
#include <limits>
#include <map>
#include <vector>
#include <set>

const int MAX_N = 1000*100+2;

std::array<int, MAX_N> ropesPos;
std::array<int, MAX_N> rDists, lDists;
std::vector<std::pair<int, int>> rLines, lLines;
std::vector<int> rLinesIdx, lLinesIdx;

void init(int N, int M, int P[]) {
    for (int i = 0; i < N; ++i)
        ropesPos[i] = P[i];
    std::sort(ropesPos.begin(), ropesPos.begin() + N);

    // ropesPos = {0, 3, 6, 6, 6, 6, 8};
    // std::cout << "test = " << std::lower_bound(ropesPos.begin(), ropesPos.begin() + 7, 3) - ropesPos.begin() << std::endl;

    ropesPos[N] = M;
    rDists.fill(std::numeric_limits<int>::max());
    lDists.fill(std::numeric_limits<int>::max());
    using T = std::pair<int, std::pair<int, bool>>; // true: right-side
    std::priority_queue<T, std::vector<T>, std::greater<T>> pq;
    lDists[N] = 0;
    rDists[N] = 0;
    lDists[N - 1] = ropesPos[N] - ropesPos[N - 1];
    pq.push({ropesPos[N] - ropesPos[N - 1], {N - 1, false}});
    while (!pq.empty()) {
        auto [dist, node] = pq.top();
        auto [idx, rightSide] = node;
        pq.pop();
        if ((rightSide && rDists[idx] != dist) || (!rightSide && lDists[idx] != dist)) {
            continue;
        }
        if (ropesPos[idx] - dist >= ropesPos[0]) {
            int pidx = std::upper_bound(ropesPos.begin(), ropesPos.begin() + N + 1, ropesPos[idx] - dist) - ropesPos.begin();
            if (ropesPos[pidx] > ropesPos[idx] - dist) {
                pidx--;
            }
            if (lDists[pidx] > ropesPos[idx] - ropesPos[pidx]) {
                lDists[pidx] = ropesPos[idx] - ropesPos[pidx];
                pq.push({lDists[pidx], {pidx, false}});
            }
        }
        if (ropesPos[idx] + dist < ropesPos[N]) {
            int nidx = std::lower_bound(ropesPos.begin(), ropesPos.begin() + N + 1, ropesPos[idx] + dist) - ropesPos.begin();
            if (ropesPos[nidx] < ropesPos[idx] + dist) {
                nidx++;
            }
            if (rDists[nidx] > ropesPos[nidx] - ropesPos[idx]) {
                rDists[nidx] = ropesPos[nidx] - ropesPos[idx];
                pq.push({rDists[nidx], {nidx, true}});
            }
        }
        if (rightSide) {
            if (idx < N) {
                int nidx = idx + 1;
                if (rDists[nidx] > dist + ropesPos[nidx] - ropesPos[idx]) {
                    rDists[nidx] = dist + ropesPos[nidx] - ropesPos[idx];
                    pq.push({rDists[nidx], {nidx, true}});
                }
            }
        } else {
            if (idx > 0) {
                int pidx = idx - 1;
                if (lDists[pidx] > dist + ropesPos[idx] - ropesPos[pidx]) {
                    lDists[pidx] = dist + ropesPos[idx] - ropesPos[pidx];
                    pq.push({lDists[pidx], {pidx, false}});
                }
            }
        }
    }
    for (int i = 0; i <= N; ++i) {
        int d = std::min(lDists[i], rDists[i]);
        lLines.push_back({ropesPos[i] - d, d});
        rLines.push_back({ropesPos[i] + d, d});
    }
    std::sort(lLines.begin(), lLines.end());
    std::sort(rLines.begin(), rLines.end());
    for (int i = 0; i < rLines.size(); ++i) {
        rLinesIdx.push_back(rLines[i].first);
    }
    for (int i = 0; i < lLines.size(); ++i) {
        lLinesIdx.push_back(lLines[i].first);
    }
    int rVal = rLines[0].second;
    int rPos = rLines[0].first;
    for (int i = 1; i < rLines.size(); ++i) {
        int nVal = rVal + rLines[i].first - rPos;
        if (rLines[i].second > nVal) {
            rLines[i].second = nVal;
        } else {
            rVal = rLines[i].second;
            rPos = rLines[i].first;
        }
    }
    int lVal = lLines[lLines.size() - 1].second;
    int lPos = lLines[lLines.size() - 1].first;
    for (int i = lLines.size() - 2; i >= 0; --i) {
        int nVal = lVal + lPos - lLines[i].first;
        if (lLines[i].second > nVal) {
            lLines[i].second = nVal;
        } else {
            lVal = lLines[i].second;
            lPos = lLines[i].first;
        }
    }
    // for (auto rl : rLines) {
    //     std::cout << rl.first << " " << rl.second << std::endl;
    // }
    // for (auto ll : lLines) {
    //     std::cout << ll.first << " " << ll.second << std::endl;
    // }
}

int minLength(int D) {
    int ans = std::numeric_limits<int>::max();
    auto rIdx = std::lower_bound(rLinesIdx.begin(), rLinesIdx.end(), D) - rLinesIdx.begin();
    if (rLinesIdx[rIdx] > D) {
        rIdx--;
    }
    // std::cout << "rIdx = " << rIdx << std::endl;
    ans = std::min(ans, D - rLines[rIdx].first + rLines[rIdx].second);
    auto lIdx = std::upper_bound(lLinesIdx.begin(), lLinesIdx.end(), D) - lLinesIdx.begin();
    lIdx--;
    if (lLinesIdx[lIdx] < D) {
        lIdx++;
    }
    // std::cout << "lIdx = " << lIdx << std::endl;
    ans = std::min(ans, lLines[lIdx].first - D + lLines[lIdx].second);
    return ans;
}

// int main() {
//     int n, m; std::cin >> n >> m;
//     int p[MAX_N];
//     for (int i = 0; i < n; ++i) {
//         std::cin >> p[i];
//     }
//     init(n, m, p);
//     int q; std::cin >> q;
//     for (int i = 0; i < q; ++i) {
//         int d; std::cin >> d;
//         std::cout << minLength(d) << std::endl;
//     }
// }

컴파일 시 표준 에러 (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: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 23
• Subtask 4: 0 / 9
• Subtask 5: 0 / 31
• Subtask 6: 0 / 9