Submission #1254705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254705		fasterthanyou	Festival (IOI25_festival)	C++20	0 / 100	75 ms	12972 KiB

festival

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

using ll = long long;
using i128 = __int128_t;

struct Item {
    ll P;
    int idx;
};

static inline long long clamp_inf(i128 x) {
    const long long INF = (long long)9e18;
    if (x > (i128)INF) return INF;
    if (x < 0) return 0;
    return (long long)x;
}

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    const int N = (int)P.size();
    array<vector<Item>, 5> buckets;
    for (int i = 0; i < N; ++i) {
        int t = T[i];
        if (t < 1 || t > 4) continue;
        buckets[t].push_back({(ll)P[i], i});
    }
    for (int t = 1; t <= 4; ++t) {
        sort(buckets[t].begin(), buckets[t].end(),
             [](const Item& a, const Item& b){
                 if (a.P != b.P) return a.P < b.P;
                 return a.idx < b.idx;
             });
    }

    // Ready queues: affordable items for each T, ordered by smallest P first.
    using Node = pair<ll,int>; // (P, idx)
    array<priority_queue<Node, vector<Node>, greater<Node>>, 5> ready;
    array<int, 5> ptr{}; // next not-yet-pushed position in each bucket

    auto push_affordable = [&](long long X) {
        for (int t = 1; t <= 4; ++t) {
            auto &b = buckets[t];
            while (ptr[t] < (int)b.size() && b[ptr[t]].P <= X) {
                ready[t].push({b[ptr[t]].P, b[ptr[t]].idx});
                ++ptr[t];
            }
        }
    };

    long long X = A;
    vector<int> ans; ans.reserve(N);

    push_affordable(X);

    while (true) {
        int pickT = -1;
        for (int t = 4; t >= 1; --t) {
            if (!ready[t].empty()) { pickT = t; break; }
        }
        if (pickT == -1) break;

        auto [p, idx] = ready[pickT].top(); ready[pickT].pop();

        // Update tokens X' = T*(X - P), using 128-bit then clamp.
        i128 nextX = (i128)pickT * ((i128)X - (i128)p);
        X = clamp_inf(nextX);
        ans.push_back(idx);

        // New items may have become affordable.
        push_affordable(X);
    }

    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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