Submission #1254707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254707		fasterthanyou	Festival (IOI25_festival)	C++20	12 / 100	1096 ms	18092 KiB

festival

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

using ll = long long;

struct Item {
    ll P;
    int T;
    int id;
};

// min-heap by price within a fixed T (since K is monotone in P when T fixed)
template<class Tpair>
using MinHeap = priority_queue<Tpair, vector<Tpair>, greater<Tpair>>;

static inline bool lessK(ll P1, int T1, ll P2, int T2) {
    // compare P1*T1/(T1-1) < P2*T2/(T2-1) without floating
    // i.e. P1*T1*(T2-1) < P2*T2*(T1-1)
    // T in {2,3,4}, (T-1)>0
    __int128 lhs = (__int128)P1 * T1 * (T2 - 1);
    __int128 rhs = (__int128)P2 * T2 * (T1 - 1);
    if (lhs != rhs) return lhs < rhs;
    // tie-break: prefer larger multiplier to boost future capacity
    return T1 > T2;
}

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    const ll INF = (ll)4e18;  // cap to prevent overflow
    int N = (int)P.size();

    // Split into T==1 and T>1 buckets, each store (P, id)
    vector<pair<ll,int>> ones;
    array<vector<pair<ll,int>>, 5> bucket; // bucket[2], bucket[3], bucket[4]

    for (int i = 0; i < N; ++i) {
        if (T[i] == 1) ones.emplace_back((ll)P[i], i);
        else bucket[T[i]].emplace_back((ll)P[i], i);
    }

    // Sort each by price ascending (we'll push into heaps when price <= X)
    sort(ones.begin(), ones.end());
    for (int t : {2,3,4}) sort(bucket[t].begin(), bucket[t].end());

    // Pointers per bucket to stream-in affordable items
    array<int, 5> ptr{}; // default 0
    // Available heaps: per T, heap of (P, id)
    MinHeap<pair<ll,int>> avail2, avail3, avail4;

    auto push_affordable = [&](ll X) {
        // move items with P <= X into avail heaps
        for (int t : {2,3,4}) {
            auto &vec = bucket[t];
            int &j = ptr[t];
            while (j < (int)vec.size() && vec[j].first <= X) {
                if (t == 2) avail2.push(vec[j]);
                else if (t == 3) avail3.push(vec[j]);
                else avail4.push(vec[j]);
                ++j;
            }
        }
    };

    ll X = A;
    push_affordable(X);

    // Record the dynamic path of T>1 choices so we can later choose best prefix
    struct Step { int id; ll P; int T; ll afterX; };
    vector<Step> path;

    // Greedy loop among T>1: at each step pick the affordable item with minimal K across {2,3,4} heap tops
    while (true) {
        // pick candidate tops (must check affordable at *current* X)
        bool has2 = !avail2.empty() && avail2.top().first <= X;
        bool has3 = !avail3.empty() && avail3.top().first <= X;
        bool has4 = !avail4.empty() && avail4.top().first <= X;

        if (!has2 && !has3 && !has4) break;

        // choose by minimal K; ties prefer larger T
        ll cP = -1; int cT = -1; int cid = -1;
        auto consider = [&](ll p, int t, int id){
            if (cT == -1 || lessK(p,t,cP,cT)) { cP=p; cT=t; cid=id; }
        };
        if (has2) consider(avail2.top().first, 2, avail2.top().second);
        if (has3) consider(avail3.top().first, 3, avail3.top().second);
        if (has4) consider(avail4.top().first, 4, avail4.top().second);

        // pop chosen from its heap
        if (cT == 2) avail2.pop();
        else if (cT == 3) avail3.pop();
        else avail4.pop();

        // buy it
        if (X < cP) break; // shouldn't happen due to has* checks
        ll NX = X - cP;
        // multiply with cap
        if (NX > 0 && cT > 1) {
            __int128 tmp = (__int128)NX * cT;
            NX = (tmp > INF ? INF : (ll)tmp);
        } else {
            NX = NX * cT; // could be 0
        }
        X = NX;
        path.push_back({cid, cP, cT, X});

        // newly affordable items may appear
        push_affordable(X);
    }

    // Pre-compute, for each prefix length r, total count = r + (#ones affordable from X_r)
    // First consider r=0 (no T>1)
    auto count_ones_from = [&](ll x)->int{
        int cnt = 0;
        for (auto &pr : ones) {
            if (x >= pr.first) { x -= pr.first; ++cnt; }
            else break;
        }
        return cnt;
    };

    int best_r = 0;
    ll curX = A;
    int best_total = count_ones_from(curX);

    for (int r = 1; r <= (int)path.size(); ++r) {
        ll xr = path[r-1].afterX;
        int total = r + count_ones_from(xr);
        if (total > best_total) {
            best_total = total;
            best_r = r;
        }
    }

    // Reconstruct answer order: take first best_r steps from path, then eat ones greedily
    vector<int> ans;
    ans.reserve(best_total);
    ll x2 = A;
    for (int i = 0; i < best_r; ++i) {
        auto [id, p, t, afterX] = path[i];
        ans.push_back(id);
        // forward-simulate X to align
        ll NX = x2 - p;
        if (NX > 0 && t > 1) {
            __int128 tmp = (__int128)NX * t;
            NX = (tmp > INF ? INF : (ll)tmp);
        } else {
            NX = NX * t;
        }
        x2 = NX;
    }
    for (auto &pr : ones) {
        if (x2 >= pr.first) {
            x2 -= pr.first;
            ans.push_back(pr.second);
        } else break;
    }
    return ans;
}

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