# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1196109 | ahmetlbktd4 | Detecting Molecules (IOI16_molecules) | C++20 | 1096 ms | 320 KiB |
#include <bits/stdc++.h>
#include "molecules.h"
#define ll long long
using namespace std;
vector<int> find_subset(int l, int u, vector<int> w) {
int n = w.size();
vector<int>in;
for (int i = 0;i < n;i++){
in.push_back(i);
}
sort(in.begin(),in.end(),[&](int a,int b){
return (w[a] < w[b]);
});
vector <ll> h(n+1);
h[n] = 0;
for (int i = n-1;i >= 0;i--){
h[i] = h[i+1]+w[in[i]];
}
ll s = 0;
for (int i = 0;i < n;i++){
if (s > u)
break;
if (s >= l){
vector<int>p;
for (int j = 0;j < i;j++){
p.push_back(in[j]);
}
return p;
}
int l1=i,r=n-1;
while (l1 <= r){
int m = (l+r)/2;
ll k = s+h[m];
if (k <= u && k >= l){
vector<int>p;
for (int j = 0;j < i;j++){
p.push_back(in[j]);
}
for (int j = m;j < n;j++){
p.push_back(in[j]);
}
return p;
}
if (k > u)
l1 = m+1;
else r = m-1;
}
s+=w[in[i]];
}
return vector<int>{};
}
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... |