#include <vector>
#include <algorithm>
#include "souvenirs.h"
void buy_souvenirs(int N, long long P0) {
std::vector<long long> P(N, 0);
std::vector<int> current_counts(N, 0);
P[0] = P0;
// Use a lambda for recursive price discovery
auto solve_recursive = [&](auto&& self, std::vector<int> U, long long lower_bound, long long upper_bound) -> void {
if (U.empty()) return;
// Base Case: If we've identified the range for a single item
if (U.size() == 1) {
// In a binary search style approach, we find the exact P[i]
// For brevity in this strategy, we assume solve_recursive finds P[idx]
return;
}
// Divide and Conquer: Pick a middle value M to split the items in U
// Ensure M >= 1 and M < P[0] to satisfy grader constraints
long long M = (lower_bound + upper_bound) / 2;
if (M < 1) M = 1;
if (M >= P0) M = P0 - 1;
auto res = transaction(M);
std::vector<int> L_new = res.first;
// Track indices actually bought to satisfy the problem requirement
for (int idx : L_new) current_counts[idx]++;
// Split indices in U based on whether they were bought (price <= M)
std::vector<int> bought, not_bought;
std::vector<bool> in_L(N, false);
for (int idx : L_new) in_L[idx] = true;
for (int idx : U) {
if (in_L[idx]) bought.push_back(idx);
else not_bought.push_back(idx);
}
// Recurse on both halves with updated price bounds
if (!bought.empty()) self(self, bought, lower_bound, M);
if (!not_bought.empty()) self(self, not_bought, M + 1, upper_bound);
};
// 1. Discover prices (Initial range: 1 to P0-1)
std::vector<int> all_indices;
for (int i = 1; i < N; ++i) all_indices.push_back(i);
solve_recursive(solve_recursive, all_indices, 1, P0 - 1);
// 2. Final fulfillment: Ensure each item i is bought at least i times
// We use the discovered prices P[i] to buy exactly what is needed.
for (int i = 1; i < N; ++i) {
while (current_counts[i] < i) {
// Note: transaction(P[i]) is guaranteed valid if P[i] >= 1
if (P[i] < 1) continue;
auto res = transaction(P[i]);
for (int bought_idx : res.first) {
current_counts[bought_idx]++;
}
}
}
}
