제출 #1259345

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1259345		ducthanh2306	축제 (IOI25_festival)	C++20	5 / 100	140 ms	9612 KiB

festival

#include <vector>
#include <algorithm>
#include <map>
#include <functional>
#include <numeric>

using namespace std;

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    int N = P.size();
    
    // Handle empty case
    if (N == 0) return {};
    
    // For small N, use bitmask DP
    if (N <= 20) {
        map<pair<int, int>, pair<int, vector<int>>> dp;
        
        function<pair<int, vector<int>>(int, int)> solve = [&](int tokens, int mask) -> pair<int, vector<int>> {
            auto state = make_pair(tokens, mask);
            if (dp.count(state)) return dp[state];
            
            pair<int, vector<int>> best = {0, {}};
            
            for (int i = 0; i < N; i++) {
                if (!(mask & (1 << i)) && tokens >= P[i]) {
                    int new_tokens = (tokens - P[i]) * T[i];
                    int new_mask = mask | (1 << i);
                    
                    auto sub = solve(new_tokens, new_mask);
                    if (sub.first + 1 > best.first) {
                        best = {sub.first + 1, sub.second};
                        best.second.insert(best.second.begin(), i);
                    }
                }
            }
            
            return dp[state] = best;
        };
        
        return solve(A, 0).second;
    }
    
    // For larger N, try multiple greedy strategies
    vector<vector<int>> strategies;
    
    // Strategy 1: Sort by price ascending
    {
        vector<int> order(N);
        iota(order.begin(), order.end(), 0);
        sort(order.begin(), order.end(), [&](int a, int b) {
            return P[a] < P[b];
        });
        strategies.push_back(order);
    }
    
    // Strategy 2: Sort by multiplier descending, then price ascending
    {
        vector<int> order(N);
        iota(order.begin(), order.end(), 0);
        sort(order.begin(), order.end(), [&](int a, int b) {
            if (T[a] != T[b]) return T[a] > T[b];
            return P[a] < P[b];
        });
        strategies.push_back(order);
    }
    
    // Strategy 3: Sort by ratio (T[i] - 1) / P[i] descending
    {
        vector<int> order(N);
        iota(order.begin(), order.end(), 0);
        sort(order.begin(), order.end(), [&](int a, int b) {
            double ratio_a = (double)(T[a] - 1) / P[a];
            double ratio_b = (double)(T[b] - 1) / P[b];
            if (abs(ratio_a - ratio_b) > 1e-9) return ratio_a > ratio_b;
            return P[a] < P[b];
        });
        strategies.push_back(order);
    }
    
    // Strategy 4: High multipliers first, then by price
    {
        vector<int> high, low;
        for (int i = 0; i < N; i++) {
            if (T[i] >= 3) high.push_back(i);
            else low.push_back(i);
        }
        sort(high.begin(), high.end(), [&](int a, int b) {
            if (T[a] != T[b]) return T[a] > T[b];
            return P[a] < P[b];
        });
        sort(low.begin(), low.end(), [&](int a, int b) {
            return P[a] < P[b];
        });
        
        vector<int> order;
        for (int x : high) order.push_back(x);
        for (int x : low) order.push_back(x);
        strategies.push_back(order);
    }
    
    // For very small N, try all permutations
    if (N <= 8) {
        vector<int> perm(N);
        iota(perm.begin(), perm.end(), 0);
        do {
            strategies.push_back(perm);
        } while (next_permutation(perm.begin(), perm.end()));
    }
    
    vector<int> best_result;
    
    // Try each strategy
    for (const auto& order : strategies) {
        vector<bool> bought(N, false);
        vector<int> result;
        int tokens = A;
        
        // Keep trying to buy coupons until no progress
        bool progress = true;
        while (progress) {
            progress = false;
            for (int i : order) {
                if (!bought[i] && tokens >= P[i]) {
                    bought[i] = true;
                    result.push_back(i);
                    tokens = (tokens - P[i]) * T[i];
                    progress = true;
                }
            }
        }
        
        if (result.size() > best_result.size()) {
            best_result = result;
        }
        
        // Early termination if we bought all coupons
        if (result.size() == N) break;
    }
    
    return best_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