#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
// Structure to keep track of coupon details along with their original index
struct Coupon {
int id;
long long p;
long long t;
};
// Comparator for high-type coupons (T > 1)
// Sorts based on the key: (P * T) / (T - 1)
// We compare a < b by cross-multiplying:
// a.p * a.t * (b.t - 1) < b.p * b.t * (a.t - 1)
bool compareHigh(const Coupon& a, const Coupon& b) {
long long valA = a.p * a.t * (b.t - 1);
long long valB = b.p * b.t * (a.t - 1);
if (valA != valB) {
return valA < valB;
}
return a.p < b.p; // Tie-breaker
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
int n = P.size();
vector<Coupon> high; // Stores coupons with T > 1
vector<Coupon> ones; // Stores coupons with T = 1
for (int i = 0; i < n; ++i) {
if (T[i] == 1) {
ones.push_back({i, (long long)P[i], (long long)T[i]});
} else {
high.push_back({i, (long long)P[i], (long long)T[i]});
}
}
// 1. Sort High coupons by the optimal greedy key
sort(high.begin(), high.end(), compareHigh);
// 2. Sort T=1 coupons by Price (cheapest first)
sort(ones.begin(), ones.end(), [](const Coupon& a, const Coupon& b) {
return a.p < b.p;
});
// 3. Precompute prefix sums for T=1 coupons to allow O(log N) queries
int m = ones.size();
vector<long long> ones_pref(m + 1, 0);
for (int i = 0; i < m; ++i) {
ones_pref[i+1] = ones_pref[i] + ones[i].p;
}
int best_total_count = -1;
vector<int> best_selection;
// 4. Iterate through possible counts of High coupons.
// Due to Subtask 6 constraints, tokens decrease exponentially for T >= 2.
// We can't buy more than ~60 high-type coupons before running out of tokens (since A <= 10^9).
// We take a safe upper bound of 70 or the size of the high list.
int max_k = min((int)high.size(), 75);
for (int k = 0; k <= max_k; ++k) {
long long current_tokens = A;
bool possible = true;
vector<int> current_indices;
// Try buying the first k high coupons in sorted order
for (int i = 0; i < k; ++i) {
if (current_tokens >= high[i].p) {
current_tokens = (current_tokens - high[i].p) * high[i].t;
current_indices.push_back(high[i].id);
} else {
possible = false;
break;
}
}
if (possible) {
// We have 'current_tokens' left. Fill with cheapest T=1 coupons.
// Find the largest index in prefix sum such that sum <= current_tokens
auto it = upper_bound(ones_pref.begin(), ones_pref.end(), current_tokens);
int count_ones = (int)(it - ones_pref.begin()) - 1;
// Check if this combination is the best so far
if (k + count_ones > best_total_count) {
best_total_count = k + count_ones;
best_selection = current_indices; // First the high coupons
// Then append the ones
for (int i = 0; i < count_ones; ++i) {
best_selection.push_back(ones[i].id);
}
}
} else {
// Optimization: If we can't afford the first k (sorted by "efficiency"),
// we likely can't afford k+1. We can break here.
break;
}
}
return best_selection;
}
