Submission #1254694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254694		fasterthanyou	Festival (IOI25_festival)	C++20	0 / 100	152 ms	197444 KiB

festival

#include <bits/stdc++.h>

#include <ranges>
using namespace std;

#ifdef LOCAL
#include "../../debug.h"
#else
#define debug(...) 42
#endif

namespace utils {
template <typename T>
bool chMax(T& target, const T& value) {
    if (value > target) {
        target = value;
        return true;
    }
    return false;
}

template <typename T>
bool chMin(T& target, const T& value) {
    if (value < target) {
        target = value;
        return true;
    }
    return false;
}
}  // namespace utils
using namespace utils;

using ll = long long;
using ld = long double;
using mp = vector<vector<int>>;
const char el = '\n';

// Helper function to find the index of the single set bit.
// GCC and Clang provide a fast intrinsic for this.
int get_bit_index(int n) {
#ifdef __GNUC__
    return __builtin_ctz(n); // Count Trailing Zeros
#else
    if (n == 0) return 0;
    int index = 0;
    while ((n & 1) == 0) {
        n >>= 1;
        index++;
    }
    return index;
#endif
}


std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
    int N = P.size();
    if (N == 0) {
        return {};
    }
    
    int num_masks = 1 << N;

    // dp[mask] = max tokens after buying coupons in the set 'mask'
    std::vector<long long> dp(num_masks, -1);

    // parent[mask] = the mask we came from to optimally reach 'mask'
    std::vector<int> parent(num_masks, 0);

    // Base case: 0 coupons bought, we have A tokens
    dp[0] = A;

    // Fill the DP table
    for (int mask = 0; mask < num_masks; ++mask) {
        // If this state is unreachable, we can't buy more from here
        if (dp[mask] == -1) {
            continue;
        }

        // Try to buy each coupon 'i' that is NOT in the current mask
        for (int i = 0; i < N; ++i) {
            // Check if i-th bit is NOT set in the mask
            if (!((mask >> i) & 1)) {
                // Check if we can afford coupon 'i'
                if (dp[mask] >= P[i]) {
                    long long new_tokens = (dp[mask] - P[i]) * T[i];
                    int next_mask = mask | (1 << i);

                    // If this path is better, update dp and store the parent
                    if (new_tokens > dp[next_mask]) {
                        dp[next_mask] = new_tokens;
                        parent[next_mask] = mask;
                    }
                }
            }
        }
    }

    // Find the best reachable final state (mask)
    int max_coupons_count = 0;
    int best_final_mask = 0;
    long long max_tokens_for_best_path = -1;

    for (int mask = 0; mask < num_masks; ++mask) {
        if (dp[mask] != -1) {
            // Get number of coupons for this mask
            int current_coupons = __builtin_popcount(mask);

            // If we found a path with more coupons, it's the new best
            if (current_coupons > max_coupons_count) {
                max_coupons_count = current_coupons;
                best_final_mask = mask;
                max_tokens_for_best_path = dp[mask];
            } 
            // Tie-breaking: if coupon count is the same, prefer more tokens
            else if (current_coupons == max_coupons_count) {
                if (dp[mask] > max_tokens_for_best_path) {
                    best_final_mask = mask;
                    max_tokens_for_best_path = dp[mask];
                }
            }
        }
    }

    // If we couldn't afford any coupons
    if (max_coupons_count == 0) {
        return {};
    }
    
    // Reconstruct the path by backtracking from the best final mask
    std::vector<int> optimal_order;
    int current_mask = best_final_mask;

    while (current_mask != 0) {
        int prev_mask = parent[current_mask];
        // The difference in masks gives us the last coupon bought
        int coupon_mask = current_mask ^ prev_mask; 
        int coupon_index = get_bit_index(coupon_mask);
        
        optimal_order.push_back(coupon_index);
        
        // Move to the previous state
        current_mask = prev_mask;
    }

    // The path was reconstructed backwards, so reverse it
    std::reverse(optimal_order.begin(), optimal_order.end());

    return optimal_order;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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