#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(); if (crt[fval]) { //cout << "TERMINATE\n"; exit(0); } 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] && (!crt[x+1])&&(!cslv[x+1])) { //cout << "loop2 at x="<<x<<"\n"; create2(cst[x]-1); //exit(0); f1 = 1; break; } } 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); break; } } } upbuy(); }