Submission #1254704

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

festival

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

using ll = long long;

struct Coupon {
    int idx;
    ll P;
    int T;
};

static inline ll ceil_div(ll a, ll b) {
    // b > 0
    return (a + b - 1) / b;
}

// Given an order, check feasibility and also return the actually buyable prefix.
static pair<int, vector<int>> simulate_forward(ll A, const vector<Coupon>& order) {
    ll X = A;
    vector<int> taken;
    taken.reserve(order.size());
    for (const auto& c : order) {
        if (X < c.P) break;
        X = (X - c.P) * c.T;
        taken.push_back(c.idx);
    }
    return { (int)taken.size(), move(taken) };
}

// Core heuristic: build an order backwards minimizing the required initial tokens R at each step.
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    const int N = (int)P.size();

    // 1) Buckets by T, min-heap by P within each T.
    //    We store {P, idx}.
    array<priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>>, 5> pq;
    for (int i = 0; i < N; ++i) {
        int t = T[i];
        if (t < 1 || t > 4) continue; // safety
        pq[t].push({(ll)P[i], i});
    }

    // 2) Backward greedy: maintain current suffix requirement R.
    ll R = 0;
    vector<Coupon> built; built.reserve(N);

    auto peek_val = [&](int t)->pair<ll,int> {
        if (pq[t].empty()) return { (ll)4e18, -1 };
        auto [p, idx] = pq[t].top();
        ll val = p + ceil_div(R, (ll)t);
        return { val, idx };
    };

    while (true) {
        // Among T in {1,2,3,4}, choose the class with minimal p + ceil(R/T)
        ll bestVal = (ll)4e18;
        int bestT = -1;
        int bestIdx = -1;
        for (int t = 1; t <= 4; ++t) {
            auto [val, idx] = peek_val(t);
            if (val < bestVal || (val == bestVal && t > bestT)) { // tie-break: larger T first
                bestVal = val;
                bestT = t;
                bestIdx = idx;
            }
        }
        if (bestIdx == -1) break;
        if (bestVal > (ll)A) break;          // cannot extend while keeping requirement <= A

        // Take it into the backward-built suffix
        auto [p, idx] = pq[bestT].top(); pq[bestT].pop();
        built.push_back(Coupon{ idx, p, bestT });
        R = bestVal;                         // new requirement after appending this coupon at the front
    }

    // 3) Reverse built order to play forward.
    reverse(built.begin(), built.end());

    // 4) Simulate forward; by construction this prefix is feasible from A.
    auto [cnt, ans] = simulate_forward((ll)A, built);

    // 5) OPTIONAL cheap tail: after the planned order, we may still afford extra T=1 with small P.
    //    Take remaining T=1 coupons in ascending P as much as possible; they cannot hurt feasibility already achieved.
    //    (We do a light pass without altering previously taken.)
    {
        // Gather remaining T=1 not used.
        vector<pair<ll,int>> t1;
        while (!pq[1].empty()) { t1.push_back(pq[1].top()); pq[1].pop(); }
        sort(t1.begin(), t1.end()); // ascending P

        // Re-simulate to the end of planned prefix to get current X, then append T=1 greedily.
        ll X = A;
        for (int i = 0; i < cnt; ++i) {
            int id = ans[i];
            ll p = P[id], t = T[id];
            X = (X - p) * t; // feasible by construction
        }
        for (auto [p, id] : t1) {
            if (X < p) break;
            X -= p;
            ans.push_back(id);
        }
    }

    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