#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
int N = P.size();
vector<int> o, t;
for (int i = 0; i < N; i++) {
if (T[i] == 1) o.emplace_back(i);
else t.emplace_back(i);
}
sort(o.begin(), o.end(), [&](int i, int j) {
return P[i] < P[j];
});
vector<ld> pref;
for (auto &i : o) {
if (pref.empty()) pref.emplace_back(P[i]);
else pref.emplace_back(pref.back() + P[i]);
}
sort(t.begin(), t.end(), [&](int i, int j) {
return P[i] < P[j];
});
int M = t.size();
// we take some prefix of o and some prefix of t
ld have = A;
int best = upper_bound(pref.begin(), pref.end(), have) - pref.begin() - 1;
int ind = -1, oth = upper_bound(pref.begin(), pref.end(), have) - pref.begin();
cerr << best sp o.size() sp t.size() << endl;
for (int i = 0; i < M; i++) {
if (have < P[t[i]]) break;
have = ld(2) * (have - P[t[i]]);
if (i >= 32) cerr << have sp P[t[i]] << endl;
if (have < 0) break;
int cand = i + upper_bound(pref.begin(), pref.end(), have) - pref.begin() - 1;
if (cand > best) {
best = cand;
ind = i;
oth = upper_bound(pref.begin(), pref.end(), have) - pref.begin();
}
}
vector<int> ans;
if (ind == -1) {
for (int i = 0; i < oth; i++) {
ans.emplace_back(o[i]);
}
} else {
for (int i = 0; i <= ind; i++) {
ans.emplace_back(t[i]);
}
for (int i = 0; i < oth; i++) {
ans.emplace_back(o[i]);
}
}
return ans;
}
