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;
#define ll long long
#define pii pair<int,int>
#define fs first
#define sc second
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
int N = w.size();
vector<int> mx(N);iota(mx.begin(),mx.end(),0);
sort(mx.begin(),mx.end(),[&](int a,int b){return w[a]>w[b];});
ll sum = 0;
set<pii> chose;
for(auto &now:mx){
if(l<=sum&&sum<=u){
vector<int> re;
for(auto &i:chose)re.push_back(i.sc);
return re;
}
if(sum<=u){
chose.insert(pii(w[now],now));
sum += w[now];
}
}
auto mn = mx;
while(sum>u){
while(!mn.empty()&&chose.find(pii(w[mn.back()],mn.back())) != chose.end())mn.pop_back();
if(mn.empty())break;
auto now = mn.back();
mn.pop_back();
auto out = *chose.rbegin();
sum -= out.fs;
chose.erase(out);
sum += w[now];
chose.insert(pii(w[now],now));
}
vector<int> ans;
for(auto &i:chose)ans.push_back(i.sc);
return (sum<=u&&sum>=l?ans:vector<int>());
}
# | 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... |