#include "souvenirs.h"
#include <utility>
#include <vector>
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> known;
vector<int> times_bought;
void prv(vector<int> &v) {
for (auto i:v) {
cout << i <<" ";
}
cout << endl;
}
void update_times(vector<int> &bought_elements) {
for (int i:bought_elements) {
times_bought[i]++;
}
}
void update_times(vector<int32_t> &bought_elements) {
for (int i:bought_elements) {
times_bought[i]++;
}
}
int debug = 0;
void solve(int l, int r, int beginning_query_value, pair<vector<int32_t>, long long> res) {
assert(l<=r);
vector<int> bought(res.first.begin(), res.first.end());
int num_bought = bought.size();
int change = res.second;
if (debug) {
cout << "TESTING " << l << " " << r <<" " << beginning_query_value <<" " << num_bought <<" " << change << " " << endl;
prv(bought);
}
assert(bought[0] == l);
while (bought.size() && bought.back() > r) {
assert(known[bought.back()]!=-1);
change += known[bought.back()];
bought.pop_back();
num_bought--;
}
assert(bought.size()>0);
if (num_bought==1) {
int known_value_l = beginning_query_value - change;
assert(known[l] == -1 || known[l] == known_value_l);
known[l] = known_value_l;
if (l==r) {
return;
}
pair<vector<int32_t>, long long> next_res = transaction(known[l]-1);
vector<int> next_bought(next_res.first.begin(), next_res.first.end());
update_times(next_bought);
solve(l+1, r, known[l]-1, next_res);
return;
}
assert(l<r);
int total = beginning_query_value - change;
int average = total / num_bought;
pair<vector<int32_t>, long long> next_res = transaction(average);
vector<int> next_bought(next_res.first.begin(), next_res.first.end());
update_times(next_bought);
int new_left = next_res.first[0];
if (debug) {
cout << "debugging bifurcation " << l <<" " << new_left <<" " << r << " " << total <<" " << average <<" " << change << " " << known[l] << endl;
}
assert(new_left > l);
assert(new_left <= r);
solve(new_left, r, average, next_res);
solve(l, new_left-1, beginning_query_value, res);
}
void buy_souvenirs(int32_t N, long long P0) {
//let's say that you start by doing P[0]-1
//this guarantees that you buy the first souvenir
//then you can repeat the same process with the rest of the souvenirs
//ok so our method is
//start with P[0]-1
//then let S be the set of bought souvenirs
//take the average of S (it's known from the given info)
//transaction based on this
//then say the first souvenir bought is i, it means that from 1 to i-1 the souvenirs are more than S
//and from i to N-1 the souvenirs are less than S
//solve i to N-1 recursively with the same process
//and then solve 1 to i-1 also recursively using the info from i to N-1
//and then once we know all the values we can do the required transactions with full information
//we need to implement a function that will solve from l to r, knowing all values past r
//and then do a recursive search, which takes in a value known to be smaller than the l-1th, and larger or equal than the lth (this is how l is chosen)
//and fills in the known values for this range
//updating the times bought for each value in between
//the query limit is safe since at least one souvenir is bought on each purchase
known=vector<int>(N, -1);
times_bought=vector<int>(N, 0);
pair<vector<int32_t>, long long> first_transaction = transaction(P0-1);
vector<int> first_bought(first_transaction.first.begin(), first_transaction.first.end());
solve(1, N-1, P0-1, first_transaction);
update_times(first_bought);
for (int i=1; i<N; i++) {
//cout << i <<" " << known[i] << " " << times_bought[i] << endl;
assert(known[i]!=-1);
assert(times_bought[i]<=i);
while (times_bought[i]<i) {
pair<vector<int32_t>, long long> useless_transaction = transaction(known[i]);
update_times(useless_transaction.first);
}
}
return;
}
