Submission #1289148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289148		ecen30	Souvenirs (IOI25_souvenirs)	C++20	0 / 100	14 ms	404 KiB

souvenirs

//testing AI Code
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>

// The provided interface for the interactive problem
std::pair<std::vector<int>, long long> transaction(long long M);

void buy_souvenirs(int N, long long P0) {
    // P_actual will store the determined prices P[1] through P[N-1].
    // P_actual[i] will store P[i]. P[0] is already P0.
    std::vector<long long> P_actual(N);
    P_actual[0] = P0;

    // A map to store the determined prices based on the single souvenir bought.
    // Key: souvenir type index (i), Value: price P[i]
    std::map<int, long long> single_price_map;

    // --- Part 1: Determine the prices P[1] through P[N-1] ---
    
    // Constraints on P[i] suggest that P[i] <= 10. Let's use the given P0.
    // We only need to check M up to P0 - 1.
    // The transaction(M) is guaranteed to buy at least one souvenir only if M >= P[N-1].
    // To ensure we get all prices, we check all possible M up to P0 - 1.
    // Note: M must be in [P[N-1], P[0] - 1]. Since P[N-1] is unknown, we check M >= 1.
    // The problem states P[i] are distinct.
    
    long long max_M = P0 - 1;
    // We can try M from 1 up to a small limit, like 10, or P0-1.
    // Since N <= 100, P[i] <= 10, then P0 <= 100 for N=100. Let's use P0-1.
    
    for (long long M = 1; M <= max_M; ++M) {
        std::pair<std::vector<int>, long long> result = transaction(M);
        std::vector<int> L = result.first;
        long long R = result.second;
        
        // If only a single souvenir of type i is bought, then P[i] = M - R.
        // This is a reliable way to find P[i] because:
        // 1. M < P[0] ensures no type 0 is bought.
        // 2. If L={i}, M must be < P[j] for all j < i (since they are checked first).
        // 3. Since P[j] < P[i] for all j > i, L={i} and R=0 is the ideal case for M=P[i].
        //    However, if R>0, it means the remaining R coins were not enough to buy P[j] for j>i.
        
        if (L.size() == 1) {
            int i = L[0];
            long long price = M - R;
            // The constraint P[0] > M >= P[N - 1] must be met, but the *problem* is to 
            // find prices, so we must be able to call transaction(M).
            // We only need to check M's that *could* be a single price.
            // If P[i] is already found, this M must correspond to a new P[j].
            
            // To be more robust, we should only trust the result if it uniquely identifies a price.
            // P[i] = M - R is the price. Since prices are distinct, we can use the determined price.
            bool already_found = false;
            for(const auto& pair : single_price_map) {
                if (pair.second == price) {
                    already_found = true;
                    break;
                }
            }
            if (!already_found) {
                single_price_map[i] = price;
            }
        }
    }

    // Since P[i] are distinct, we collect all found prices and sort them to assign.
    std::vector<long long> determined_prices;
    for (const auto& pair : single_price_map) {
        determined_prices.push_back(pair.second);
    }
    
    // If not enough prices are found from the single-souvenir-purchase strategy, we might need 
    // to include the ones that weren't found. This would be necessary if all prices
    // lead to multi-souvenir purchases. Let's assume the single-purchase strategy is enough 
    // because the distinct prices are small (<= 10).
    
    // Sort in decreasing order to assign P[1], P[2], ...
    std::sort(determined_prices.rbegin(), determined_prices.rend());
    
    // Assign to P_actual[1], P_actual[2], ...
    for (int i = 1; i < N; ++i) {
        // determined_prices size must be N-1. If not, the simple strategy failed.
        // With P[i] <= 10, P0 > P1 > ... > P[N-1], and N <= 100, P[i] will be in [1, 9].
        // The distinctness forces N-1 prices. The problem constraints are generous.
        if (i - 1 < determined_prices.size()) {
             P_actual[i] = determined_prices[i - 1];
        } else {
             // This case should not happen based on constraints and test M=1 to 9.
             // If it does, we must assume P[i] is a small number not found, but we can't guess.
             // For a safe assumption in a contest, we could take the smallest available.
        }
    }
    
    // The problem requires at least one souvenir and M >= P[N-1].
    long long P_N_minus_1 = P_actual[N - 1];
    if (P_N_minus_1 == 0) {
        // If not found, a very unlikely scenario under the given constraints.
        // We must ensure M >= P[N-1], so a safe M is P[0]-1 if P[N-1] is not 1.
        // If P[N-1] = 1, then P_actual[N-1]=1.
        // Let's assume P_actual[N-1] is correctly determined and is >= 1.
    }


    // --- Part 2: Buy the required souvenirs ---
    // We need i souvenirs of type i for i = 1 to N-1.
    // We will perform i transactions of M = P[i] for each type i.
    // Transaction(P[i]) results in ({i}, 0) because P[i] is enough to buy P[i], 
    // but not P[j] for j < i (since P[i] < P[j]), and not P[j] for j > i (since C=0).
    
    for (int i = 1; i < N; ++i) {
        long long M = P_actual[i];
        
        // Safety check: The constraints on M must be met: P[0] > M >= P[N - 1].
        // Our M=P[i] is correct because:
        // 1. P[0] > P[i] (by price order)
        // 2. P[i] >= P[N-1] (by price order)
        
        for (int k = 0; k < i; ++k) {
            // Note: the problem does not require to minimize transactions.
            transaction(M); 
        }
    }
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 4
• Subtask 2: 0 / 3
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 0 / 28
• Subtask 6: 0 / 33