#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;
map<int,bool> asked;
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]];
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});
}
que.erase(que.begin()+w);
w--;
} else if(que[w].s.size() == 0) {
que.erase(que.begin()+w);
w--;
}
}
sort(all(que));
//the first one has a subtask
pair<ll,vector<int>> t;
if(que.size() == 0) break;
t = que[0];
s = (t.f + t.s.size() - 1)/t.s.size();
//cout << "debug ";
for(auto e : t.s) //cout << e << " ";
//cout << " total " << t.f << "\n";
pair<vector<int>, ll> res = wrapper(s);
ll sum = s - res.second;
que.push_back({sum, res.first});
/*
if(res.first.size() == 1) {
know[res.first[0]] = sum;
if(res.first[0] != N-1) {
pair<vector<int>, ll> res2 = wrapper(sum - 1);
ll sum2 = (sum - 1) - res2.second;
que.push_back({sum2, res2.first});
}
} else {
que.push_back({sum, res.first});
}
*/
}
}
//cout << "que: \n";
for(auto a : que) {
//for(auto b : a.s) //cout << b << " ";
//cout << "\n";
}
//cout << "prices: \n";
for(int i = 0; i < N; i++) //cout << i << " is " << know[i] << endl;
for(int i = 0; i < N; i++) {
while(cnt[i] < i) {transaction(know[i]); cnt[i]++;}
}
return;
}
