제출 #1285245

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285245		ecen30	Souvenirs (IOI25_souvenirs)	C++20	0 / 100	12 ms	400 KiB

souvenirs

//This is ChatGPT code. I am using this website to test different AI's and their abilities to solve IOI problems. Please understand. I do not mean to cheat. Just trying to get a good grade on my science project.
#include <vector>
#include <iostream>
#include <utility>

using namespace std;

// The transaction function provided by the grader.
extern pair<vector<int>, long long> transaction(long long M);

void buy_souvenirs(int N, long long P0) {
    // Initialize the prices array where we know the first price
    vector<long long> prices(N, 0);
    prices[0] = P0;  // The price of the most expensive souvenir is known

    // Binary search to determine the prices of souvenirs
    // Start with an assumption that the minimum price for the cheapest souvenir is 1.
    long long min_price = 1;
    long long max_price = P0 - 1;

    // Deduce the prices for souvenirs 1 to N-1
    for (int i = 1; i < N; i++) {
        long long current_guess = (max_price + min_price) / 2;
        
        // Perform a transaction with the current guess for the price
        auto [L, R] = transaction(current_guess);
        
        // If we receive souvenirs (R == 0), we have identified the price
        if (R == 0) {
            prices[i] = current_guess;
        }

        // Adjust the price range based on the remaining coins (R)
        if (R > 0) {
            // If there are remaining coins, the price is too high
            max_price = current_guess - 1;
        } else {
            // If there are no remaining coins, the price is too low
            min_price = current_guess + 1;
        }
    }

    // Now that we know the prices, simulate buying the souvenirs
    vector<int> souvenirs_count(N, 0);

    // Loop through all souvenir types (except for the most expensive one, type 0)
    for (int i = 1; i < N; i++) {
        // We need to buy exactly `i` souvenirs of type `i`
        for (int j = 0; j < i; j++) {
            long long coins_needed = prices[i];
            
            // Perform a transaction to buy one souvenir of type `i`
            auto [L, R] = transaction(coins_needed);
            souvenirs_count[i] += L.size();
        }
    }

    // Output the result: number of souvenirs bought for each type
    for (int i = 0; i < N; i++) {
        cout << souvenirs_count[i] << " ";
    }
    cout << endl;
}

• 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