//This is Grok 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 <bits/stdc++.h>
#include "souvenirs.h"
using namespace std;
pair<vector<int>, long long> transaction(long long M);
void buy_souvenirs(int n, long long P0) {
vector<long long> price(n);
price[0] = P0;
// Step 1: Discover all prices using a single greedy descent
// We start with M = P0-1 and repeatedly take the "leading" transaction
// that buys the highest type not yet fully resolved.
vector<vector<int>> leading(n);
vector<long long> spent(n, 0);
vector<int> bought(n, 0);
int resolved = 0;
long long M = P0 - 1;
while (resolved < n - 1) {
auto [types, rem] = transaction(M);
sort(types.begin(), types.end());
long long cost = M - rem;
int lead = types.empty() ? 0 : types[0];
if (leading[lead].empty()) {
leading[lead] = types;
spent[lead] = cost;
resolved++;
}
for (int t : types) bought[t]++;
// Reduce M to force buying lower types or resolve current lead
if (types.size() == 1) {
M = cost - 1; // Avoid exact match unless needed
} else {
M = cost / types.size();
if (M * (long long)types.size() == cost) M--;
}
// Stop when we have enough information to resolve all
if (lead == n - 1 && resolved == n - 1) break;
}
// Step 2: Resolve prices from highest to lowest
for (int i = n - 1; i >= 1; --i) {
if (price[i]) continue;
long long total = spent[i];
for (int j : leading[i]) {
if (j != i && price[j]) {
total -= price[j];
}
}
price[i] = total;
}
// Step 3: Buy exactly i souvenirs of type i (for i=1 to n-1)
for (int i = 1; i < n; ++i) {
while (bought[i] < i) {
transaction(price[i]);
bought[i]++;
}
}
}
