#include "souvenirs.h"
#include <utility>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
pair<vector<int>,ll> convert(pair<vector<int>,ll> query, int N){
vector<int> temp(N,0);
for (int i=0;i<query.first.size();i++){
temp[query.first[i]] = 1;
}
return {temp,query.second};
}
void buy_souvenirs(int N, long long p0){
ll bought2[N+5];
memset(bought2,0,sizeof(bought2));
ll price[N+5];
memset(price,-1,sizeof(price));
price[0] = p0;
ll mn = p0-1;
pair<vector<int>,long long> query = transaction(mn);
query = convert(query,N);
for (int i=0;i<query.first.size();i++){
bought2[i] += query.first[i];
}
priority_queue<pair<vector<int>,pair<ll,ll>>,vector<pair<vector<int>,pair<ll,ll>>>,greater<pair<vector<int>,pair<ll,ll>>>> pq;
pq.push({query.first,{query.second,mn}});
int back = N-1;
while (!pq.empty()){
ll next = -1;
pair<vector<int>,pair<ll,ll>> query = pq.top();
//pq.pop();
vector<int> items;
int ind = -1;
ll total = 0;
for (int i=0;i<N;i++){
if (query.first[i]==1 && price[i]==-1) {
items.push_back(i);
ind = max(ind,i);
}
else if (query.first[i]==1 && price[i]!=-1) total += price[i];
}
if (items.size()==0){
pq.pop();
}
else if (items.size()==1){
pq.pop();
price[ind] = query.second.second - query.second.first - total;
next = price[ind] - 1;
while (back>=0 && price[back]!=-1){
back--;
}
}
else{
next = (query.second.second - query.second.first - total)/items.size();
}
if (ind<=back && items.size()>0){
pair<vector<int>,ll> q = transaction(next);
q = convert(q,N);
for (int i=0;i<q.first.size();i++){
bought2[i] += q.first[i];
}
if (next==-1) break;
pq.push({q.first,{q.second,next}});
}
items.clear();
}
//for (int i=0;i<N;i++) cout << price[i] << ' ';
//cout << "\n";
// for (int i=0;i<N;i++){
// cout << bought[i] << ' ';
// // if (bought[i]>i){
// // cout << "too many " << bought[i] << ' ' << i << "\n";
// // }
// }
// cout << "\n";
for (int i=0;i<N;i++){
for (int j=0;j<i-bought2[i];j++){
transaction(price[i]);
}
}
}
