#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define all(x) x.begin(),x.end()
vector<int> cnt;
unordered_map<int,bool> asked;
unordered_map<int,pair<vector<int>, ll>> result;
pair<vector<int>, ll> wrapper(ll S) {
if(asked[S] == true) {
return result[S];
} else {
asked[S] = true;
result[S] = transaction(S);
for(auto e : result[S].first) cnt[e]++;
return result[S];
}
}
void buy_souvenirs(int N, long long P0) {
asked.clear();
result.clear();
cnt.clear();
ofstream out("output.txt");
vector<pair<ll,vector<int>>> que;
//try to get the smallest
cnt = vector<int>(N,0);
vector<ll> know(N+1,-1);
know[0] = P0;
ll s = P0 - 1;
while(true) {
out << "callll 1 for " << s << endl;
pair<vector<int>, ll> res = wrapper(s);
ll sum = s - res.second;
if(res.first.size() == 1) {
know[res.first[0]] = sum;
out << "defaulted " << res.first[0] << " is " << sum << " after having called " << s << endl;
s = sum - 1;
if(res.first[0] == N-1) break;
} else {
s = (sum + res.f.size() - 1)/res.f.size();
que.push_back({sum, res.first});
}
}
while(que.size() > 0) {
bool changed = false;
for(int w = 0; w < (int)que.size(); w++) {
pair<ll,vector<int>> t = que[w];
for(int i = t.s.size()-1; i>=0; i--) {
if(know[t.s[i]]!=-1) {
t.f -= know[t.s[i]];
swap(t.s[i], t.s[t.s.size()-1]);
t.s.pop_back();
//t.s.erase(t.s.begin()+i);
}
}
que[w] = t;
if(que[w].s.size() == 1) {
know[que[w].s[0]] = que[w].f;
out << "added " << que[w].s[0] << " as " << que[w].f << "\n";
changed = true;
/*
if(que[w].s[0] != N-1 and know[que[w].s[0]+1] == -1) {
out << "callll 2" << endl;
pair<vector<int>, ll> res = wrapper(que[w].f-1);
ll sum = (que[w].f-1) - res.second;
que.push_back({sum, res.first});
break;
}
*/
swap(que[w], que[que.size()-1]);
que.pop_back();
w--;
} else if(que[w].s.size() == 0) {
swap(que[w], que[que.size()-1]);
que.pop_back();
w--;
}
}
bool dif = false;
for(int i = N-2; i >= 0; i--) {
//find first that has a one we know before it.
if(know[i+1] == -1 and know[i] != -1) {
pair<vector<int>, ll> res = wrapper(know[i]-1);
ll sum = (know[i]-1) - res.second;
/*
for(int j = res.first.size()-1; j>= 0; j--) {
if(know[res.first[j]] != -1) {
sum -= know[res.first[j]];
res.first.erase(res.first.begin()+j);
}
}
*/
dif = true;
que.push_back({sum, res.first});
break;
}
}
if(dif) continue;
sort(all(que));
pair<ll,vector<int>> t;
if(que.size() == 0) break;
t = que[0];
s = (t.f + t.s.size() - 1)/t.s.size();
out << "callll 3" << endl;
pair<vector<int>, ll> res = wrapper(s);
ll sum = s - res.second;
que.push_back({sum, res.first});
}
for(int i = 0; i < N; i++) out << know[i] << " ";
out << endl;
for(int i = 0; i < N; i++) {
out << "calllll 4" << endl;
while(cnt[i] < i) {transaction(know[i]); cnt[i]++;
out << "added " << i << endl;
}
}
out.flush();
out.close();
return;
}
