#include "souvenirs.h"
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <utility>
#include <vector>
#include <iostream>
#include <unordered_set>
using namespace std;
void buy_souvenirs(int N, long long P0) {
vector<int> counts(N);
vector<long long> values(N);
unordered_set<long long> bounds;
vector<long long> cands;
vector<vector<long long>> rels;
values[0] = P0;
for (int i = 1; i < N; i++) values[i] = -1;
while (true) {
// for (long long i : values) {
// cout << i << " ";
// }
// cout << endl;
bool done = true;
for (long long i : values) {
if (i == -1) {
done = false;
break;
}
}
if (done) break;
long long bound = -1;
bool start = false;
int culprit = -1;
for (int i = N - 1; i >= 0; i--) {
if (values[i] == -1) {
if (!start) culprit = i;
start = true;
}
else if (start) {
bound = values[i];
break;
}
}
//cout << bound << " " << culprit << endl;
if (cands.size() == 0 || cands[0] > bound) {
cands.clear();
cands.push_back(bound);
}
while (cands.size() > 0) {
for (long long i : values) {
//cout << i << " ";
}
//cout << endl;
bound = cands[0];
//cout << "lol " << cands[0] << endl;
cands.erase(cands.begin());
if (bounds.find(bound) != bounds.end()) continue;
bounds.insert(bound);
pair<vector<int>, long long> x = transaction(bound - 1);
vector<long long> temp;
long long y = 0;
for (int i : x.first) {
counts[i]++;
if (values[i] == -1) {
temp.push_back(i);
}
else {
y += values[i];
}
}
long long off = 0;
for (int i : temp) {
off += temp[temp.size() - 1] - i;
}
temp.push_back(bound - 1 - x.second - y);
rels.push_back(temp);
if (temp.size() == 2) {
values[temp[0]] = temp[1];
bound = temp[1];
if (temp[0] == culprit) break;
}
else if (temp.size() == 1) {
bool aa = false;
bound = -1;
for (int j = N - 1; j >= 0; j--) {
if (values[j] == -1) aa = true;
else if (aa) {
if (values[j] < bound) {
bound = values[j];
}
}
}
if (bound == -1) break;
}
else {
bound = (temp[temp.size() - 1]) / (temp.size() - 1);
//cout << "bound " << bound << " " << off << " ! ";
//for (long long i : temp) cout << i << " ";
//cout << endl;
}
if (bound == 0) {
//cout <<" slikdjflskdjfs" << endl;
//cout << temp.size() << endl;
}
cands.push_back(bound);
}
sort(rels.begin(), rels.end(),
[](const vector<long long>& x, const vector<long long>& y) {
return x[0] > y[0];
});
bool stop = false;
while (!stop) {
stop = true;
for (int i = 0; i < rels.size(); i++) {
bool sdf = false;
int target = -1;
int count = 0;
//cout << "here ";
for (int j = 0; j < rels[i].size() - 1; j++) {
//cout << rels[i][j] << " ";
if (values[rels[i][j]] != -1) {
rels[i][rels[i].size() - 1] -= values[rels[i][j]];
rels[i].erase(rels[i].begin() + j);
j--;
}
else {
target = rels[i][j];
}
}
//cout << endl;
//cout << "target " << target;
if (rels[i].size() == 2 && target != -1) {
values[target] = rels[i][rels[i].size() - 1];
//cout << "before " << rels[i][rels[i].size() - 1] << endl;
stop = false;
rels.erase(rels.begin() + i);
i--;
}
else if (rels[i].size() == 2 && target == -1) {
rels.erase(rels.begin() + i);
i--;
}
else if (rels[i].size() == 1) {
rels.erase(rels.begin() + i);
i--;
}
}
}
for (int i = 0; i < rels.size(); i++) {
bool sdf = false;
int target = -1;
int count = 0;
//cout << "here ";
for (int j = 0; j < rels[i].size() - 1; j++) {
//cout << rels[i][j] << " ";
if (values[rels[i][j]] != -1) {
rels[i][rels[i].size() - 1] -= values[rels[i][j]];
rels[i].erase(rels[i].begin() + j);
j--;
}
else {
target = rels[i][j];
}
}
//cout << endl;
//cout << "target " << target;
if (rels[i].size() == 2 && target != -1) {
values[target] = rels[i][rels[i].size() - 1];
//cout << "before " << rels[i][rels[i].size() - 1] << endl;
stop = false;
rels.erase(rels.begin() + i);
i--;
}
else if (rels[i].size() == 2 && target == -1) {
rels.erase(rels.begin() + i);
i--;
}
else if (rels[i].size() == 1) {
rels.erase(rels.begin() + i);
i--;
}
else {
long long r = 0;
for (int j = 0; j < rels[i].size() - 1; j++) {
r += rels[i][rels[i].size() - 2] - rels[i][j];
}
long long test = (rels[i][rels[i].size() - 1]) / (rels[i].size() - 1);
//cout << "test " << test << endl;
if (bounds.find(test) == bounds.end()) {
cands.push_back(test);
sdf = true;
break;
}
}
if (sdf) {
stop = true;
break;
}
}
}
for (int i = 0; i < N; i++) {
while (counts[i] < i) {
transaction(values[i]);
counts[i]++;
}
}
return;
}
