#include "souvenirs.h"
#include <utility>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
void clear(vector<pair<long long, vector<int>>>& prices, vector<long long>& solo, int index) {
long long& ticksum = prices[index].first;
vector<int>& tickvec = prices[index].second;
for(int i = 0; i < tickvec.size(); i++) {
if(solo[tickvec[i]] != -1) {
ticksum -= solo[tickvec[i]];
tickvec[i] = tickvec.back();
tickvec.pop_back();
i--;
}
}
if(tickvec.size() == 1 && tickvec[0] == index) {
solo[index] = ticksum;
ticksum -= solo[tickvec[0]];
tickvec.clear();
}
}
void buy_souvenirs(int N, long long P0) {
vector<pair<long long, vector<int>>> prices(N, make_pair(-1, vector<int>()));
vector<long long> solo(N, -1);
solo[0] = P0;
prices[0] = make_pair(0, vector<int>());
vector<int> purchased(N, 0);
while(true) {
int lastknown = N;
for(int i = N - 1; i >= 0; i--) {
if(prices[i].first != -1 && solo[i] == -1) {
clear(prices, solo, i);
}
if(prices[i].first == -1) {
break;
}
lastknown = i;
}
if(lastknown == 0) break;
int tick = -1;
for(int i = lastknown - 1; i >= 0; i--) {
if(prices[i].first != -1) {
tick = i;
break;
}
}
clear(prices, solo, tick);
long long& ticksum = prices[tick].first;
vector<int>& tickvec = prices[tick].second;
long long query;
if(solo[tick] != -1) {
query = solo[tick] - 1;
}
else {
query = ticksum / tickvec.size();
}
pair<vector<int>, long long> ans = transaction(query);
prices[ans.first[0]] = make_pair(query - ans.second, ans.first);
for(int a : ans.first) purchased[a]++;
}
for(int i = 0; i < N; i++) {
while(purchased[i] < i) {
transaction(solo[i]);
purchased[i]++;
}
}
return;
}
