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>
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2e5+10;
pii A[MAXN];
ll psum[MAXN];
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
int n = (int)w.size();
for(int i=1;i<=n;i++){
A[i] = pii(w[i-1],i-1);
}
sort(A+1,A+n+1);
for(int i=1;i<=n;i++){
psum[i] = psum[i-1]+(ll)A[i].f;
}
ll lsum = 0;
ll rsum = 0;
ll curv = 0;
ll lv = 0;
ll rv = 0;
vector<int> ans;
int idx = 1;
for(int i=1;i<=n;i++){
lsum += (ll)A[i].f;
rsum += (ll)A[n+1-i].f;
if(lsum>u)break;
if(rsum<l)continue;
if(lsum>=l){
for(int j=1;j<=i;j++){
ans.push_back(A[j].s);
}
}
else if(rsum<=u){
for(int j=1;j<=i;j++){
ans.push_back(A[n+1-j].s);
}
}
else {
idx = 1;
curv = 0;
for(int j=i-1;j>=0;j--){
while(idx<=n){
lv = curv + A[idx].f + (psum[idx+j]-psum[idx]);
rv = curv + A[idx].f + (psum[n]-psum[n-j]);
if(lv<=l&&rv<=u)break;
idx++;
}
assert(idx<=n);
ans.push_back(A[idx].s);
curv += (ll)A[idx].f;
lv = curv + (psum[idx+j]-psum[idx]);
rv = curv + (psum[n]-psum[n-j]);
if(l<=lv&&lv<=u){
for(int t=idx+1;t<=idx+j;t++){
ans.push_back(A[t].s);
}
break;
}
else if(l<=rv&&rv<=u){
for(int t=n-j+1;t<=n;t++){
ans.push_back(A[t].s);
}
break;
}
idx++;
}
}
break;
}
return ans;
}
# | 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... |