#include "souvenirs.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
using T = pair<vector<int>, ll>;
#define F first
#define S second
vector<ll> upd;
vector<ll> P;
map<ll, T> saved;
stack<pair<ll, T>> recent;
bool debug= false;
T qry(ll given){
if (debug) cout << "GIVING : " << given << endl;
if (saved.find(given) != saved.end()) return saved[given];
T res = transaction(given);
for (ll x : res.F) upd[x]++;
recent.push({given, res});
if (debug) {
cout << "BOUGHT : { ";
for (ll x : res.F) cout << x << " ";
cout << "}" << endl;
cout << "REMAINING : " << res.S << endl;
}
return saved[given] = res;
}
void clean(ll &given, T &res, int treshold){
vector<int> nres;
ll nvalue = 0;
for (int x: res.F) {
if (x < treshold) {
nres.push_back(x);
} else {
given -= P[x];
}
}
res.F = nres;
}
ll find_index(int idx, int N, ll given, T res){
clean(given, res, idx+1);
if (res.F.size() == 1) {
ll value = given - res.S;
if (res.F[0] == idx) return value;
else {
res = qry(value-1);
return find_index(idx, N, value-1, res);
}
}
else {
given = (given - res.S)/res.F.size();
res = qry(given);
return find_index(idx, N, given, res);
}
}
void buy_souvenirs(int N, ll P0) {
P.assign(N, -1);
P[0] = P0;
upd.assign(N, 0);
P[N-1] = find_index(N-1, N, P0-1, qry(P0-1));
for (int i=N-2;i>=1;i--) {
while(!recent.empty()){
clean(recent.top().F, recent.top().S, i+1);
if (recent.top().S.F.empty()) recent.pop();
else break;
}
P[i] = find_index(i, N, recent.top().F, recent.top().S);
}
for (int i=0;i<N;i++) {
while(upd[i] < i){
upd[i]++;
transaction(P[i]);
}
}
}
