| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1317097 | marzuq01 | Detecting Molecules (IOI16_molecules) | C++20 | 0 ms | 0 KiB |
#include "molecules.h"
#include <bits/stdc++.h>
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
using namespace std;
int n = w.size();
vector<int> nope;
for (int i = 0;i < n;i++) {
if (l <= w[i] && w[i] <= u) {
return {i};
}
}
// all element outside [l,r]
vector<pair<int,int>> v;
for (int i = 0; i < n;i++) {
if (w[i] < l) v.push_back({w[i],i});
}
if (v.size() <= 1) return nope;
// v.size() >= 2
sort(v.begin(),v.end());
int flag0 = v[0].first + v[v.size() - 1].first;
if (l <= flag0 && flag0 <= u) {
return {v[0].second,v[v.size() - 1].second};
}
int sum = 0;
for (auto i : v) sum += i.first;
if (l <= sum && sum <= u) {
vector<int> result;
for (int i = 0; i < v.size();i++) {
result.push_back(v[i].second);
}
return result;
} else if (sum < l) return nope;
sum = 0;
//sort(v.rbegin(),v.rend());
reverse(v.begin(),v.end());
vector<int> res;
for (int i = 0; i < n;i++) {
int now = sum + v[i].first;
if (now > u) continue;
sum += v[i].first;
res.pb(v[i].second);
if (l <= sum && sum <= u) return res;
}
return {0};
}
