Submission #1254700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254700		fasterthanyou	Festival (IOI25_festival)	C++20	5 / 100	44 ms	9652 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 int N = (int)P.size();

    // Split into T=1 and multipliers T>=2
    vector<pair<int,int>> t1; // (price, idx)
    struct MItem {
        long long key; // w(T) * P key
        int p, t, idx;
    };
    vector<MItem> mult;

    int maxP = 0;
    ll sumT1 = 0;

    auto weight = [](int t) -> int {
        // Sorting by s = P*T/(T-1). Multiply by 6 to avoid fractions:
        // T=2 -> 12, T=3 -> 9, T=4 -> 8
        if (t == 2) return 12;
        if (t == 3) return 9;
        // t == 4
        return 8;
    };

    for (int i = 0; i < N; ++i) {
        maxP = max(maxP, P[i]);
        if (T[i] == 1) {
            t1.emplace_back(P[i], i);
            sumT1 += (ll)P[i];
        } else {
            int w = weight(T[i]);
            mult.push_back(MItem{ (ll)w * (ll)P[i], P[i], T[i], i });
        }
    }

    // Sort multipliers by key, then by price, then by index for determinism
    sort(mult.begin(), mult.end(), [](const MItem& a, const MItem& b) {
        if (a.key != b.key) return a.key < b.key;
        if (a.p != b.p) return a.p < b.p;
        if (a.t != b.t) return a.t < b.t;
        return a.idx < b.idx;
    });

    // Sort T=1 by ascending price, tie-break by index
    sort(t1.begin(), t1.end(), [](const pair<int,int>& a, const pair<int,int>& b){
        if (a.first != b.first) return a.first < b.first;
        return a.second < b.second;
    });

    // Prefix sums for T=1
    vector<ll> pref1(1, 0);
    pref1.reserve(t1.size() + 1);
    for (auto &e : t1) pref1.push_back(pref1.back() + (ll)e.first);

    // Cap to avoid overflow while preserving correctness:
    // Must be >= max price to not break feasibility checks, and >= sum of T1
    // so we don't undercount purchasable T1.
    ll cap = sumT1 + (ll)maxP + 1;

    // Simulate all feasible prefixes of multipliers
    vector<ll> after; // tokens after buying first k multipliers
    after.reserve(mult.size() + 1);
    ll tokens = (ll)A;
    after.push_back(tokens);

    int F = 0; // number of feasible multipliers in order
    for (int i = 0; i < (int)mult.size(); ++i) {
        tokens = min(tokens, cap);
        if (tokens < mult[i].p) break; // can't afford next multiplier
        ll ntok = (tokens - (ll)mult[i].p) * (ll)mult[i].t;
        if (ntok > cap) ntok = cap;
        tokens = ntok;
        after.push_back(tokens);
        ++F;
    }

    // For each feasible prefix k, buy as many T=1 as possible and track the best
    int best_k = 0, best_r = 0;
    ll best_total = -1;
    for (int k = 0; k <= F; ++k) {
        ll cur = after[k];
        // r = largest with pref1[r] <= cur
        int r = (int)(upper_bound(pref1.begin(), pref1.end(), cur) - pref1.begin()) - 1;
        ll total = (ll)k + (ll)r;
        if (total > best_total) {
            best_total = total;
            best_k = k;
            best_r = r;
        } else if (total == best_total) {
            // Optional tie-breaker: prefer more multipliers
            if (k > best_k) {
                best_k = k;
                best_r = r;
            }
        }
    }

    // Build the actual purchase order: first the chosen multipliers, then chosen T=1
    vector<int> order;
    order.reserve(best_k + best_r);
    for (int i = 0; i < best_k; ++i) order.push_back(mult[i].idx);
    for (int i = 0; i < best_r; ++i) order.push_back(t1[i].second);

    return order;
}

• 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