Submission #1288732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288732		ecen30	선물 (IOI25_souvenirs)	C++20	0 / 100	13 ms	388 KiB

souvenirs

//testing AI CODe
#include "souvenirs.h"
#include <vector>
#include <algorithm>

using namespace std;

void buy_souvenirs(int N, long long P0) {
    vector<long long> prices(N);
    prices[0] = P0;
    vector<int> bought(N, 0);
    
    // Strategy: Discover prices by binary search, then buy exact amounts needed
    
    // Step 1: Find P[N-1] (the cheapest item)
    long long lo = 1, hi = P0 - 1;
    while (lo < hi) {
        long long mid = (lo + hi) / 2;
        auto result = transaction(mid);
        
        // Update bought counts
        for (int item : result.first) {
            bought[item]++;
        }
        
        if (result.first.empty() || result.first.back() < N - 1) {
            // Didn't buy item N-1, so mid < P[N-1]
            lo = mid + 1;
        } else {
            // Bought item N-1, so mid >= P[N-1]
            hi = mid;
        }
    }
    prices[N - 1] = lo;
    
    // Step 2: Find other prices by testing specific amounts
    // Key insight: If we pay exactly sum of prices from i to N-1,
    // we buy exactly items i through N-1
    for (int i = N - 2; i >= 1; i--) {
        // Binary search for P[i]
        lo = prices[N - 1];
        hi = (i == 1) ? (P0 - 1) : prices[i - 1] - 1;
        
        while (lo < hi) {
            long long mid = (lo + hi + 1) / 2;
            
            // Test: pay mid + (sum of prices from i+1 to N-1)
            long long test_amount = mid;
            for (int j = i + 1; j < N; j++) {
                test_amount += prices[j];
            }
            
            // Make sure test_amount is valid
            if (test_amount >= P0) {
                // Just test mid alone
                auto result = transaction(mid);
                for (int item : result.first) {
                    bought[item]++;
                }
                
                // Check if item i was bought
                bool bought_i = false;
                for (int item : result.first) {
                    if (item == i) {
                        bought_i = true;
                        break;
                    }
                }
                
                if (bought_i) {
                    lo = mid;
                } else {
                    hi = mid - 1;
                }
            } else {
                auto result = transaction(test_amount);
                for (int item : result.first) {
                    bought[item]++;
                }
                
                // If we bought item i, then mid >= P[i]
                bool bought_i = false;
                for (int item : result.first) {
                    if (item == i) {
                        bought_i = true;
                        break;
                    }
                }
                
                if (bought_i) {
                    // We can deduce the price from what was bought
                    long long total_spent = test_amount - result.second;
                    long long known_sum = 0;
                    for (int item : result.first) {
                        if (item > i) {
                            known_sum += prices[item];
                        }
                    }
                    prices[i] = total_spent - known_sum;
                    break;
                } else {
                    hi = mid - 1;
                }
            }
        }
        
        if (prices[i] == 0) {
            prices[i] = lo;
        }
    }
    
    // Step 3: Buy remaining souvenirs to meet quotas
    // We need exactly i souvenirs of type i
    for (int i = 1; i < N; i++) {
        while (bought[i] < i) {
            auto result = transaction(prices[i]);
            for (int item : result.first) {
                bought[item]++;
            }
        }
    }
}

• 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