/**
* 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. I proposed the following way
* of selecting numbers. Take S as the empty set, sort the numbers from large to
* small and consider them iteratively. If adding the current num to S keeps
* sum(S) <= u, we add it. I noticed that if the selected numbers don't form a
* consecutive segment, then there exists two numbers x > y where x isn't picked
* while y is. This case is solved. In other words, i just have to go through each
* position i and consider the maximal subarray ending at i. By induction i also
* proved that this is sufficient and necessary.
*
* Thomas and the editorial both provided simpler solutions. Instead of "adding
* numbers", we try "switching numbers", which better suits the property. The
* general idea is to iterate through all k, the size of our subset. For each k,
* if #sum_of_smallest_k_num >= l or #sum_of_greatest_k_num <= u the situation is
* easy to consider. When #sum_of_smallest_k_num < l and
* #sum_of_greatest_k_num > u, we can "smoothly" change our subset, eg by taking
* all subarrays of len k (on our sorted list). Shifting the frame right by 1 means
* to delete a num and add another one.
*
* Time Complexity: O(n * log(n))
* Implementation 1
*/
#include <bits/stdc++.h>
#include "molecules.h"
typedef long long ll;
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<ll> 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] <= ll(u))
j -= step;
}
if (prefix_sum[i] - prefix_sum[j] >= ll(l)) {
assert(prefix_sum[i] - prefix_sum[j] <= ll(u));
found = true;
for (int k = j; k < i; k++)
ans.emplace_back(k);
} else if (j > 0) {
if (ll(values[0].val) + prefix_sum[i] - prefix_sum[j] <= ll(u)) {
found = true;
ans.emplace_back(0);
for (int k = j; k < i; k++)
ans.emplace_back(k);
}
}
}
if (found) { // test-driven development
ll sum = 0;
for (int& a : ans) {
sum += values[a].val;
a = values[a].pos;
}
assert(sum >= ll(l) && sum <= ll(u));
return ans;
} else {
return std::vector<int>();
}
}
