#include "souvenirs.h"
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
const i64 MX = 1e15;
void buy_souvenirs(int n, i64 P0){
std::vector<i64> p(n);
p[0] = P0;
std::set<std::pair<std::vector<int>, i64>> S;//[p1, p2 ... pn], cost
std::vector<int> sc = {0};
S.insert(make_pair(sc, p[0]));
std::vector<int> EQ(n), CNT(n); // we have an eqn where min index = i
while(!S.empty()){
auto [v, sm] = *S.rbegin();
S.erase(*S.rbegin());
//first update indices to latest
std::vector<int> nv;
for(auto x : v){
if(p[x]) sm -= p[x];
else nv.push_back(x);
}
if(v.front() == 0){
//ask 0!
auto [res, rem] = transaction(p[0] - 1);
i64 used = p[0] - 1 - rem;
EQ[res.front()] = 1;
S.insert(std::make_pair(res, used));
for(auto x : res) CNT[x]++;
// cout << S.size() << '\n';
}
else if(nv.empty()){
//do nothing
}
else if(nv.size() == 1){
p[nv.back()] = sm;
auto i = nv.back();
if(i + 1 < n and EQ[i + 1] == 0){
auto [res, rem] = transaction(p[i] - 1);
for(auto x : res) CNT[x]++;
i64 used = p[i] - 1 - rem;
EQ[res.front()] = 1;
assert(res.front() == i + 1);
S.insert(make_pair(res, used));
}
}
else{
//ask sm / n
i64 old = sm;
sm /= nv.size();
auto [res, rem] = transaction(sm);
for(auto x : res) CNT[x]++;
i64 used = sm - rem;
EQ[res.front()] = 1;
EQ[nv.front()] = 1;
S.insert(make_pair(res, used));
S.insert(make_pair(nv, old));
}
}
for(int i = 0; i < n; i++){
while(CNT[i] < i) {
++CNT[i];
transaction(p[i]);
}
}
}
