#include "souvenirs.h"
#include <utility>
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
using ll = unsigned long long;
#define f first
#define s second
#define all(x) begin(x),end(x)
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 - sure
*/
vector<pair<vector<int>,ll>> query;
P[0] = P0;
vis[0] = 2;
bool quit = false;
auto bound = [&](pair<vector<int>,ll> ret){
int si = ret.f.size();
ll use = ret.s;
ll over = 0;
ll mini = ret.f[si-1];
for(int i{si-1};i >= 0;i--){
if(vis[ret.f[i]] == 2) mini = ret.f[i];
else break;
}
//cout << mini << endl;
ll div = 0;
for(auto k:ret.f){
if(vis[k] == 2) use -= P[k];
else div++,over += k-mini;
//cout << over << endl;
}
//cout << div << " " << over << endl;
if(div == 1) vis[ret.f[0]] = 2,P[ret.f[0]] = use;
else if(div >= 1) vis[ret.f[0]] = 1,P[ret.f[0]] = (use-over)/div;
};
while(!quit){
bool lower = false;
for(int i{N-1};i >= 0;i--){
if(vis[i] != 0 && lower){
auto ret = transaction(P[i]-1);
ll use = P[i]-1-ret.s;
// cout << "Query -> " << use << " : ";
for(auto k:ret.f) cnt[k]++;
//cout << endl;
bound({ret.f,use});
query.push_back({ret.f,use});
break;
}
else if(vis[i] == 0) lower = true;
}
for(int i{};i < N;i++){
for(auto ret:query){
if(vis[ret.f[0]] == 2) continue;
bound(ret);
}
}
// 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] < 2) quit = false;
}
}
for(int i{};i < N;i++){
while(cnt[i] < i){
transaction(P[i]);
cnt[i]++;
}
}
return;
}
