#include "souvenirs.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define fi first
#define se second
vector<ll>p;
vector<int>cnt;
int Refresh(ll &sum,vector<int>&cur)
{
int old=cur.size();
set<int>s;
for(int v:cur)
{
s.insert(v);
}
for(int v:cur)
{
if(p[v]!=-1)
{
sum-=p[v];
s.erase(v);
}
}
cur.clear();
for(int v:s)cur.push_back(v);
return (old>cur.size());
}
void dfs(int u,ll sum,vector<int>cur)
{
if(cur.size()==1)
{
p[u]=sum;
return ;
}
if(p[u]!=-1)assert(0);
Refresh(sum,cur);
while(true)
{
if(cur.size()==1)
{
p[u]=sum;
break;
}
ll nxt_sum=sum/cur.size();
for(int i=cur.back(); i>=u; i--)
{
if(p[i]!=-1)
{
nxt_sum=p[i]-1;
break;
}
}
pair<vi,ll>nxt=transaction(nxt_sum);
for(int v:nxt.fi)cnt[v]++;
nxt_sum-=nxt.se;
dfs(nxt.fi[0],nxt_sum,nxt.fi);
Refresh(sum,cur);
}
}
void buy_souvenirs(int n,ll p0)
{
p=vector<ll>(n,-1);
p[0]=p0;
cnt=vector<int>(n,0);
for(int i=1; i<n; i++)
{
if(p[i]==-1)
{
ll nxt_sum=p[i-1]-1;
pair<vi,ll>nxt=transaction(nxt_sum);
for(int v:nxt.fi)cnt[v]++;
nxt_sum-=nxt.se;
Refresh(nxt_sum,nxt.fi);
dfs(nxt.fi[0],nxt_sum,nxt.fi);
}
}
for(int i=1; i<n; i++)
{
while(cnt[i]<i)
{
transaction(p[i]);
cnt[i]++;
}
}
}
