#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void buy_souvenirs(int n, ll p0) {
vector<ll> prices(n, -1);
prices[0] = p0;
vector<ll> cnt(n);
// transaction on nxt
vector<pair<vector<ll>, ll>> cur;
map<ll, pair<vector<ll>, ll>> cache;
auto get = [&](ll cost) {
if (cache.count(cost) == 1) {
return cache[cost];
}
auto [vals, over] = transaction(cost);
for (auto &val: vals) {
cnt[val]++;
}
return cache[cost] = pair{vector<ll>(vals.begin(), vals.end()), over};
};
vector<bool> used(n);
while (count(prices.begin(), prices.end(), -1) != 0) {
auto update = [&](vector<ll> vals, ll sum) -> pair<vector<ll>, ll> {
vector<ll> new_vals;
for (auto &val: vals) {
if (prices[val] == -1) {
new_vals.push_back(val);
} else {
sum -= prices[val];
}
}
return {new_vals, sum};
};
auto update_cur = [&]() {
vector<pair<vector<ll>, ll>> new_cur;
for (auto [vals, sum]: cur) {
tie(vals, sum) = update(vals, sum);
if (!vals.empty()) {
new_cur.push_back({vals, sum});
}
}
cur = new_cur;
};
auto clear = [&]() {
while (true) {
update_cur();
bool changed = false;
for (auto &[vals, sum]: cur) {
if (vals.size() == 1) {
prices[vals[0]] = sum;
changed = true;
}
}
if (!changed) {
break;
}
}
};
bool started = false;
while (!cur.empty() || !started) {
started = true;
ll cost = 0;
auto next = [&](ll i) -> ll {
for (; i < n; ++i) {
if (prices[i] == -1) {
return prices[i - 1] - 1;
}
}
return -1;
};
if (cur.empty()) {
cost = next(0);
} else {
std::sort(cur.begin(), cur.end(), [](auto a, auto b) {
return make_pair(a.first.back(), a.first.front()) > make_pair(b.first.back(), b.first.front());
});
// for (int i = 0; i < cur.size(); ++i) {
//
// cout << "{ ";
// for (auto &val: cur[i].first) {
// cout << val << " ";
// }
// cout << "}" << " " << cur[i].second << '\n';
//
// }
// cout << "-------------------------" << '\n';
cost = cur.front().second / cur.front().first.size();
}
// cost = next();
while (count(prices.begin(), prices.end(), -1) != 0) {
// cout << cost << endl;
// cout << cnt[4] << endl;
auto [vals, over] = get(cost);
// for (auto &val: vals) {
// cnt[val]++;
// }
ll old = vals[0];
ll sum = cost - over;
tie(vals, sum) = update(vals, sum);
cur.push_back({vals, sum});
if (vals.size() == 0) {
cost = next(old);
if (cost == -1) {
break;
}
} else if (vals.size() == 1) {
prices[vals[0]] = sum;
clear();
cost = next(vals[0]);
if (cost == -1) {
break;
}
} else {
cost = sum / vals.size();
}
}
clear();
}
}
for (int i = 0; i < n; ++i) {
while (cnt[i] < i) {
assert(transaction(prices[i]).first.size() == 1);
cnt[i]++;
}
// assert(cnt[i] == i);
}
return;
}
