#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = tuple<int, int>;
using vii = vector<ii>;
using i64 = int64_t;
using vl = vector<i64>;
using ll = pair<i64, i64>;
using vll = vector<ll>;
constexpr int iINF = numeric_limits<int>::max();
constexpr i64 lINF = numeric_limits<i64>::max();
#define RANGE(x) begin(x), end(x)
template <typename... T>
void DBG(T&&... args) {
((cerr << args << ' '), ...) << '\n';
}
template <typename T>
ostream &operator<<(ostream &out, const vector<T> &vec) {
out << '{';
for (size_t i = 0; i < vec.size()-1; ++i)
out << vec[i] << ", ";
out << vec.back() << '}';
return out;
}
std::vector<int> find_subset(int L, int U, std::vector<int> w) {
const int N = w.size();
vi sorted(N);
iota(RANGE(sorted), 0);
stable_sort(RANGE(sorted), [&] (auto a, auto b) {
return w[a] < w[b];
});
DBG(sorted);
vl sum(N+1);
for (int i = 1; i <= N; ++i) {
sum[i] = sum[i-1] + i64(w[sorted[i-1]]);
}
DBG(sum);
for (int i = 1; i <= N; ++i) {
int l, r;
l = i;
r = N;
while (true) {
int mid = (l+r+1) / 2;
i64 rsum = sum[mid] - sum[i-1];
if (rsum <= U && rsum >= L) {
l = i;
r = mid;
DBG(l, r, rsum);
vi ans;
ans.reserve(r-l);
for (i = l; i <= r; ++i) {
ans.push_back(sorted[i-1]);
}
DBG(ans);
return ans;
}
if (l == r) {
break;
}
if (rsum > U) {
r = mid-1;
} else if (rsum < L) {
l = mid;
}
}
}
return {};
}
