//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 <algorithm>
#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
// Deduce the prices for souvenirs 1 to N-1 using binary search
for (int i = 1; i < N; i++) {
long long low = 1, high = P0 - 1; // We know that P[i] < P[0] and P[i] >= P[N-1]
long long price = -1;
// Binary search to find the correct price for prices[i]
while (low <= high) {
long long mid = (low + high) / 2;
auto [L, R] = transaction(mid); // Perform the transaction with mid coins
// If the return amount is 0, it means we exactly bought souvenirs of type i
if (R == 0) {
price = mid;
break;
}
// Adjust the search range based on the coins returned
if (R > 0) {
high = mid - 1; // The price is too high, adjust the upper bound
} else {
low = mid + 1; // The price is too low, adjust the lower bound
}
}
// We should have found the price of souvenir type i
prices[i] = price;
}
// Now that we know the prices, simulate buying the souvenirs
vector<int> souvenirs_count(N, 0);
// For each souvenir type i, we need to buy exactly i souvenirs of that type
for (int i = 1; i < N; 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(); // Count how many of type i we bought
}
}
// Output the result: number of souvenirs bought for each type
for (int i = 0; i < N; i++) {
cout << souvenirs_count[i] << " ";
}
cout << endl;
}
