Submission #1259336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259336		ducthanh2306	Festival (IOI25_festival)	C++20	5 / 100	57 ms	6840 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 CLAMP = (1LL<<62); // cap to avoid overflow
    int N = (int)P.size();

    // Group coupons by type
    vector<pair<int,int>> by[5];
    for (int i = 0; i < N; ++i) {
        by[T[i]].push_back({P[i], i});
    }

    // Sort each group ascending by price
    for (int t = 1; t <= 4; ++t)
        sort(by[t].begin(), by[t].end());

    // Current tokens
    ll X = A;
    vector<int> ans;

    // Pointers to cheapest not-yet-used coupon of each multiplier type
    size_t p2 = 0, p3 = 0, p4 = 0;

    // Phase 1: Buy multipliers greedily by cheapest affordable
    while (true) {
        int chosenType = 0;
        int chosenIdx = -1;
        int chosenPrice = 0;

        // Among available coupons, choose the cheapest affordable one
        int minPrice = INT_MAX;
        if (p2 < by[2].size() && by[2][p2].first <= X && by[2][p2].first < minPrice) {
            minPrice = by[2][p2].first;
            chosenType = 2; chosenPrice = by[2][p2].first; chosenIdx = by[2][p2].second;
        }
        if (p3 < by[3].size() && by[3][p3].first <= X && by[3][p3].first < minPrice) {
            minPrice = by[3][p3].first;
            chosenType = 3; chosenPrice = by[3][p3].first; chosenIdx = by[3][p3].second;
        }
        if (p4 < by[4].size() && by[4][p4].first <= X && by[4][p4].first < minPrice) {
            minPrice = by[4][p4].first;
            chosenType = 4; chosenPrice = by[4][p4].first; chosenIdx = by[4][p4].second;
        }

        if (chosenType == 0) break; // none affordable

        // Buy it
        ans.push_back(chosenIdx);
        __int128 nxt = (__int128)(X - chosenPrice) * chosenType;
        if (nxt > CLAMP) X = CLAMP;
        else X = (ll)nxt;

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

    // Phase 2: Spend remaining tokens on T=1 cheapest-first
    sort(by[1].begin(), by[1].end()); 
    for (auto &c : by[1]) {
        if (c.first <= X) {
            X -= c.first;
            ans.push_back(c.second);
        } else break;
    }

    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