#include "souvenirs.h"
#include <utility>
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
#define f first
#define s second
#define all(x) begin(x),end(x)
bool comp(pair<vector<int>,ll> &a, pair<vector<int>,ll> &b){
return a.f[0] > b.f[0];
}
void buy_souvenirs(int N, long long P0) {
vector<ll> P(N);
vector<int> cnt(N);
vector<int> vis(N,0);
/*
0 - haven't done
1 - not sure
2 - not sure and update
3 - sure
4 - sure and update
*/
vector<pair<vector<int>,ll>> query;
P[0] = P0;
vis[0] = 1;
bool quit = false;
while(!quit){
for(int i{};i < N-1;i++){
// for(auto k:P) cout << k << " ";
// cout << endl;
// for(auto k:vis) cout << k << " ";
// cout << endl;
if(vis[i] == 0 || vis[i] == 2 || vis[i] == 4) continue;
if(vis[i] == 3 && vis[i+1] != 0) continue;
vis[i]++;
auto ret = transaction(P[i]-1);
ll use = (P[i]-1)-ret.s;
ll over = 0;
ll mini = ret.f.back();
query.push_back({ret.f,use});
for(auto k:ret.f){
cnt[k]++;
over += k-mini;
}
if(vis[ret.f.front()] == 0){
vis[ret.f.front()] = 1;
P[ret.f.front()] = (use-over)/(ret.f.size());
break;
}
}
sort(all(query),comp);
for(auto [a,b]:query){
if(vis[a[0]] >= 3) continue;
ll val = b;
bool sure = true;
for(int i{1};i < a.size();i++){
if(vis[a[i]] < 3) {sure = false;}
val -= P[a[i]];
}
if(sure) P[a[0]] = val,vis[a[0]] = 3;
}
// for(auto k:P) cout << k << " ";
// cout << endl;
// for(auto k:vis) cout << k << " ";
// cout << endl;
quit = true;
for(int i{1};i < N;i++){
if(vis[i] < 3) quit = false;
}
}
for(int i{};i < N;i++){
while(cnt[i] < i){
transaction(P[i]);
cnt[i]++;
}
}
return;
}
