제출 #473976

#제출 시각아이디문제언어결과실행 시간메모리
473976cs71107Detecting Molecules (IOI16_molecules)C++14
9 / 100
1 ms460 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...