#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using pi = pair<int, int>;
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define ROF(i, a, b) for (int i = a; i >= b; i--)
#define each(a, x) for (auto &a : x)
#define all(x) (x).begin(), (x).end()
#define bg(x) (x).begin()
#define en(x) (x).end()
#define rev(x) reverse(all(x))
#define sz(x) int((x).size())
#define srt(x) sort(all(x))
#define cnt(a, x) count(all(x), a)
#define trace(x) each(a, (x)) cerr << a << " "
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
struct DSU {
int n; vi par, siz;
DSU() {};
DSU(int N) {
n = N; par.resize(n); siz.assign(n, 1);
iota(all(par), 0);
}
int find(int v) {
if (par[v] == v) return v;
return par[v] = find(par[v]);
}
void unite(int a, int b) {
a = find(a); b = find(b);
if (a != b) {
if (siz[a] < siz[b]) swap(a, b);
par[b] = a;
siz[a] += siz[b];
}
}
};
using R = pair<vi, ll>;
struct txn {ll paid; R res;};
const ll INF = 4e18;
int n;
vi bought; vl price, low, high;
R transact(ll money) {
auto res = transaction(money);
for (auto &el : res.first) {
bought[el]++;
}
// cerr << "Money: " << money << " Received: ["; for (auto &el : res.first) cerr << " " << el; cerr << " ] Change: " << res.second << "\n";
return res;
}
// find the minimum value the most expensive item must have such that the other values can satisfy the conditions and be >= paid
ll find_min(ll paid, int received) {
ll lo = 1, hi = 1e15;
while (lo < hi) {
ll mid = lo + (hi - lo) / 2;
bool check = true;
ll tl = mid; for (int i = 1; i < received; i++) {
if (mid - i <= 0) {
check = false;
break;
}
tl += (mid - i);
}
check = check && tl >= paid;
if (check) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
// o1: if we continually find the smallest possible number which p[x] must be, we eventually reach n-1
// o2: the original returned list goes down in a daisy chain and determines p[1]
bool can_resolve(vi ret) {
bool can = true;
for (auto &el : ret) can = can && price[el] != -1;
return can;
}
int id = 0;
void dfs(ll paid, int pid) { // returns
int myid = id++;
// cerr << myid << " called by " << pid << "\n";
auto r = transact(paid);
ll used = paid - r.second;
if (sz(r.first) == 1) {
price[r.first[0]] = used;
if (r.first[0] != n-1) dfs(used - 1, myid);
return;
}
while (sz(r.first) > 1) {
vi nf = {r.first[0]};
for (int i = 1; i < sz(r.first); i++) {
if (price[r.first[i]] == -1) {
nf.push_back(r.first[i]);
continue;
}
used -= price[r.first[i]];
}
r.first = nf;
if (r.first.size() == 1) break;
// cerr << myid << " open "; trace(r.first); cerr << "\n";
ll np = find_min(used, r.first.size()) - 1;
dfs(np, myid);
}
price[r.first[0]] = used;
// cerr << "Aim: " << r.first[0] + 1 << " Price: " << price[r.first[0] + 1] << "\n";
if (price[r.first[0] + 1] == -1) dfs(used - 1, myid);
return;
}
void buy_souvenirs(int N, ll P0) {
n = N;
bought.assign(n, 0); price.assign(n, -1);
price[0] = P0;
FOR(i, 1, n) {
if (price[i] != -1) continue;
// cerr << "No price for " << i << " using parent " << i - 1 << "'s price -1 of " << price[i-1] - 1 << "\n";
ll paid = price[i-1] - 1;
dfs(paid, -1);
}
FOR(i, 0, n) {
// cerr << price[i] << " ";
if (price[i] == -1) continue;
while (bought[i] < i) {
transact(price[i]);
}
}
// cerr << "\n";
}
