제출 #1281238

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281238		tunademayo	Marathon Race 2 (JOI24_ho_t3)	C++20	0 / 100	0 ms	332 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long L;
    if (!(cin >> N >> L)) return 0;
    vector<long long> X(N);
    for (int i = 0; i < N; ++i) cin >> X[i];
    // compress
    map<long long,int> mp;
    for (auto x : X) mp[x]++;
    vector<long long> pos;
    vector<int> cnts;
    for (auto &p : mp){ pos.push_back(p.first); cnts.push_back(p.second); }
    int M = pos.size();

    auto simulate_with_defer = [&](long long S, long long G, bool goLeftFirst, int defer_idx)-> long long {
        // defer_idx: -1 means no defer; otherwise index in [0..M-1] to defer first time
        // build initial visit order (first sweep to one side then to other)
        vector<int> left_idx, right_idx;
        for (int i = 0; i < M; ++i){
            if (pos[i] <= S) left_idx.push_back(i);
            else right_idx.push_back(i);
        }
        vector<int> visit;
        if (goLeftFirst){
            for (int i = (int)left_idx.size()-1; i >= 0; --i) visit.push_back(left_idx[i]);
            for (int i = 0; i < (int)right_idx.size(); ++i) visit.push_back(right_idx[i]);
        } else {
            for (int i = 0; i < (int)right_idx.size(); ++i) visit.push_back(right_idx[i]);
            for (int i = (int)left_idx.size()-1; i >= 0; --i) visit.push_back(left_idx[i]);
        }
        // We'll simulate step-by-step. When moving from curPos to nextP, we will stop
        // at any not-yet-picked positions that lie between curPos and nextP (inclusive),
        // in the correct order along that direction.

        ll time = 0;
        ll curPos = S;
        int carrying = 0;
        vector<int> picked(M, 0);
        // Note: we do NOT auto-pick at S at time 0 unless S is explicitly visited in `visit`
        // and not deferred.

        auto process_move_to = [&](long long target){
            // Move from curPos to target, but stop at any pos[k] lying strictly between curPos and target
            if (curPos == target) return;
            if (curPos < target){
                // moving right; consider all positions with curPos < pos[i] && pos[i] <= target
                // Gather those indices sorted increasing by position
                vector<int> mids;
                for (int i = 0; i < M; ++i){
                    if (!picked[i] && pos[i] > curPos && pos[i] <= target) mids.push_back(i);
                }
                sort(mids.begin(), mids.end(), [&](int a, int b){ return pos[a] < pos[b]; });
                ll from = curPos;
                for (int idx : mids){
                    ll to = pos[idx];
                    ll dist = to - from;
                    time += dist * ( (ll)carrying + 1 ); // movement cost
                    // when we arrive at pos[idx], decide whether to pick now:
                    // pick if idx != defer_idx OR (idx==defer_idx AND this is not the first pass).
                    // To know if this is "first pass", we mark defer by not picking when first met in visit sequence.
                    // But here, we will pick whenever we reach it unless it is the first encounter and we are at the initial visit pass
                    // How to tell "first encounter"? We'll only mark defer as NOT pick on the first time we encounter idx
                    // anywhere. We need a flag to say whether we've "skipped" it already.
                    // We will use picked[idx]==0 to indicate not picked; we also need a deferredSkipped flag stored externally.
                    // We'll rely on external logic: when we first encountered idx in visit loop we may have intentionally skipped it.
                    // However here in process_move_to we may be passing through indices that were skipped earlier; so we'll pick them now.
                    // Simpler: maintain an external vector<int> should_defer(M) initially only defer_idx==1, and also an external vector<int> skipped_once(M).
                    // But since lambda can't access easily, we'll implement process inline in main simulate loop below.
                    from = to;
                }
                // final segment to target
                ll dist = target - from;
                time += dist * ( (ll)carrying + 1 );
                curPos = target;
            } else {
                // moving left: curPos > target
                vector<int> mids;
                for (int i = 0; i < M; ++i){
                    if (!picked[i] && pos[i] < curPos && pos[i] >= target) mids.push_back(i);
                }
                sort(mids.begin(), mids.end(), [&](int a, int b){ return pos[a] > pos[b]; }); // descending
                ll from = curPos;
                for (int idx : mids){
                    ll to = pos[idx];
                    ll dist = from - to;
                    time += dist * ( (ll)carrying + 1 );
                    from = to;
                }
                ll dist = from - target;
                time += dist * ( (ll)carrying + 1 );
                curPos = target;
            }
        };

        // The above helper was intended to be generic, but we need finer control to pick when passing.
        // For clarity and correctness, we'll implement the main loop explicitly below, handling deferred logic.

        // Reset state and implement explicit simulation:
        time = 0;
        curPos = S;
        carrying = 0;
        fill(picked.begin(), picked.end(), 0);
        vector<int> skipped_once(M, 0); // 1 if we've encountered defer_idx and skipped it already
        // Now iterate through visit list, but between each consecutive stop we also allow picking deferred pos when we pass them.
        auto move_and_handle_between = [&](long long dest){
            if (curPos == dest) return;
            if (curPos < dest){
                // moving right: we'll consider positions in increasing order between (curPos, dest]
                // collect indices in increasing pos
                vector<pair<long long,int>> mids;
                for (int i = 0; i < M; ++i){
                    if (!picked[i] && pos[i] > curPos && pos[i] <= dest) mids.emplace_back(pos[i], i);
                }
                sort(mids.begin(), mids.end());
                ll prev = curPos;
                for (auto &pr : mids){
                    ll p = pr.first; int idx = pr.second;
                    ll d = p - prev;
                    time += d * ( (ll)carrying + 1 );
                    // decide to pick now?
                    if (idx == defer_idx && !skipped_once[idx]){
                        // this is the first encounter and we are supposed to skip on first pass
                        skipped_once[idx] = 1;
                        // do NOT pick now; just pass through (we are at position p)
                        prev = p;
                        curPos = p;
                        continue;
                    } else {
                        // pick now
                        carrying += cnts[idx];
                        time += cnts[idx]; // pick cost
                        picked[idx] = 1;
                        prev = p;
                        curPos = p;
                    }
                }
                // final segment to dest
                ll dlast = dest - prev;
                time += dlast * ( (ll)carrying + 1 );
                curPos = dest;
            } else {
                // moving left: consider positions in decreasing order between [dest, curPos)
                vector<pair<long long,int>> mids;
                for (int i = 0; i < M; ++i){
                    if (!picked[i] && pos[i] < curPos && pos[i] >= dest) mids.emplace_back(pos[i], i);
                }
                sort(mids.begin(), mids.end(), greater<pair<long long,int>>());
                ll prev = curPos;
                for (auto &pr : mids){
                    ll p = pr.first; int idx = pr.second;
                    ll d = prev - p;
                    time += d * ( (ll)carrying + 1 );
                    if (idx == defer_idx && !skipped_once[idx]){
                        skipped_once[idx] = 1;
                        prev = p;
                        curPos = p;
                        continue;
                    } else {
                        carrying += cnts[idx];
                        time += cnts[idx];
                        picked[idx] = 1;
                        prev = p;
                        curPos = p;
                    }
                }
                ll dlast = prev - dest;
                time += dlast * ( (ll)carrying + 1 );
                curPos = dest;
            }
        };

        // Now simulate visiting sequence
        for (int id : visit){
            // if already picked (maybe via passing), skip
            if (picked[id]) continue;
            // move from curPos to pos[id], handling any interim deferred picks
            move_and_handle_between(pos[id]);
            // upon arrival, if this position still unpicked:
            if (!picked[id]){
                if (id == defer_idx && !skipped_once[id]){
                    // skip (mark skipped)
                    skipped_once[id] = 1;
                    // we are at pos[id], but did not pick
                } else {
                    // pick now
                    carrying += cnts[id];
                    time += cnts[id];
                    picked[id] = 1;
                }
            }
        }
        // After visiting planned waypoints, it's possible the deferred index remains unpicked and lies between curPos and G.
        // Move to G, and during that movement we must pick any remaining unpicked positions we cross (including defer_idx).
        move_and_handle_between(G);
        // by construction all positions should be picked
        return time;
    };

    int Q; cin >> Q;
    for (int qi = 0; qi < Q; ++qi){
        long long S, G, Tlim; cin >> S >> G >> Tlim;
        // find up-to-2 indices nearest to G
        vector<pair<long long,int>> dist_idx;
        for (int i = 0; i < M; ++i) dist_idx.emplace_back( llabs(pos[i] - G), i );
        sort(dist_idx.begin(), dist_idx.end());
        vector<int> candidates;
        if (!dist_idx.empty()) {
            candidates.push_back(dist_idx[0].second);
            if ((int)dist_idx.size() >= 2 && dist_idx[1].first == dist_idx[0].first) {
                // if tie in distance, include second; otherwise still include second as "2 closest"
                candidates.push_back(dist_idx[1].second);
            } else if ((int)dist_idx.size() >= 2) {
                candidates.push_back(dist_idx[1].second);
            }
        }
        // ensure unique
        sort(candidates.begin(), candidates.end());
        candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end());
        // options: defer none (-1), or each candidate
        vector<int> defers = {-1};
        for (int c : candidates) defers.push_back(c);

        ll best = LLONG_MAX;
        for (bool leftFirst : {true, false}){
            for (int didx : defers){
                ll t = simulate_with_defer(S, G, leftFirst, didx);
                best = min(best, t);
            }
        }
        if (best <= Tlim) cout << "Yes\n"; else cout << "No\n";
    }
    return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 28
• Subtask 5: 0 / 10
• Subtask 6: 0 / 19
• Subtask 7: 0 / 19