#include <vector>
#include <algorithm>
#include <utility>
// Grader provided function
std::pair<std::vector<int>, long long> transaction(long long M);
void buy_souvenirs(int N, long long P0) {
std::vector<long long> P(N, -1);
P[0] = P0;
std::vector<int> bought(N, 0);
// equations stores unresolved subsets: pair of <unknown variables, target sum X>
std::vector<std::pair<std::vector<int>, long long>> equations;
// Helper lambda to propagate known prices through all unresolved equations
auto simplify_all = [&]() {
bool changed = true;
while (changed) {
changed = false;
for (int i = 0; i < (int)equations.size(); ++i) {
std::vector<int> unk;
long long rem_X = equations[i].second;
for (int u : equations[i].first) {
if (P[u] != -1) {
rem_X -= P[u];
} else {
unk.push_back(u);
}
}
equations[i].first = unk;
equations[i].second = rem_X;
if (equations[i].first.empty()) {
equations.erase(equations.begin() + i);
changed = true;
break;
} else if (equations[i].first.size() == 1) {
P[equations[i].first[0]] = equations[i].second;
equations.erase(equations.begin() + i);
changed = true;
break;
}
}
}
};
// Phase 1: Discover all prices
for (int k = 1; k < N; ++k) {
while (P[k] == -1) {
long long M = -1;
if (!equations.empty()) {
// Always pick the deepest equation to advance the frontier
int best_idx = 0;
for (int i = 1; i < (int)equations.size(); ++i) {
if (equations[i].first[0] > equations[best_idx].first[0]) {
best_idx = i;
}
}
long long X = equations[best_idx].second;
M = X / equations[best_idx].first.size();
// CRITICAL FIX: Prevent overbuying already discovered items
int u0 = equations[best_idx].first[0];
for (int v = u0 + 1; v < N; ++v) {
if (P[v] == -1) {
// The first item we might buy is unknown. This is perfect, stop capping!
break;
}
if (M >= P[v]) {
// Cap M to safely skip the known item v without buying it again
M = P[v] - 1;
}
}
} else {
// If no unresolved equations, start a new chain targeting k
M = P[k-1] - 1;
}
auto res = transaction(M);
std::vector<int> L = res.first;
long long R = res.second;
long long X = M - R;
for (int item : L) {
bought[item]++;
}
std::vector<int> unk;
for (int u : L) {
if (P[u] != -1) {
X -= P[u];
} else {
unk.push_back(u);
}
}
if (unk.size() == 1) {
P[unk[0]] = X;
simplify_all();
} else if (unk.size() > 1) {
equations.push_back({unk, X});
simplify_all();
}
}
}
// Phase 2: Complete the exact required souvenir counts
for (int j = 1; j < N; ++j) {
int need = j - bought[j];
for (int step = 0; step < need; ++step) {
// M = P[j] perfectly affords exactly 1 copy of j and nothing else
transaction(P[j]);
}
}
}
