/**
* If we've got a subset S and two elements x, y (not in S). We must not have:
* sum(S + {x}) > u, sum(S + {y}) < v,
* As this immediately violates the given constraint. We now can propose a solution.
*
* Time Complexity: O(n * log(n))
* Implementation 1
*/
#include <bits/stdc++.h>
#include "molecules.h"
struct val_t {
int pos, val;
};
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
int n = w.size();
std::vector<val_t> values(n);
for (int k = 0; k < n; k++)
values[k].val = w[k], values[k].pos = k;
std::sort(values.begin(), values.end(),
[](const val_t& v1, const val_t& v2) {
return v1.val < v2.val;
});
std::vector<int> prefix_sum(n + 1);
prefix_sum[0] = 0;
for (int i = 0; i < n; i++)
prefix_sum[i + 1] = prefix_sum[i] + values[i].val;
bool found = false;
std::vector<int> ans;
for (int i = n; i >= 1 && !found; i--) {
int j = i;
for (int step = n / 2 + 1; step >= 1; step /= 2) {
while (j - step >= 0 && prefix_sum[i] - prefix_sum[j - step] <= u)
j -= step;
}
if (prefix_sum[i] - prefix_sum[j] >= l) {
assert(prefix_sum[i] - prefix_sum[j] <= u);
found = true;
for (int k = j; k < i; k++)
ans.emplace_back(k);
} else if (j > 0) {
if (values[0].val + prefix_sum[i] - prefix_sum[j] <= u) {
found = true;
ans.emplace_back(0);
for (int k = j; k < i; k++)
ans.emplace_back(k);
}
}
}
if (found) { // test-driven development
int sum = 0;
for (int& a : ans) {
sum += values[a].val;
a = values[a].pos;
}
assert(sum >= l && sum <= u);
return ans;
} else {
return std::vector<int>();
}
}
