#include "molecules.h" #include <vector> #include <algorithm> using namespace std; /* u - l >= w_max - w_min WLOG w[i] <= w[i+1] When is it impossible: * u < w[0] * sum(w) < l */ vector<int> W; int n; vector<int> find_subset(int l, int u, vector<int> w) { W = w; n = w.size(); int i, x; vector<int> I(n); for(i = 0; i < n; i++) I[i] = i; sort(I.begin(), I.end(), [] (int x, int y) { return W[x] < W[y]; }); int sum = w[I[0]]; vector<int> empty_res; vector<int> res; if(w[I[0]] > u) return empty_res; for(x = 1; x < n && sum < l; x++) { i = I[x]; sum += w[i]; res.push_back(i); } if(sum < l) return empty_res; sum -= w[I[x-1]]; res.pop_back(); sum -= w[I[0]]; sum += w[I[n-1]]; res.push_back(I[n-1]); return res; }