#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
struct Entry {
pair<vector<int>, long long> ans;
int count;
long long price;
};
void buy_souvenirs(int N, long long P0) {
// std::pair<std::vector<int>, long long> res = transaction(3);
vector<long long> res(N);
vector<int> curr(N);
res[0] = P0;
int cnt = 1;
stack<Entry> st;
long long price = res[0]-1;
while (cnt < N) {
pair<vector<int>, long long> ans = transaction(price);
int count = ans.first.size();
for (int i = 0; i < count; i++) {
curr[ans.first[i]]++;
}
int newCount = count, lastN = -1;
long long tmpSum2 = 0;
for (int i = 0; i < count; i++) {
if (res[ans.first[i]] == 0)
lastN = ans.first[i];
else {
tmpSum2 += res[ans.first[i]];
newCount--;
}
}
cout << price << " " << count << " " << newCount << endl;
if (newCount <= 1) {
if (newCount == 1) {
res[lastN] = price - ans.second-tmpSum2;
cnt++;
}
long long down = -1;
for (int i = ans.first[0]+1; i < N; i++) {
if (res[i] == 0) {
down = res[i-1]-1;
break;
}
}
// cout << res[ans.first[0]] << endl;
// cout << tmpSum2 << " " << ans.second << endl;
if (down != -1) price = down;
else {
bool found = false;
while (st.size() && !found) {
Entry entry = st.top(); st.pop();
long long tmpCount = 0, tmpSum = 0;
for (int i = 0; i < entry.count; i++) {
// if (entry.ans.first[i] == 0) continue;
if (res[entry.ans.first[i]] != 0) {
tmpSum += res[entry.ans.first[i]];
continue;
}
tmpCount++;
}
// cout << "HI2: " << entry.price-entry.ans.second-tmpSum << endl;
if (tmpCount == 1) {
for (int i = 0; i < entry.count; i++) {
if (res[entry.ans.first[i]] != 0) continue;
res[entry.ans.first[i]] = entry.price-entry.ans.second-tmpSum;
cnt++;
}
}
long long tmpPrice = entry.price-entry.ans.second;
int idx = entry.count-1;
int newCount2 = entry.count;
for (int i = N-1; i >= 0 && idx >= 0; i--) {
// if (entry.ans.first[idx] != i) break;
// if (res[i] == 0) break;
if (res[entry.ans.first[idx]] != 0) newCount2--;
tmpPrice -= res[entry.ans.first[idx]];
idx--;
}
for (int i = N-2; i >= entry.ans.first[0]; i--) {
if (res[i+1] == 0 && res[i] != 0) {
price = res[i]-1;
found = true;
st.push(entry);
break;
}
}
if (tmpPrice != 0) {
price = tmpPrice/newCount2;
st.push(entry);
found = true;
// cout << "HI: " << newCount2 << endl;
// for (int i = 0; i < N; i++) cout << res[i] << " ";
// cout << endl;
}
}
if (!found) {
for (int i = N-2; i >= 0; i--) {
if (res[i+1] == 0 && res[i] != 0) {
price = res[i]-1;
break;
}
}
}
}
} else {
if (newCount > 1) st.push({ans, count, price});
// cout << price - ans.second-tmpSum2)/ew << endl;
price = (price - ans.second-tmpSum2)/newCount;
}
// cout << res[0] << " " << res[1] << " " << res[2] << endl;
}
for (int i = 0; i < N; i++) {
while (curr[i] < i) {
curr[i]++;
transaction(res[i]);
}
}
return;
}
