#include "molecules.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
constexpr int maxn = 2e5 + 5;
ll pref[maxn] = { 0 }, suff[maxn] = { 0 };
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
int n = w.size();
vector<pii> v(n);
for (int i = 0; i < n; i++) v[i].first = w[i], v[i].second = i;
sort(v.begin(), v.end());
pref[0] = v[0].first;
for (int i = 1; i < n; i++) pref[i] = pref[i - 1] + v[i].first;
suff[0] = v.back().first;
for (int i = 1; i < n; i++) suff[i] = suff[i - 1] + v[n - i - 1].first;
int len = -1;
for (int i = 0; i < n; i++)
{
if (pref[i] <= u && suff[i] >= l)
{
len = i + 1;
break;
}
}
if (len == -1)
{
// Impossible
return vector <int>();
}
ll val = suff[len - 1];
int i = 0;
while (val > u)
{
val += v[i].first - v[n - i - 1].first;
swap(v[i], v[n - i - 1]);
i++;
}
vector <int> output(len);
for (int &i : output)
{
i = v.back().second;
v.pop_back();
}
return output;
}
