#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
ll N;
vector<bool> crt; //created with this as endpoint?
vector<set<int>> cseq; //created sequence
vector<ll> csum; //created sequence: total sum of values
vector<ll> nbt; //number already bought
vector<bool> cslv; //cost solved?
vector<ll> cst; //cost value
ll ceil(ll a, ll b) {
return ((a+b-1)/b);
}
void create(ll Pc) {
auto A0 = transaction(Pc);
ll Tc = Pc - (A0.second); //total cost
vector<int> entr = A0.first;
ll fval = entr[0];
ll M = entr.size();
ll Pn = ceil(Tc+(M*(M-1))/2,M)-1;
assert(!crt[fval]);
crt[fval]=1;
csum[fval]=Tc;
for (ll x: entr) {
nbt[x]++;
cseq[fval].insert(x);
}
if (fval!=(N-1)) {
create(Pn);
}
}
void create2(ll Pc) {
//cout << "create2 at Pc="<<Pc<<"\n";
auto A0 = transaction(Pc);
ll Tc = Pc - (A0.second); //total cost
vector<int> entr = A0.first;
ll fval = entr[0];
ll M = entr.size();
assert(!crt[fval]);
crt[fval]=1;
for (ll x: entr) {
nbt[x]++;
if (cslv[x]) {
Tc -= cst[x];
} else {
cseq[fval].insert(x);
}
}
csum[fval]=Tc;
}
bool reduce() {
for (ll t=(N-1);t>=1;t--) {
if (t==2) {
//cout << "t=2: "<<cslv[t] <<" "<<crt[t] <<" "<<cseq[t].size() <<"\n";
}
if ((!cslv[t]) && (crt[t]) && (cseq[t].size()==1)) {
cslv[t]=1;
cst[t]=csum[t];
//cout << "elim t="<<t<<"\n";
for (ll s=1;s<t;s++) {
if (cseq[s].find(t)!=cseq[s].end()) {
cseq[s].erase(cseq[s].find(t));
csum[s]-=cst[t];
}
}
return 1;
}
}
return 0;
}
void rreduce() {
while (1) {
if (!reduce()) {
return;
}
}
}
bool aslv() {
for (ll x=1;x<N;x++) {
if (!cslv[x]) {
return 0;
}
}
return 1;
}
void upbuy() {
for (ll x=1;x<N;x++) {
for (ll T=0;T<(x-nbt[x]);T++) {
transaction(cst[x]);
}
}
}
void buy_souvenirs(int _N, long long P0) {
N = _N;
crt.clear(); cseq.clear(); csum.clear(); nbt.clear(); cslv.clear(); cst.clear();
crt = vector<bool>(N,0);
cslv = vector<bool>(N,0);
cseq = vector<set<int>>(N);
csum = vector<ll>(N,0);
nbt = vector<ll>(N,0);
cst = vector<ll>(N,0);
create(P0-1);
rreduce();
ll CLOCK = 0;
while (!aslv()) {
//cout << "ncyc\n";
rreduce();
if (aslv()) {
break;
}
bool f1 = 0;
for (ll x=(N-2);x>=1;x--) {
if (cslv[x] && (!cslv[x+1])) {
//cout << "loop2 at x="<<x<<"\n";
create2(cst[x]-1);
//exit(0);
f1 = 1;
continue;
}
}
if (f1) {
continue;
}
for (ll x=(N-1);x>=1;x--) {
if ((!cslv[x]) && (crt[x])) {
//cout << "loop3 at x="<<x<<"\n";
ll K = csum[x];
ll M = cseq[x].size();
//cout << "K,M="<<K<<","<<M<<"\n";
assert(M!=0);
create2(ceil(K+(M*(M-1))/2,M)-1);
continue;
}
}
}
upbuy();
}
