Submission #1262578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262578		imann	Circus (Balkan15_CIRCUS)	C++20	100 / 100	450 ms	16792 KiB

circus

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

using ll = long long;

const int MAX_N = 1000*100+2;

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

void init(int N, int M, int P[]) {
    posSize = N;
    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<ll>::max());
    lDists.fill(std::numeric_limits<ll>::max());
    using T = std::pair<ll, std::pair<ll, 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]) {
            ll 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]) {
            ll 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) {
                ll 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) {
                ll pidx = idx - 1;
                if (lDists[pidx] > dist + ropesPos[idx] - ropesPos[pidx]) {
                    lDists[pidx] = dist + ropesPos[idx] - ropesPos[pidx];
                    pq.push({lDists[pidx], {pidx, false}});
                }
            }
        }
    }
    // std::cout << "shortest path = " << std::endl;
    for (int i = 0; i <= N; ++i) {
        ll d = std::min(lDists[i], rDists[i]);
        // std::cout << ropesPos[i] << " " << d << std::endl;
        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());
    ll rVal = rLines[0].second;
    ll rPos = rLines[0].first;
    for (int i = 1; i < rLines.size(); ++i) {
        ll nVal = rVal + rLines[i].first - rPos;
        if (rLines[i].second > nVal) {
            rLines[i].second = nVal;
        } else {
            rVal = rLines[i].second;
            rPos = rLines[i].first;
        }
    }
    ll lVal = lLines[lLines.size() - 1].second;
    ll lPos = lLines[lLines.size() - 1].first;
    for (int i = lLines.size() - 2; i >= 0; --i) {
        ll nVal = lVal + lPos - lLines[i].first;
        if (lLines[i].second > nVal) {
            lLines[i].second = nVal;
        } else {
            lVal = lLines[i].second;
            lPos = lLines[i].first;
        }
    }
    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);
    }
    // std::cout << "right lines = " << std::endl;
    // for (auto rl : rLines) {
    //     std::cout << rl.first << " " << rl.second << std::endl;
    // }
    // std::cout << "left lines = " << std::endl;
    // for (auto ll : lLines) {
    //     std::cout << ll.first << " " << ll.second << std::endl;
    // }
}

int minLength(int D) {
    // ll ans = std::numeric_limits<ll>::max();
    // for (int i = 0; i <= posSize; ++i) {
    //     if (std::abs(ropesPos[i] - D) >= std::min(lDists[i], rDists[i]))
    //         ans = std::min(ans, std::abs(ropesPos[i] - D));
    // }
    // return ans;

    // ll ans = std::numeric_limits<ll>::max();
    // for (int i = 0; i < rLinesIdx.size(); ++i) {
    //     if (D >= rLinesIdx[i]) {
    //         ans = std::min(ans, D - rLinesIdx[i] + rLines[i].second);
    //     }
    // }
    // for (int i = 0; i < lLinesIdx.size(); ++i) {
    //     if (D <= lLinesIdx[i]) {
    //         ans = std::min(ans, lLinesIdx[i] - D + lLines[i].second);
    //     }
    // }
    // return ans;

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

Compilation message (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