#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define all(x) x.begin(),x.end()
vector<int> cnt;
unordered_map<int,bool> asked;
unordered_map<int,pair<vector<int>, ll>> result;
pair<vector<int>, ll> wrapper(ll S) {
if(asked[S] == true) {
return result[S];
} else {
asked[S] = true;
result[S] = transaction(S);
for(auto e : result[S].first) cnt[e]++;
return result[S];
}
}
void buy_souvenirs(int N, long long P0) {
vector<pair<ll,vector<int>>> que;
//try to get the smallest
cnt = vector<int>(N,0);
vector<ll> know(N+1,-1);
know[0] = P0;
ll s = P0 - 1;
while(true) {
pair<vector<int>, ll> res = wrapper(s);
ll sum = s - res.second;
if(res.first.size() == 1) {
s = sum - 1;
know[res.first[0]] = sum;
if(res.first[0] == N-1) break;
} else {
s = (sum + res.f.size() - 1)/res.f.size();
que.push_back({sum, res.first});
}
}
while(que.size() > 0) {
for(int w = 0; w < (int)que.size(); w++) {
pair<ll,vector<int>> t = que[w];
for(int i = t.s.size()-1; i>=0; i--) {
if(know[t.s[i]]!=-1) {
t.f -= know[t.s[i]];
swap(t.s[i], t.s[t.s.size()-1]);
t.s.pop_back();
//t.s.erase(t.s.begin()+i);
}
}
que[w] = t;
if(que[w].s.size() == 1) {
know[que[w].s[0]] = que[w].f;
//cout << "added " << que[w].s[0] << " as " << que[w].f << "\n";
if(que[w].s[0] != N-1 and know[que[w].s[0]+1] == -1) {
pair<vector<int>, ll> res = wrapper(que[w].f-1);
ll sum = (que[w].f-1) - res.second;
que.push_back({sum, res.first});
}
swap(que[w], que[que.size()-1]);
que.pop_back();
w--;
} else if(que[w].s.size() == 0) {
swap(que[w], que[que.size()-1]);
que.pop_back();
w--;
}
}
sort(all(que));
pair<ll,vector<int>> t;
if(que.size() == 0) break;
t = que[0];
s = (t.f + t.s.size() - 1)/t.s.size();
pair<vector<int>, ll> res = wrapper(s);
ll sum = s - res.second;
que.push_back({sum, res.first});
}
for(int i = 0; i < N; i++) {
while(cnt[i] < i) {transaction(know[i]); cnt[i]++;}
}
return;
}
