Submission #1316571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316571		lucas110550	Festival (IOI25_festival)	C++20	Compilation error	0 ms	0 KiB

festival

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

// Translate of the given Python function.
// Returns the list of chosen coupon original indices (0-based), in the same order
// as the Python code builds `answer`.
vector<int> max_coupons(long long A, const vector<long long>& P, const vector<int>& T) {
    int n = (int)P.size();

    // ---------- split coupons ----------
    vector<pair<long long,int>> cheap; // (price, original_index) for T==1
    // boosters: (weight_key, price, t, original_index)
    struct Booster {
        long long key;
        long long p;
        int t;
        int idx;
    };
    vector<Booster> boosters;

    // coeff = 12 * T / (T-1) for T in {2,3,4} -> {24,18,16}
    unordered_map<int, long long> coeff;
    coeff[2] = 24;
    coeff[3] = 18;
    coeff[4] = 16;

    long long max_price = 0;
    for (int i = 0; i < n; i++) {
        int ti = T[i];
        long long pi = P[i];
        if (ti == 1) {
            cheap.push_back({pi, i});
        } else {
            long long key = pi * coeff[ti];
            boosters.push_back({key, pi, ti, i});
            max_price = max(max_price, pi);
        }
    }

    // ---------- sort ----------
    sort(cheap.begin(), cheap.end(), [](auto &a, auto &b){
        return a.first < b.first; // cheapest first
    });
    sort(boosters.begin(), boosters.end(), [](const Booster& a, const Booster& b){
        if (a.key != b.key) return a.key < b.key;
        return a.p < b.p; // tie-break by price
    });

    vector<long long> cheap_prices;
    vector<int> cheap_idx;
    cheap_prices.reserve(cheap.size());
    cheap_idx.reserve(cheap.size());
    for (auto &cp : cheap) {
        cheap_prices.push_back(cp.first);
        cheap_idx.push_back(cp.second);
    }

    // prefix sums of cheap prices
    // cheap_psum[k] = sum of first k cheap prices, cheap_psum[0]=0
    vector<long long> cheap_psum;
    cheap_psum.reserve(cheap_prices.size() + 1);
    cheap_psum.push_back(0);
    for (long long p : cheap_prices) {
        cheap_psum.push_back(cheap_psum.back() + p);
    }

    auto bisect_right = [&](const vector<long long>& arr, long long x) -> int {
        // returns first index > x
        return (int)(upper_bound(arr.begin(), arr.end(), x) - arr.begin());
    };

    // ---------- take all non-decreasing boosters ----------
    long long token = A;
    vector<int> prefix_ids; // original indices of taken prefix boosters
    int i = 0;
    int m = (int)boosters.size();

    while (i < m) {
        const auto& b = boosters[i];
        long long p = b.p;
        int t = b.t;
        int idx = b.idx;

        // Python: if token * (t - 1) >= p * t
        // Use __int128 to avoid overflow.
        __int128 L = (__int128)token * (t - 1);
        __int128 R = (__int128)p * t;
        if (L >= R) {
            prefix_ids.push_back(idx);
            // token = (token - p) * t
            token = (token - p) * (long long)t;
            i++;
        } else {
            break;
        }
    }

    // ---------- hard suffix ----------
    vector<Booster> hard;
    for (int k = i; k < m; k++) hard.push_back(boosters[k]);
    int h_len = (int)hard.size();

    const int K = 61; // safe upper bound per original code
    vector<long long> dp(K + 1, -1);
    dp[0] = token;

    // predecessor table: parent[j][c] = 1 iff hard[j] used for dp[c]
    vector<vector<uint8_t>> parent(h_len, vector<uint8_t>(K + 1, 0));

    for (int j = 0; j < h_len; j++) {
        long long p = hard[j].p;
        int t = hard[j].t;

        int max_c = min(j + 1, K);
        for (int c = max_c; c >= 1; c--) {
            long long prev = dp[c - 1];
            if (prev >= p) {
                long long cand = (prev - p) * (long long)t;
                if (cand > dp[c]) {
                    dp[c] = cand;
                    parent[j][c] = 1;
                }
            }
        }
    }

    // ---------- evaluate all possibilities ----------
    int best_total = -1;
    int best_c = 0;
    long long best_token = dp[0];

    for (int c = 0; c <= min(K, h_len); c++) {
        long long cur = dp[c];
        if (cur < 0) continue;

        // cheap_cnt = bisect_right(cheap_psum, cur) - 1
        int cheap_cnt = bisect_right(cheap_psum, cur) - 1;
        int total = i + c + cheap_cnt;
        if (total > best_total) {
            best_total = total;
            best_c = c;
            best_token = cur;
        }
    }

    // ---------- reconstruct the chosen hard subset ----------
    vector<int> chosen_hard; // indices (within hard) chosen by DP
    int need = best_c;
    for (int j = h_len - 1; j >= 0; j--) {
        if (need == 0) break;
        if (parent[j][need]) {
            chosen_hard.push_back(j);
            need--;
        }
    }
    reverse(chosen_hard.begin(), chosen_hard.end()); // keep original order

    // ---------- build the final answer ----------
    vector<int> answer;

    // prefix boosters
    answer.insert(answer.end(), prefix_ids.begin(), prefix_ids.end());

    // hard boosters selected by DP
    // Note: same as python, we just append indices; token already best_token
    token = best_token;
    for (int j : chosen_hard) {
        answer.push_back(hard[j].idx);
    }

    // cheap coupons as many as we can afford now
    int cheap_cnt_final = bisect_right(cheap_psum, token) - 1;
    for (int k = 0; k < cheap_cnt_final; k++) {
        answer.push_back(cheap_idx[k]);
    }

    return answer;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccUFNNRa.o: in function `main':
grader.cpp:(.text.startup+0x22a): undefined reference to `max_coupons(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status