#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
#include "molecules.h"
vector<int> find_subset(int L, int H, vector<int> w) {
int N = w.size();
vector<ii> all(N);
for (int i = 0; i < N; i++) {
all[i].fi = w[i];
all[i].se = i;
}
sort(all.begin(), all.end());
/* cout<<"all: ";
for (int i = 0; i < N; i++) {
cout<<"("<<all[i].fi<<", "<<all[i].se<<"); ";
}
cout<<endl;*/
// consider all prefix left and right sums
set<ii> preR;
preR.insert({0, N});
ll curr = 0; // current sum
for (int i = N - 1; i >= 0; i--) {
curr += all[i].fi;
preR.insert({curr, i});
}
/* cout<<"preR: ";
for (ii p : preR)
cout<<"("<<p.fi<<", "<<p.se<<"); ";
cout<<endl;*/
curr = 0; // current sum
for (int i = 0; i <= N; i++) { // take up to i, exclusive
// cout<<i<<": "<<curr<<endl;
ii lb = {L - curr, -1};
ii ub = {H - curr, 1e9};
// cout<<"lb, ub: "<<lb.fi<<" "<<lb.se<<" "<<ub.fi<<" "<<ub.se<<endl;
// if any in [lb, ub] in preR, works
if (preR.lower_bound(lb) != preR.lower_bound(ub)) { // found
auto it = preR.lower_bound(lb);
ii res = *it;
int rv = res.se;
vector<int> ans;
for (int j = 0; j < i; j++) {
ans.pb(all[j].se);
}
for (int j = rv; j < N; j++) {
ans.pb(all[j].se);
}
return ans;
}
preR.erase(*(--preR.end()));
curr += all[i].fi;
}
return {};
}
