# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1078393 | DrAymeinstein | 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 <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
static vector<int> find_subset(int l, int u, vector<int> w) {
int n = w.size();
vector<pair<int, int>> vec; // vec = <weight, index>
for (int i = 0; i < n; i++) {
vec.push_back({ w[i], i });
}
sort(vec.begin(), vec.end()); // based on w[i]
int left = 0, right = 0; // pointers (hash map maybe)
long long sum = vec[0].first;
while (right < n) {
if (sum >= l && sum <= u) {
vector<int> result;
for (int i = left; i <= right; i++) {
result.push_back(vec[i].second);
}
return result;
}
if (sum < 1 && right + 1 < n) {
right++;
sum += vec[right].first;
}
else if (sum > u && left < right) {
sum -= vec[left].first;
left++;
}
else {
break;
}
}
return {};
}