#include "molecules.h"
#ifdef LOCAL
#include "grader.cpp"
#endif
#include <vector>
#include <cassert>
#include <algorithm>
#include <set>
#include <map>
typedef long long ll;
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
int n = (int) w.size();
std::vector<std::pair<int, int>> a(n);
for (int i = 0; i < n; i++) {
a[i] = {w[i], i};
}
std::sort(a.begin(), a.end());
/**
l <= sum[i] - sum[j - 1] <= u | -sum[i]
=>
l - sum[i] <= -sum[j - 1] <= u - sum[i] | *-1
sum[i] - l >= sum[j - 1] >= sum[i] - u
**/
std::set<ll> st;
std::map<ll, int> pos;
ll s = 0;
st.insert(0);
pos[0] = -1;
for (int i = 0; i < n; i++) {
auto [value, idx] = a[i];
s += value;
auto it = *st.lower_bound(s - u);
if (it <= s - l) {
std::vector<int> ret;
for (int j = pos[it] + 1; j <= i; j++) {
ret.push_back(a[j].second);
}
return ret;
}
st.insert(s);
pos[s] = i;
}
return {};
}
/**
4 15 17
6 8 8 7
**/
