#include <bits/stdc++.h>
struct item {
int64_t i, p, t;
};
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
const int n = P.size();
std::vector<item> a(n);
for (int i = 0; i < n; ++i) {
a[i] = {i, P[i], T[i]};
}
std::sort(a.begin(), a.end(), [&](item i, item j) {
if (i.t != j.t) {
return i.t > j.t;
}
return i.p < j.p;
});
int _n = n;
for (int i = 0; i < n; ++i) {
if (a[i].t == 1) {
_n = i;
break;
}
}
std::vector<int> ansl, ansr;
int64_t max = 0;
const int lg = 28;
// for each n, fix how many chosen in left, right
for (int i = 0; i <= std::min(lg, n); ++i) {
int64_t vall = 0, valr = 0;
std::vector<int> cur_ansl, cur_ansr;
int ptr1 = 0, ptr2 = _n;
for (int size = i; size <= n; ++size) {
for (; ptr1 < i and ptr1 < _n; ++ptr1) {
cur_ansl.push_back(ptr1);
vall = a[ptr1].t * (vall - a[ptr1].p);
}
for (; ptr2 - _n < size - i and ptr2 < n; ++ptr2) {
cur_ansr.push_back(ptr2);
valr = a[ptr2].t * (valr - a[ptr2].p);
}
int64_t cur = (int64_t(A) << i) + (vall + valr);
if (cur > 0 and cur_ansl.size() + cur_ansr.size() > max) {
max = cur_ansl.size() + cur_ansr.size();
ansl = cur_ansl, ansr = cur_ansr;
}
}
}
std::vector<int> ans;
for (int &i : ansl) {
ans.push_back(i);
}
for (int &i : ansr) {
ans.push_back(i);
}
return ans;
}
