Submission #1259330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259330		ducthanh2306	Festival (IOI25_festival)	C++20	5 / 100	56 ms	6840 KiB

festival

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

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    const long long CLAMP = (1LL<<62); // keep X bounded to avoid overflow
    int N = (int)P.size();

    // Group by type; store (price, index) and sort by price asc.
    vector<pair<int,int>> by[5];
    for (int i = 0; i < N; ++i) by[T[i]].push_back({P[i], i});
    for (int t = 1; t <= 4; ++t) sort(by[t].begin(), by[t].end());

    // Current tokens (use long long; compute transitions in __int128 to be safe)
    long long X = A;
    vector<int> ans;

    // Pointers to the next not-yet-bought coupon in each multiplier bucket
    size_t p2 = 0, p3 = 0, p4 = 0;

    auto next_tokens = [](long long X, int price, int t) -> __int128 {
        return (__int128)(X - price) * t;
    };

    // Phase 1: use multipliers greedily
    while (true) {
        int bestT = 0, bestPrice = 0, bestIdx = -1;
        __int128 bestVal = -1;

        if (p2 < by[2].size() && by[2][p2].first <= X) {
            auto val = next_tokens(X, by[2][p2].first, 2);
            if (val > bestVal) { bestVal = val; bestT = 2; bestPrice = by[2][p2].first; bestIdx = by[2][p2].second; }
        }
        if (p3 < by[3].size() && by[3][p3].first <= X) {
            auto val = next_tokens(X, by[3][p3].first, 3);
            if (val > bestVal) { bestVal = val; bestT = 3; bestPrice = by[3][p3].first; bestIdx = by[3][p3].second; }
        }
        if (p4 < by[4].size() && by[4][p4].first <= X) {
            auto val = next_tokens(X, by[4][p4].first, 4);
            if (val > bestVal) { bestVal = val; bestT = 4; bestPrice = by[4][p4].first; bestIdx = by[4][p4].second; }
        }

        if (bestT == 0) break; // no multiplier affordable

        // Buy it
        ans.push_back(bestIdx);
        __int128 nxt = bestVal;
        if (nxt > (__int128)CLAMP) X = CLAMP;            // clamp to avoid overflow on future ops
        else if (nxt < 0) X = -1;                        // (won't happen since price<=X)
        else X = (long long)nxt;

        if (bestT == 2) ++p2;
        else if (bestT == 3) ++p3;
        else ++p4;
    }

    // Phase 2: spend remaining tokens on T=1, cheapest-first
    size_t p1 = 0;
    while (p1 < by[1].size() && by[1][p1].first <= X) {
        X -= by[1][p1].first;
        ans.push_back(by[1][p1].second);
        ++p1;
    }

    return ans;
}

• 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