#include "souvenirs.h"
#include <utility>
#include <vector>
#include <cassert>
#include <iostream>
using namespace std;
void buy_souvenirs(int N, long long P0) {
vector<long long> p(N, -1);
vector<int> bought(N, 0);
p[0] = P0;
auto my_transaction = [&](long long M) {
// cerr << "transaction: " << M << endl;
// for(auto x: p) cerr << x << " " << endl;
auto [v, c] = transaction(M);
for(int x: v) bought[x]++;
return make_pair(v, M - c);
};
auto clean_group = [&](vector<int> &v, long long &c) {
vector<int> new_v;
for(int x: v) {
if(p[x] != -1) c -= p[x];
else new_v.push_back(x);
}
v = new_v;
};
auto rec = [&](auto &&self, vector<int> v, long long c) -> void {
// cerr << v.size() << " " << c << endl;
while(v.size() > 1) {
auto [next_v, next_c] = my_transaction(c / v.size());
self(self, next_v, next_c);
clean_group(v, c);
}
assert(v.size() == 1);
p[v[0]] = c;
for(int i=v[0]; i<N; i++) {
if(p[i] == -1) {
auto [v, c] = my_transaction(p[i-1] - 1);
self(self, v, c);
}
}
};
for(int i=1; i<N; i++) {
if(p[i] == -1) {
auto [v, c] = my_transaction(p[i-1] - 1);
rec(rec, v, c);
}
assert(p[i] != -1);
// cerr << i << " price " << p[i] << endl;
while(bought[i] < i) my_transaction(p[i]);
}
}
