#include "festival.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define ll long long int
const int N = 2e5+100;
void apply(ll &C, ll p, ll t){
if((C-p) > 1e17){
return;
}
C = (C-p)*t;
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
int n = (int) P.size();
vector<array<ll, 3>> B;
for(int i = 0; i < n; ++i){
B.pb({P[i], T[i], i});
}
function<int(ll, ll ,ll)> F = [&](ll p, ll t, ll C){
return (t)*C - p*t;
};
vi RES;
ll CC = A;
while(B.size()){
if(CC > 1e17){
for(auto x: B){
RES.pb(x[2]);
}
break;
}
sort(all(B), [&](const array<ll, 3> &x, const array<ll, 3> &y){
if(x[0] > CC) return false;
if(y[0] > CC) return true;
if(x[1] == 1 && y[1] == 1){
return x[0] < y[0];
}
if(x[1] == 1) return false;
if(y[1] == 1) return true;
// bool take1 = (CC-x[0])*x[1] >= y[0];
// bool take2 = (CC-y[0])*y[1] >= x[0];
// if(take1 && take2){
// ll c = ((CC-x[0])*x[1] - y[0]) * y[1];
// ll d = ((CC-y[0])*y[1] - x[0]) * x[1];
double c = x[0]*x[1] / (double)(y[0]*y[1]);
double d = (x[1]-1) / (double)(y[1]-1);
return c>d;
// }
assert(false);
// if(take1) return true;
// if(take2) return false;
return F(x[0], x[1], CC) > F(y[0], y[1], CC);
});
// for(auto [x, y, z]: B) cerr << x << ' ' << y << ' ' << z << '\n';
for(int j = 0; j < n; ++j){
RES.pb(B[j][2]);
}
break;
cerr << '\n';
cerr << '\n';
}
return RES;
vector<pair<ll, int>> X, Y;
vector<ll> pref;
ll C = A;
for(int i = 0; i < n; ++i){
if(T[i] == 1){
X.pb({P[i], i});
}else{
Y.pb({P[i], i});
}
}
sort(all(X));
sort(all(Y));
pref.resize(X.size()+1);
pref[0] = 0;
for(int i = 1; i <= X.size(); ++i) pref[i] = pref[i - 1] + X[i - 1].ff;
function<int(ll)> get = [&](ll sum){
return lower_bound(all(pref), sum) - pref.begin();
};
int best = 0, cnt = get(C);
for(int i = 0; i < Y.size(); ++i){
if(C < Y[i].ff){
break;
}
apply(C, Y[i].ff, 2);
int num = i + 1 + get(C);
if(num > cnt){
cnt = num;
best = i + 1;
}
}
vi res;
C = A;
for(int j = 0; j < best; ++j){
res.pb(Y[j].ss);
apply(C, Y[j].ff, 2);
}
for(int j = 0; j < X.size(); ++j){
if(X[j].ff <= C){
C -= X[j].ff;
res.pb(X[j].ss);
}
}
return res;
}
