Submission #1281240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281240		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 positions -> pos[], cnts[]
    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 = (int)pos.size();

    // helper: index of position if exists, else -1
    auto idx_of = [&](long long v)->int{
        auto it = lower_bound(pos.begin(), pos.end(), v);
        if (it != pos.end() && *it == v) return int(it - pos.begin());
        return -1;
    };

    // simulate with choices:
    // goLeftFirst: bool
    // defer_idx: index to skip first time (-1 none)
    // pickAtStart: if true, and S coincides with a pos and it's not deferred, pick immediately before moving
    auto simulate = [&](long long S, long long G, bool goLeftFirst, int defer_idx, bool pickAtStart)-> ll {
        // build visit order: go one side fully then the other (monotone first sweep)
        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]);
        }

        ll time = 0;
        ll cur = S;
        int carrying = 0;
        vector<int> picked(M, 0);
        vector<int> skipped_once(M, 0);

        // Option: pick at start immediately if requested and there is a pos at S and it's not the deferred one
        int s_idx = idx_of(S);
        if (s_idx != -1 && pickAtStart) {
            if (defer_idx != s_idx) {
                picked[s_idx] = 1;
                carrying += cnts[s_idx];
                time += cnts[s_idx];
            } else {
                // if it's deferred and pickAtStart requested, we still skip (first time)
                skipped_once[s_idx] = 1; // mark skipped once already
            }
        }

        // helper to move from cur to dest, stopping at any unpicked positions on the way (and picking unless they are deferred on first encounter)
        auto move_and_handle = [&](ll dest){
            if (cur == dest) return;
            if (cur < dest) {
                // positions strictly between cur and dest inclusive of dest
                // collect indices with pos > cur && pos <= dest and not yet picked
                vector<pair<ll,int>> mids;
                for (int i = 0; i < M; ++i) if (!picked[i] && pos[i] > cur && pos[i] <= dest) mids.emplace_back(pos[i], i);
                sort(mids.begin(), mids.end()); // increasing
                ll prev = cur;
                for (auto &pr : mids) {
                    ll p = pr.first; int id = pr.second;
                    ll d = p - prev;
                    time += d * ( (ll)carrying + 1 );
                    prev = p;
                    cur = p;
                    if (id == defer_idx && !skipped_once[id]) {
                        // skip first time
                        skipped_once[id] = 1;
                        continue;
                    } else {
                        // pick now
                        carrying += cnts[id];
                        time += cnts[id];
                        picked[id] = 1;
                    }
                }
                // final segment to dest
                ll dlast = dest - prev;
                time += dlast * ( (ll)carrying + 1 );
                cur = dest;
            } else {
                // cur > dest: move left
                vector<pair<ll,int>> mids;
                for (int i = 0; i < M; ++i) if (!picked[i] && pos[i] < cur && pos[i] >= dest) mids.emplace_back(pos[i], i);
                sort(mids.begin(), mids.end(), greater<pair<ll,int>>()); // decreasing
                ll prev = cur;
                for (auto &pr : mids) {
                    ll p = pr.first; int id = pr.second;
                    ll d = prev - p;
                    time += d * ( (ll)carrying + 1 );
                    prev = p;
                    cur = p;
                    if (id == defer_idx && !skipped_once[id]) {
                        skipped_once[id] = 1;
                        continue;
                    } else {
                        carrying += cnts[id];
                        time += cnts[id];
                        picked[id] = 1;
                    }
                }
                ll dlast = prev - dest;
                time += dlast * ( (ll)carrying + 1 );
                cur = dest;
            }
        };

        // Walk through planned visit order; note that some positions may have been already auto-picked at start
        for (int id : visit) {
            if (picked[id]) continue;
            move_and_handle(pos[id]);
            // after arriving at pos[id], if still unpicked, decide
            if (!picked[id]) {
                if (id == defer_idx && !skipped_once[id]) {
                    skipped_once[id] = 1; // skip first time
                } else {
                    carrying += cnts[id];
                    time += cnts[id];
                    picked[id] = 1;
                }
            }
        }
        // finally move to G and pick any remaining while on the way
        move_and_handle(G);

        // Sanity: all must be picked
        // (if not, then something wrong; but we just handle remaining by extra moves if needed)
        for (int i = 0; i < M; ++i) {
            if (!picked[i]) {
                // go to it, pick, then go to G
                move_and_handle(pos[i]);
                // pick
                carrying += cnts[i];
                time += cnts[i];
                picked[i] = 1;
                move_and_handle(G);
            }
        }
        return time;
    };

    int Q; cin >> Q;
    for (int qi = 0; qi < Q; ++qi) {
        ll S, G, Tlim; cin >> S >> G >> Tlim;
        // build candidate defer indices: none (-1), nearest-to-G 1 and 2 (if exist), and S-index (if exists)
        vector<pair<ll,int>> byDist;
        for (int i = 0; i < M; ++i) byDist.emplace_back(llabs(pos[i] - G), i);
        sort(byDist.begin(), byDist.end());
        vector<int> candidates;
        candidates.push_back(-1);
        if (!byDist.empty()) candidates.push_back(byDist[0].second);
        if ((int)byDist.size() >= 2 && byDist[1].second != byDist[0].second) candidates.push_back(byDist[1].second);
        int sidx = idx_of(S);
        if (sidx != -1) candidates.push_back(sidx);
        // unique
        sort(candidates.begin(), candidates.end());
        candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end());

        // Also consider pickAtStart true/false (if S has pos)
        vector<bool> startChoices;
        if (sidx == -1) startChoices = {false}; else startChoices = {false, true};

        ll best = LLONG_MAX;
        for (bool leftFirst : {true, false}) {
            for (int defer_idx : candidates) {
                for (bool pickAtStart : startChoices) {
                    // make sure not to conflict: if pickAtStart==true and defer_idx==sidx -> that means picking and deferring same pos; allow it,
                    // but simulate handles skip priority (we set skipped_once for sidx if pickAtStart requested and it's deferred).
                    ll t = simulate(S, G, leftFirst, defer_idx, pickAtStart);
                    if (t < best) 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