#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct rango{
ll L, R;
rango(ll a, ll b) {
L = a;
R = b;
}
};
rango merger(rango a, rango b) {
rango ans(0,0);
ans.L = min(a.L,b.L);
ans.R = max(a.R,b.R);
return ans;
}
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
ll n = w.size();
ll in[n],L=0,R=n-1,idx=0;
for (int i=0;i<n;i++) in[i] = i;
sort(in,in+n, [&] (ll a, ll b) {return w[a] < w[b];});
vector <int> ans;
vector <rango> ran;
ran.push_back(rango(l,u));
for (int i=0;i<n;i++) {
if (i%2==0) {
ran.push_back(rango(ran[ran.size()-1].L-w[in[L]],ran[ran.size()-1].R-w[in[L]]));
for (int j=ran.size()-1;j>idx;j--) ran[j] = merger(ran[j],rango(ran[j-1].L-w[in[L]],ran[j-1].R-w[in[L]]));
idx++;
L++;
}
else {
ran.push_back(rango(ran[ran.size()-1].L-w[in[R]],ran[ran.size()-1].R-w[in[R]]));
for (int j=ran.size()-1;j>idx;j--) ran[j] = merger(ran[j],rango(ran[j-1].L-w[in[R]],ran[j-1].R-w[in[R]]));
idx++;
R--;
}
if (ran[ran.size()-1].L <= 0 && ran[ran.size()-1].R >= 0) {
L--;
R++;
while (L>0) {
ans.push_back(in[L]);
L--;
}
while (R<n) {
ans.push_back(in[R]);
R++;
}
}
}
return ans;
}
