#include <bits/stdc++.h>
#include "souvenirs.h"
#define MULTITEST false
using namespace std;
vector<bool> solved;
vector<long long> values;
int N;
struct Pivot {
long long sum = 0;
vector<int> indices;
long long remainder () {
long long nsum = sum;
int ncount = indices.size();
for (int i : indices) {
if (solved[i]) {
ncount --;
nsum += values[i];
}
}
return nsum / ncount;
}
pair<int, long long> pivot_property () {
long long value = sum;
int index = indices[0];
for (int i : indices) {
value -= values[i];
}
return { index, value };
}
bool pivot_solved () {
int scount = 1;
for (int i : indices) {
if (solved[i]) {
scount ++;
}
}
return scount == indices.size();
}
};
vector<int> built_count;
Pivot create_pivot (long long M) {
const auto res = transaction(M);
Pivot p;
p.sum = M - res.second;
p.indices = res.first;
for (int i : p.indices)
built_count[i] ++;
return p;
}
void buy_souvenirs (int _N, long long _P0) {
N = _N; values.resize(N);
solved.resize(N);
built_count.resize(N);
solved[0] = true;
values[0] = _P0;
vector<Pivot> pivots;
pivots.push_back({ -1, { 0 } });
while (pivots.size() != 0) {
Pivot &p = pivots.back();
if (p.sum != -1 && p.pivot_solved()) {
pair<int, long long> res = p.pivot_property();
int p_id = res.first;
long long p_vl = res.second;
solved[p_id] = true;
values[p_id] = p_vl;
pivots.pop_back();
continue ;
}
int ppos = p.indices[0];
bool found_better = false;
for (int j = N - 2; j >= ppos; j --) {
if (solved[j] && !solved[j + 1]) {
pivots.push_back(create_pivot(values[j] - 1));
found_better = true;
break ;
}
}
if (found_better) continue ;
if (p.sum == -1) break ;
pivots.push_back(create_pivot(p.remainder()));
}
for (int i = 0; i < N; i ++) {
while (built_count[i] < i) {
built_count[i] ++;
transaction(values[i]);
}
}
}
