//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]++; } } }