Submission #1255079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255079		fasterthanyou	Festival (IOI25_festival)	C++20	5 / 100	40 ms	6468 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();

    // Buckets by multiplier. Keep (price, index), and sort ascending by price.
    vector<pair<ll,int>> b2, b3, b4, b1;
    b2.reserve(n); b3.reserve(n); b4.reserve(n); b1.reserve(n);

    for (int i = 0; i < n; ++i) {
        if (T[i] <= 1) b1.emplace_back((ll)P[i], i);
        else if (T[i] == 2) b2.emplace_back((ll)P[i], i);
        else if (T[i] == 3) b3.emplace_back((ll)P[i], i);
        else b4.emplace_back((ll)P[i], i); // treat T>=4 as 4
    }

    auto by_price = [](const pair<ll,int>& a, const pair<ll,int>& b){
        if (a.first != b.first) return a.first < b.first;
        return a.second < b.second;
    };
    sort(b1.begin(), b1.end(), by_price);
    sort(b2.begin(), b2.end(), by_price);
    sort(b3.begin(), b3.end(), by_price);
    sort(b4.begin(), b4.end(), by_price);

    // Pointers to the next cheapest in each T>=2 bucket
    size_t i2 = 0, i3 = 0, i4 = 0;

    auto has2 = [&]{ return i2 < b2.size(); };
    auto has3 = [&]{ return i3 < b3.size(); };
    auto has4 = [&]{ return i4 < b4.size(); };
    auto cdiv = [](long long x, int t)->long long { return (x + t - 1) / t; };

    // Build the T>=2 block from the end: maintain R = required start for built suffix.
    long long R = 0;
    vector<int> picked_rev; picked_rev.reserve(n);

    while (true) {
        long long best = (1LL<<62);
        int which = -1; // 2,3,4
        if (has2()) {
            long long cand = b2[i2].first + cdiv(R, 2);
            if (cand < best || (cand == best && which < 2)) best = cand, which = 2;
        }
        if (has3()) {
            long long cand = b3[i3].first + cdiv(R, 3);
            if (cand < best || (cand == best && which < 3)) best = cand, which = 3;
        }
        if (has4()) {
            long long cand = b4[i4].first + cdiv(R, 4);
            if (cand < best || (cand == best && which < 4)) best = cand, which = 4;
        }
        if (which == -1) break;          // no T>=2 left
        if (best > (long long)A) break;  // cannot extend the T>=2 block

        if (which == 2) { picked_rev.push_back(b2[i2].second); ++i2; }
        else if (which == 3) { picked_rev.push_back(b3[i3].second); ++i3; }
        else { picked_rev.push_back(b4[i4].second); ++i4; }
        R = best;
    }

    // Now append as many T=1 as possible (cheapest first) within remaining allowance A - R.
    long long rem = (long long)A - R;
    vector<int> one_tail;
    for (size_t i = 0; i < b1.size(); ++i) {
        if (b1[i].first <= rem) {
            rem -= b1[i].first;
            one_tail.push_back(b1[i].second);
        } else break;
    }

    // Final order: reverse of picked_rev (since we built "last to first"), then the T=1 tail.
    reverse(picked_rev.begin(), picked_rev.end());
    picked_rev.insert(picked_rev.end(), one_tail.begin(), one_tail.end());
    return picked_rev;
}

• 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