# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1208519 | omsincoconut | Detecting Molecules (IOI16_molecules) | C++17 | 34 ms | 6728 KiB |
#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> find_subset(int l, int u, vector<int> w) {
int n = w.size();
vector<pair<ll, int>> wi(n);
ll sum_all = 0;
for (int i = 0; i < n; i++) {
wi[i] = make_pair((ll)w[i], i);
sum_all += w[i];
}
sort(wi.begin(), wi.end());
if (u < wi[0].first || l > sum_all) return vector<int>();
ll qc[n+1];
qc[0] = 0;
for (int i = 1; i <= n; i++) qc[i] = qc[i-1] + wi[i-1].first;
int take = 0;
while (take <= n && qc[take] <= u) take++;
take--;
for (int left = 0; left <= take; left++) {
ll val = qc[left] + qc[n] - qc[n-take+left];
if (l <= val && val <= u) {
vector<int> ret;
for (int i = 0; i < left; i++) ret.push_back(wi[i].second);
for (int i = n-take+left; i < n; i++) ret.push_back(wi[i].second);
return ret;
}
}
return {};
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |