/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#include "molecules.h"
using namespace std;
typedef long long ll;
vector <int> find_subset (int low, int high, vector <int> w)
{
int n = (int) w.size();
vector <int> p (n);
for(int i = 0; i < n; i++)
p[i] = i;
sort(p.begin(), p.end(),
[&] (const int &x, const int &y)
{
return w[x] < w[y];
});
vector <int> pref (n);
for(int i = 0; i < n; i++)
pref[i] = w[p[i]];
for(int i = 1; i < n; i++)
pref[i] += pref[i - 1];
function <int (int, int)> seg = [&] (int l, int r)
{
return pref[r] - (l == 0 ? 0 : pref[l - 1]);
};
for(int len = 1; len <= n; len++)
if(seg(0, len - 1) <= low && low <= seg(n - len, n - 1))
{
int pos = 0;
while(seg(pos + 1, pos + len) < low)
pos++;
vector <int> answer (len);
for(int i = 0; i < len; i++)
answer[i] = pos + i;
int sum = seg(pos, pos + len - 1);
int curr = len - 1;
while(sum < low)
{
sum -= w[p[answer[curr]]];
answer[curr]++;
sum += w[p[answer[curr]]];
curr--;
}
for(int i = 0; i < len; i++)
answer[i] = p[answer[i]];
return answer;
}
else if(low <= seg(0, len - 1) && seg(0, len - 1) <= high)
{
vector <int> answer (len);
for(int i = 0; i < len; i++)
answer[i] = p[i];
return answer;
}
return {};
}
