#include "molecules.h"
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/ioi/codes/ioi16_d1/debug.h"
#else
#define debug(...) void(37)
#endif
std::vector<int> find_subset(int L, int U, std::vector<int> W) {
int N = int(W.size());
vector<int> ord(N);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int x, int y) {
return W[x] < W[y];
});
vector<int> nw(N);
for (int i = 0; i < N; ++i) {
nw[i] = W[ord[i]];
}
swap(W, nw);
debug(W, ord);
int sum = 0;
int p = -1;
vector<int> res;
while (p < N - 2 && sum + W[p + 1] <= U) {
++p;
sum += W[p];
res.push_back(p);
}
for (int i = p; i >= 0; --i) {
int next = W[N - 1 - (p - i)];
res.pop_back();
if (sum + next - W[i] >= L) {
int add = i;
while (sum < L) {
sum += W[add + 1] - W[add];
++add;
}
assert(L <= sum && sum <= U);
res.push_back(add);
break;
} else {
sum += next - W[i];
}
}
debug(res);
if (sum < L || U < sum) {
return vector<int>{};
}
for (int i = p - int(res.size()); i >= 0; --i) {
res.push_back(N - 1 - i);
}
for (auto& x : res) {
x = ord[x];
}
sort(res.begin(), res.end());
return res;
}
