#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<int> cnt(n);
// transaction on nxt
vector<pair<vector<int>, ll>> cur;
map<ll, pair<vector<int>, ll>> cache;
auto get = [&](ll cost) {
if (cache.count(cost)) {
return cache[cost];
} else {
auto [vals, over] = transaction(cost);
for (auto &val: vals) {
cnt[val]++;
}
cache[cost] = {vals, over};
return pair{vals, over};
}
};
while (count(prices.begin(), prices.end(), -1) != 0) {
auto update = [&](vector<int> vals, ll sum) -> pair<vector<int>, ll> {
vector<int> 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<int>, 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;
if (cur.empty()) {
for (int i = 0; i < n; ++i) {
if (prices[i] == -1) {
cost = prices[i - 1] - 1;
break;
}
}
} else {
std::sort(cur.begin(), cur.end(), [](auto a, auto b) {
return make_pair(a.first.front(), a.second) > make_pair(b.first.front(), b.second);
});
cost = cur.front().second / cur.front().first.size();
// cout << cost << endl;
// for (int i = 0; i < cur.size(); ++i) {
//
// cout << "{ ";
// for (auto &val: cur[i].first) {
// cout << val << " ";
// }
// cout << "}" << " " << cur[i].second << '\n';
//
// }
// cout << "-------------------------" << '\n';
}
while (count(prices.begin(), prices.end(), -1) != 0) {
auto [vals, over] = get(cost);
// for (auto &val: vals) {
// cnt[val]++;
// }
ll sum = cost - over;
bool sub = !(vals.size() == 1 && vals[0] == n - 1);
ll old_sum = sum;
tie(vals, sum) = update(vals, sum);
cur.push_back({vals, sum});
if (vals.size() == 0) {
if (sub) {
cost = old_sum - 1;
} else {
break;
}
} else if (vals.size() == 1) {
prices[vals[0]] = sum;
clear();
if (vals[0] == n - 1) {
break;
} else {
cost = sum - 1;
}
} 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;
}
