제출 #1255068

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255068		fasterthanyou	축제 (IOI25_festival)	C++20	5 / 100	42 ms	7608 KiB

festival

#include <vector>
#include <algorithm>
using namespace std;

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    using ll = long long;
    const int n = (int)P.size();

    // Bucket coupons by multiplier T in {1,2,3,4}, keep (price, index)
    vector<pair<ll,int>> buckets[5];
    for (int i = 0; i < n; ++i) {
        int t = T[i];
        if (t < 1) t = 1;
        if (t > 4) t = 4;
        buckets[t].push_back({(ll)P[i], i});
    }
    // Sort each bucket by price ascending (tie-break by index for determinism)
    for (int t = 1; t <= 4; ++t) {
        sort(buckets[t].begin(), buckets[t].end(),
             [](const pair<ll,int>& a, const pair<ll,int>& b){
                 if (a.first != b.first) return a.first < b.first;
                 return a.second < b.second;
             });
    }

    // Pointers to the "cheapest remaining" in each bucket
    size_t ptr[5] = {0,0,0,0,0};

    auto has = [&](int t)->bool { return ptr[t] < buckets[t].size(); };
    auto ceil_div = [](ll x, int t)->ll { return (x + t - 1) / t; };

    ll R = 0;  // current "required tokens" for the already-built suffix
    vector<int> last_to_first;  // we append items as the LAST element each step

    while (true) {
        ll best_cost = (1LL<<62);
        int best_t = -1;

        // Among T=1..4, consider the cheapest remaining in each bucket
        for (int t = 1; t <= 4; ++t) if (has(t)) {
            ll p = buckets[t][ptr[t]].first;
            ll c = p + ceil_div(R, t);              // cost_t(R) = P + ceil(R / T)
            // tie-break: prefer larger T (helps future division), then smaller index
            if (c < best_cost || (c == best_cost && t > best_t)) {
                best_cost = c;
                best_t = t;
            }
        }

        if (best_t == -1) break;              // nothing left
        if (best_cost > (ll)A) break;         // cannot extend without exceeding A

        // Accept this as the last element of the sequence
        last_to_first.push_back(buckets[best_t][ptr[best_t]].second);
        ++ptr[best_t];
        R = best_cost;                        // new requirement for the enlarged suffix
    }

    // The forward buying order is the reverse of the "last-to-first" list
    reverse(last_to_first.begin(), last_to_first.end());
    return last_to_first;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 27
• Subtask 6: 0 / 16
• Subtask 7: 0 / 18