Submission #1310339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310339		beluga_cat	Festival (IOI25_festival)	C++20	5 / 100	55 ms	9584 KiB

festival

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

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    int N = P.size();
    vector<int> result;
    long long tokens = A;

    vector<int> used(N, 0);

    // Growth coupons (T >= 2)
    vector<int> growth;
    // Drain coupons (T == 1)
    vector<int> drain;

    for (int i = 0; i < N; i++) {
        if (T[i] >= 2) growth.push_back(i);
        else drain.push_back(i);
    }

    // Sort growth by price ascending, then T descending
    sort(growth.begin(), growth.end(), [&](int a, int b) {
        if (P[a] != P[b]) return P[a] < P[b];
        return T[a] > T[b];
    });

    // Phase 1: growth
    bool progress = true;
    while (progress) {
        progress = false;
        for (int i : growth) {
            if (used[i]) continue;
            if (tokens >= P[i]) {
                tokens = (tokens - P[i]) * T[i];
                used[i] = 1;
                result.push_back(i);
                progress = true;
            }
        }
    }

    // Phase 2: drain
    sort(drain.begin(), drain.end(), [&](int a, int b) {
        return P[a] < P[b];
    });

    for (int i : drain) {
        if (tokens >= P[i]) {
            tokens -= P[i];
            result.push_back(i);
        }
    }

    // Remaining unused growth coupons (no longer help, treat as drain)
    vector<int> leftover;
    for (int i : growth)
        if (!used[i]) leftover.push_back(i);

    sort(leftover.begin(), leftover.end(), [&](int a, int b) {
        return P[a] < P[b];
    });

    for (int i : leftover) {
        if (tokens >= P[i]) {
            tokens = (tokens - P[i]) * T[i];
            result.push_back(i);
        }
    }

    return result;
}

• 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