#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
vector<int> max_coupons(int A_, vector<int> P, vector<int> T) {
const int n = P.size();
ll A = A_;
vector<pair<ll, int>> ones, twos;
ll sum = 0;
for (int i = 0; i < n; i++) {
if (T[i] == 1) {
ones.push_back({P[i], i});
} else {
twos.push_back({P[i], i});
}
sum += P[i];
}
sort(all(ones));
vector<ll> ps(int(ones.size()) + 1);
for (int i = 0; i < int(ones.size()); i++) {
ps[i+1] = ps[i] + ones[i].first;
}
sort(all(twos));
int best_two_cnt = 0;
auto Count = [&](ll M) -> int {
int lo = 0, hi = ones.size();
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (ps[mid] > M) {
hi = mid - 1;
} else {
lo = mid;
}
}
return lo;
};
int best_score = Count(A);
for (int i = 0; i < int(twos.size()); i++) {
if (twos[i].first> A) break;
A = (A - twos[i].first) * 2ll;
sum -= twos[i].first;
if (A >= sum) {
vector<int> res;
for (auto [x, j] : twos) {
res.push_back(j);
}
for (auto [x, j] : ones) {
res.push_back(j);
}
return res;
}
int score = Count(A);
if (i + 1 + score > best_two_cnt + best_score) {
best_two_cnt = i + 1;
best_score = score;
}
}
vector<int> res;
for (int i = 0; i < best_two_cnt; i++) {
res.push_back(twos[i].second);
}
for (int i = 0; i < best_score; i++) {
res.push_back(ones[i].second);
}
return res;
}
//#include "grader.cpp"
