#include <bits/stdc++.h>
#include "molecules.h"
using namespace std;
vector<int> find_subset(int l, int u, vector<int> w){
int n = w.size(), sum = 0;
set<pair<int, int>> taken, free;
// sort(w.begin(), w.end());
for(int i = 0; i < n; i++){
if(sum < l){
sum += w[i];
taken.insert({w[i], i});
}
else{
free.insert({w[i], i});
}
}
bool flag = false;
while(!(sum >= l && sum <= u)){
if(sum > u){
if(flag) return vector<int>{};
if(free.empty() || free.begin()->first - prev(taken.end())->first >= 0){
sum -= prev(taken.end())->first;
free.insert(*prev(taken.end()));
taken.erase(prev(taken.end()));
}
else{
sum += free.begin()->first - prev(taken.end())->first;
pair<int, int> p = *free.begin(), p2 = *prev(taken.end());
free.erase(p), taken.erase(p2);
free.insert(p2), taken.insert(p);
}
}
else if(sum < l){
if(free.empty() || prev(free.end())->first - taken.begin()->first <= 0){
return vector<int>{};
}
else{
flag = true;
sum += prev(free.end())->first - taken.begin()->first;
pair<int, int> p = *prev(free.end()), p2 = *taken.begin();
free.erase(p), taken.erase(p2);
free.insert(p2), taken.insert(p);
}
}
}
vector<int> ans;
for(auto p : taken) ans.push_back(p.second);
long long actsum = 0;
for(auto i : ans) actsum += w[i];
assert(actsum >= l && actsum <= u);
return ans;
}
