#include "souvenirs.h"
#include <utility>
#include <vector>
#include <iostream>
#define F first
#define S second
using namespace std;
using qr = pair<vector<int>, long long>;
vector<qr> lst;
vector<int> lst_v;
vector<int> calls;
int start_from(int n, int z) {
int k = -1;
for(int i = z ; i >= 0 ; i--) {
int f = lst_v[i];
// cout << f << " " << i << " " << z << endl;
if(f!=-1) {
k = i;
break;
}
}
return k;
}
int find_last(int P0, int n, int z, vector<int> &P) {
int e = start_from(n, z);
// cout << "H" << e << endl;
bool yay = 1;
int k = P0-1;
qr kr;
if(e != -1) {
k = lst_v[e];
// cout << e << " " << k << endl;
kr = lst[e];
// cout << "w" << kr.F.size() << endl;
// cout << lst_v[e] << endl;
yay = 0;
}
// cout << "k" << e << " " << z << " " << kr.F.size() << endl;
// cout << k << " " << z << endl;
for(int i = 0 ; ; i++) {
qr u;
if(yay) {
// cout << z << " " << i << " " << k << endl;
u = transaction(k);
}
else u = kr;
int w = k-u.S;
// k = (k-u.S)/u.F.size();
int q = 0;
for(int j = 0 ; j < (int)u.F.size() ; j++) {
// u.F[j]--;
if(yay) calls[u.F[j]]++;
q = max(q, u.F[j]);
}
// cout << q << " " << k << endl;
// if(q < lst) {
// lst = q;
// lst_v = u.F;
// // lst_m = q;
// }
lst[q] = u;
lst_v[q] = k;
for(int j = 0 ; j < u.F.size() ; j++) {
if(u.F[j] > z) w -= P[u.F[j]];
}
k = w;
// cout << kr.F.size() << " " << u.F.size() << endl;
// transaction(u.F[])
// cout << "G" << i << " " << k << " " << u.F.size() << " " << u.F[0] << " " << z << endl;
// cout << i << " " << k << endl;
// cout << "J" << i << " "<< k << " " << u.F.size() << " " << z << endl;
if(u.F.size() == 1 and u.F[0] == z) return k;
if(u.F.size() == 1) k--;
else k = k/u.F.size();
yay = 1;
}
}
void buy_souvenirs(int N, long long P0) {
// cout << find_last(N, P0) << '\n';
// qr zz = transaction(P0-1);
// lst_v = zz.F;
// lst = (P0-1)-zz.S;
vector<int> P(N);
calls.resize(N, 0);
lst.resize(N);
lst_v.resize(N);
// cout << transaction(P0-1).F[0] << endl;
for(int i = 0 ; i < N ; i++) lst_v[i] = -1;
for(int i = 0 ; i < N ; i++) lst[i].S = -1;
// P[N-1] = find_last(P0, N, N-1, P);
// for(int i = 0 ; i < N ; i++) cout << lst_v[i] << endl;
// P[N-2] = find_last(P0, N, N-2, P);
for(int i = N-1 ; i >= 1 ; i--) {
P[i] = find_last(P0, N, i, P);
}
// for(int i = 1 ; i < N ; i++) cout << P[i] << " " << calls[i] << endl;
for(int i = 1 ; i < N ; i++) {
// cout << "M" << i << " " << calls[i] << endl;
for(int j = calls[i] ; j < i ; j++) {
// cout << i << " " << P[i] << endl;
transaction(P[i]);
}
}
// lst[N-1] = zz;
// lst_v[N-1] = P0-1;
// P[0] = P0;
// cout << N << endl;
// for(int i = 0 ; i < N ; i++) {
// cout << "K" << lst_v[i] << endl;
// for(int j: lst[i].F) cout << j << " ";
// cout << endl;
// }
// for(int i = 0 ; i < N ; i++) cout << P[i] << " ";
// for(int i = 0 ; i < N ; i++) cout << P[i] << " ";
// cout << endl;
// for(int i = 0 ; i < )
// for(int i = 1 ; i <= N ; i++) {
// for(int j = 0 ; j < i-calls[i] ; j++) transaction(P[i]);
// }
return;
}
