# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
276373 | eohomegrownapps | Detecting Molecules (IOI16_molecules) | C++14 | 68 ms | 8696 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 "molecules.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> find_subset(int l, int u, vector<int> wx) {
ll n = wx.size();
vector<ll> minval(n);
vector<ll> maxval(n);
vector<pair<int,int>> w(n);
for (int i = 0; i<n; i++){
w[i]={wx[i],i};
}
sort(w.begin(),w.end());
ll curmin = 0;
ll curmax = 0;
for (int i = 0; i<n; i++){
curmin+=w[i].first;
curmax+=w[n-1-i].first;
minval[i]=curmin;
maxval[i]=curmax;
}
/*for (int i = 0; i<n; i++){
cout<<minval[i]<<' '<<maxval[i]<<'\n';
}*/
for (int i = 0; i<n; i++){
if (minval[i]<=l&&l<=maxval[i]||minval[i]<=u&&u<=maxval[i]||l<=minval[i]&&maxval[i]<=u){
int lptr = i;
int rptr = n-1;
ll s = minval[i];
while (!(l<=s&&s<=u)){
s-=w[lptr].first;
s+=w[rptr].first;
lptr--;
rptr--;
}
vector<int> ans;
for (int i = 0; i<=lptr; i++){
ans.push_back(w[i].second);
}
for (int i = rptr+1; i<n; i++){
ans.push_back(w[i].second);
}
assert(ans.size()>0);
return ans;
} else {
assert(maxval[i]<l||u<minval[i]);
}
}
return vector<int>(0);
}
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... |