#include "souvenirs.h"
#include <utility>
#include <vector>
using namespace std;
void buy_souvenirs(int N, long long P0) {
vector<int> counts(N);
vector<long long> values(N);
values[0] = P0;
for (int i = 1; i < N; i++) values[i] = -1;
while (true) {
bool done = true;
for (long long i : values) {
if (i == -1) {
done = false;
break;
}
}
if (done) break;
long long bound = -1;
bool start = false;
for (int i = N - 1; i >= 0; i--) {
if (values[i] == -1) start = true;
else if (start) {
bound = values[i];
break;
}
}
vector<vector<long long>> rels;
while (true) {
pair<vector<int>, long long> x = transaction(bound - 1);
vector<long long> temp;
long long off = 0;
for (int i : x.first) {
counts[i]++;
off += x.first[x.first.size() - 1] - i;
temp.push_back(i);
}
temp.push_back(bound - 1 - x.second);
rels.push_back(temp);
if (temp.size() == 2) {
values[temp[0]] = temp[1];
bound = temp[1];
if (temp[0] == N - 1) break;
}
else {
bound = (temp[temp.size() - 1] - off) / x.first.size() + 1;
}
}
bool stop = false;
while (!stop) {
stop = true;
for (int i = 0; i < rels.size(); i++) {
int count = 0;
int target = -1;
long long sum = 0;
for (int j = 0; j < rels[i].size() - 1; j++) {
if (values[rels[i][j]] != -1) {
count++;
sum += values[rels[i][j]];
}
else {
target = rels[i][j];
}
}
if (count == rels[i].size() - 2) {
values[target] = rels[i][rels[i].size() - 1] - sum;
stop = false;
rels.erase(rels.begin() + i);
i--;
}
else if (count == rels[i].size() - 1) {
rels.erase(rels.begin() + i);
i--;
}
}
}
}
for (int i = 0; i < N; i++) {
while (counts[i] < i) {
transaction(values[i]);
counts[i]++;
}
}
return;
}
