#include "souvenirs.h"
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
vector<pair<vector<signed>,int>> transactions;
vector<int> rem;
vector<int> val;
int N;
bool poss(int j, int x){
int cv=1;
vector<int> val2=val;
val2[j]=x;
for (int i = N-1; i >= 0; i--)
{
if(val2[i]!=-1) {
if(cv>val2[i]) return false;
cv=val2[i];
}
val2[i]=cv;
cv++;
}
for (auto u : transactions)
{
int csum=0;
for (auto v : u.first) csum+=val2[v];
if(csum>u.second) return false;
}
return true;
}
void clean_transaction(){
for (auto u : transactions)
{
int rem=u.second;
int rems=sz(u.first);
for (auto v : u.first){
if(val[v]!=-1) rems--;
if(val[v]!=-1) rem-=val[v];
}
if(rems==1){
for (auto v : u.first){
if(val[v]==-1) val[v]=rem;
}
}
}
}
void buy_souvenirs(signed _N, int P0) {
N=_N;
val.resize(N+1,-1);
rem.resize(N,0);
val[0]=P0;
int j=N-1;
for (int i = 0; i < N; i++) rem[i]=i;
val[N]=0;
int mx=P0-j;
while(j>0){
/*if(rem[j]==0) {
j--;
continue;
}*/
if(val[j]!=-1) {
j--;
mx=P0-j+1;
continue;
}
int l=val[j+1]+1; int r=mx;
int ans=-1;
while(l<=r){
int mid=(l+r)/2;
if(poss(j,mid)){
l=mid+1;
ans=mid;
}else{
r=mid-1;
}
}
ans=r;
pair<vector<signed>, int> res=transaction(ans);
res.second=ans-res.second;
// cerr << ans << ": ";
for (auto u : res.first) {
// cerr << u << " ";
rem[u]--;
}
// cerr << "\n";
if(sz(res.first)==1) val[res.first[0]]=res.second;
else transactions.push_back(res);
mx--;
clean_transaction();
}
for (int i = 0; i < N; i++)
{
while(rem[i]>0) {
transaction(val[i]);
rem[i]--;
}
}
return;
}
