#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> find_subset(int l, int u, vector<int> w) {
vector<pair<int,int>> arr;
int n = w.size(), temp = 0;
for (int i=0;i<n;i++) {
arr.push_back(make_pair(w[i],i));
}
sort(arr.begin(), arr.end());
vector<int> prefix(n);
for (int i=0;i<n;i++) {
temp += arr[i].first;
prefix[i] = temp;
}
vector<int> ansarr;
if (n == 1) {
if (l <= w[0] && w[0] <= u) {
ansarr.push_back(0);
return ansarr;
} else {
return ansarr;
}
}
int bottom = 0, top = n-1, middle, base;
while (bottom + 1 < top) {
middle = (bottom + top)/2;
if (prefix[middle] <= l) {
bottom = middle;
} else if (prefix[middle] <= u) {
for (int i=0;i<middle+1;i++) {
ansarr.push_back(arr[i].second);
}
return ansarr;
} else {
top = middle;
}
}
cout << top << ' ' << bottom << '\n';
if (prefix[top] < l) {
base = top;
} else if (prefix[top] <= u) {
for (int i=0;i<top+1;i++) {
ansarr.push_back(arr[i].second);
}
return ansarr;
} else if (prefix[bottom] < l) {
base = bottom;
} else if (prefix[bottom] <= u) {
for (int i=0;i<bottom+1;i++) {
ansarr.push_back(arr[i].second);
}
return ansarr;
} else {
return ansarr;
}
int anstotal = prefix[base], anstart = 0;
for (int i=0;i<n-base;i++) {
if (anstotal < l) {
if (i == n-base-1) {
return ansarr;
}
anstotal = prefix[i+base+1] - prefix[i];
} else {
anstart = i;
break;
}
}
int gap = anstart-1;
for (int i=0;i<base+1;i++) {
if (anstotal < u) {
for (int j=anstart-1;j<anstart+base+1;j++) {
if (j == gap) {
continue;
}
ansarr.push_back(arr[j].second);
}
break;
} else {
anstotal += arr[gap].first - arr[gap+1].first;
}
}
return ansarr;
}
