제출 #1308110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308110		orosmori	축제 (IOI25_festival)	C++20	5 / 100	51 ms	9784 KiB

festival

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

// Structure to keep track of coupon details along with their original index
struct Coupon {
    int id;
    long long p;
    long long t;
};

// Comparator for high-type coupons (T > 1)
// Sorts based on the key: (P * T) / (T - 1)
// We compare a < b by cross-multiplying: 
// a.p * a.t * (b.t - 1) < b.p * b.t * (a.t - 1)
bool compareHigh(const Coupon& a, const Coupon& b) {
    long long valA = a.p * a.t * (b.t - 1);
    long long valB = b.p * b.t * (a.t - 1);
    if (valA != valB) {
        return valA < valB;
    }
    return a.p < b.p; // Tie-breaker
}

std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
    int n = P.size();
    vector<Coupon> high; // Stores coupons with T > 1
    vector<Coupon> ones; // Stores coupons with T = 1

    for (int i = 0; i < n; ++i) {
        if (T[i] == 1) {
            ones.push_back({i, (long long)P[i], (long long)T[i]});
        } else {
            high.push_back({i, (long long)P[i], (long long)T[i]});
        }
    }

    // 1. Sort High coupons by the optimal greedy key
    sort(high.begin(), high.end(), compareHigh);
    
    // 2. Sort T=1 coupons by Price (cheapest first)
    sort(ones.begin(), ones.end(), [](const Coupon& a, const Coupon& b) {
        return a.p < b.p;
    });

    // 3. Precompute prefix sums for T=1 coupons to allow O(log N) queries
    int m = ones.size();
    vector<long long> ones_pref(m + 1, 0);
    for (int i = 0; i < m; ++i) {
        ones_pref[i+1] = ones_pref[i] + ones[i].p;
    }

    int best_total_count = -1;
    vector<int> best_selection;

    // 4. Iterate through possible counts of High coupons.
    // Due to Subtask 6 constraints, tokens decrease exponentially for T >= 2.
    // We can't buy more than ~60 high-type coupons before running out of tokens (since A <= 10^9).
    // We take a safe upper bound of 70 or the size of the high list.
    int max_k = min((int)high.size(), 75); 

    for (int k = 0; k <= max_k; ++k) {
        long long current_tokens = A;
        bool possible = true;
        vector<int> current_indices;
        
        // Try buying the first k high coupons in sorted order
        for (int i = 0; i < k; ++i) {
            if (current_tokens >= high[i].p) {
                current_tokens = (current_tokens - high[i].p) * high[i].t;
                current_indices.push_back(high[i].id);
            } else {
                possible = false;
                break;
            }
        }

        if (possible) {
            // We have 'current_tokens' left. Fill with cheapest T=1 coupons.
            // Find the largest index in prefix sum such that sum <= current_tokens
            auto it = upper_bound(ones_pref.begin(), ones_pref.end(), current_tokens);
            int count_ones = (int)(it - ones_pref.begin()) - 1; 
            
            // Check if this combination is the best so far
            if (k + count_ones > best_total_count) {
                best_total_count = k + count_ones;
                best_selection = current_indices; // First the high coupons
                // Then append the ones
                for (int i = 0; i < count_ones; ++i) {
                    best_selection.push_back(ones[i].id);
                }
            }
        } else {
            // Optimization: If we can't afford the first k (sorted by "efficiency"),
            // we likely can't afford k+1. We can break here.
            break;
        }
    }

    return best_selection;
}

• 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