Submission #1254708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254708		fasterthanyou	Festival (IOI25_festival)	C++20	5 / 100	56 ms	6068 KiB

festival

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

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    using ll = long long;
    const ll BIG = 2000000000LL; // 2e9 threshold described above

    int N = (int)P.size();
    array<vector<pair<int,int>>, 5> byT; // byT[t] holds {P, idx}

    for (int i = 0; i < N; ++i) {
        int t = T[i];
        if (t < 1 || t > 4) continue; // defensive
        byT[t].push_back({P[i], i});
    }
    for (int t = 1; t <= 4; ++t) {
        sort(byT[t].begin(), byT[t].end()); // sort by price ascending
    }

    array<int, 5> ptr{}; // next unused per T
    vector<int> order;
    order.reserve(N);

    auto affordable = [&](int t, ll x) -> bool {
        return ptr[t] < (int)byT[t].size() && (ll)byT[t][ptr[t]].first <= x;
    };

    ll x = (ll)A;

    // Main greedy loop
    while (true) {
        if (x >= BIG) break;

        ll bestVal = -1;
        int bestT = -1;
        int bestIdx = -1;
        int bestPrice = -1;

        for (int t = 1; t <= 4; ++t) {
            if (!affordable(t, x)) continue;
            int price = byT[t][ptr[t]].first;
            int idx   = byT[t][ptr[t]].second;

            // candidate next tokens; safe since x < 2e9 here
            ll val = (ll)t * (x - (ll)price);

            // tie-break: larger val, then larger T, then smaller price, then smaller idx
            if (val > bestVal ||
                (val == bestVal && t > bestT) ||
                (val == bestVal && t == bestT && price < bestPrice) ||
                (val == bestVal && t == bestT && price == bestPrice && idx < bestIdx)) {
                bestVal = val;
                bestT = t;
                bestIdx = idx;
                bestPrice = price;
            }
        }

        if (bestT == -1) {
            // nothing affordable in any group
            return order;
        }

        // take it
        order.push_back(bestIdx);
        ++ptr[bestT];

        ll nextX = bestVal;
        if (nextX >= BIG) {
            x = BIG;
            break;
        } else {
            x = nextX;
        }
    }

    // If we reached BIG, we can finish deterministically:
    if (x >= BIG) {
        // All remaining T>1 coupons are affordable and non-decreasing
        for (int t = 4; t >= 2; --t) {
            for (int k = ptr[t]; k < (int)byT[t].size(); ++k) {
                order.push_back(byT[t][k].second);
            }
            ptr[t] = (int)byT[t].size();
        }
        // Then all T=1 by price ascending
        for (int k = ptr[1]; k < (int)byT[1].size(); ++k) {
            order.push_back(byT[1][k].second);
        }
        ptr[1] = (int)byT[1].size();
        return order;
    }

    // Otherwise (no affordable coupons), we’re done
    return order;
}

• 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