# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
853711 | thinknoexit | Detecting Molecules (IOI16_molecules) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> find_subset(int l, int u, vector<int> w) {
int n = w.size();
pair<int, int> a[n];
ll sum = 0;
for (int i = 0;i < n;i++) {
sum += w[i];
a[i] = { w[i],i };
}
sort(a, a + n);
deque<int> dq;
vector<int> ans;
for (int i = 0;i < n;) {
if (l <= sum && sum <= u) break;
if (sum > u) {
sum -= a[dq.front()].first;
dq.pop_front();
continue;
}
else if (sum < l) {
sum += a[i].first;
dq.push_back(i);
i++;
}
}
while (sum > u) {
sum -= a[dq.front()].firstr;
dq.pop_front();
}
while (!dq.empty() && (l <= sum && sum <= u)) {
ans.push_back(a[dq.front()].second);
dq.pop_front();
}
return ans;
}