Submission #1288731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288731		ecen30	Souvenirs (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> P(N);
    P[0] = P0;
    
    // Discover all prices
    // Start by finding P[N-1] using binary search
    long long low = 1, high = P0 - 1;
    
    // Find P[N-1] - the minimum price
    while (low < high) {
        long long mid = (low + high) / 2;
        auto result = transaction(mid);
        
        if (result.first.empty()) {
            // mid < P[N-1]
            low = mid + 1;
        } else {
            // mid >= P[N-1]
            high = mid;
        }
    }
    P[N-1] = low;
    
    // Discover other prices from top to bottom
    for (int i = 1; i < N - 1; i++) {
        // Find P[i] by testing values between P[i-1]-1 and P[N-1]
        low = P[N-1];
        high = P[i-1] - 1;
        
        while (low < high) {
            long long mid = (low + high + 1) / 2;
            auto result = transaction(mid);
            
            // Check if we bought type i
            bool bought_i = false;
            for (int t : result.first) {
                if (t == i) {
                    bought_i = true;
                    break;
                }
            }
            
            if (bought_i) {
                // mid >= P[i]
                low = mid;
            } else {
                // mid < P[i]
                high = mid - 1;
            }
        }
        P[i] = low;
    }
    
    // Now we know all prices, buy the required souvenirs
    // For type i, we need i souvenirs
    vector<int> remaining(N);
    for (int i = 0; i < N; i++) {
        remaining[i] = i;
    }
    
    // Buy souvenirs optimally
    while (true) {
        bool done = true;
        for (int i = 1; i < N; i++) {
            if (remaining[i] > 0) {
                done = false;
                break;
            }
        }
        if (done) break;
        
        // Calculate optimal amount to spend
        long long amount = 0;
        for (int i = 1; i < N; i++) {
            if (remaining[i] > 0) {
                amount += P[i];
            }
        }
        
        // Make sure amount is valid (< P[0] and >= P[N-1])
        if (amount >= P[0]) {
            // Buy one at a time for remaining types
            for (int i = 1; i < N; i++) {
                while (remaining[i] > 0) {
                    auto result = transaction(P[i]);
                    for (int t : result.first) {
                        remaining[t]--;
                    }
                }
            }
            break;
        }
        
        auto result = transaction(amount);
        for (int t : result.first) {
            remaining[t]--;
        }
    }
}

• 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