#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
struct Query
{
long long val;
vector<int> id;
};
vector<Query> Tab;
void review(long long x, vector<long long> &price, vector<long long> &atmost, long long targ)
{
while (!Tab[x].id.empty() && Tab[x].id.back() > targ)
{
Tab[x].val -= price[Tab[x].id.back()];
Tab[x].id.pop_back();
}
if (Tab[x].id.empty())return;
if (Tab[x].id.size() == 1)
price[Tab[x].id.back()] = Tab[x].val;
else
atmost[Tab[x].id.back()] = Tab[x].val / Tab[x].id.size();
}
void buy_souvenirs(int N, long long P0)
{
vector<long long> cnt(N), price(N, -1), atmost(N, -1);
int targ = N - 1, cur = 0, until = 1;
while (targ >= until)
{
while (price[targ] == -1)
{
long long ask = price[cur] - 1;
if (price[cur] == -1)
ask = atmost[cur];
pair<vector<int>, long long> temp = transaction(ask);
Tab.push_back({ask - temp.second, temp.first});
for (long long i = 0; i < Tab.back().id.size(); i++)
cnt[Tab.back().id[i]]++;
review(Tab.size() - 1, price, atmost, targ);
cur = Tab.back().id.back();
}
while (until < N && cnt[until] == until)
until++;
targ--;
cur = 0;
for (long long i = 0; i < Tab.size(); i++)
{
review(i, price, atmost, targ);
if (Tab[i].id.empty())
{
swap(Tab[i], Tab.back());
Tab.pop_back();
i--;
continue;
}
cur = max(cur, Tab[i].id.back());
}
}
for (long long i = 0; i < N; i++)
{
while (cnt[i] < i)
{
transaction(price[i]);
cnt[i]++;
}
}
}
