Submission #435992

#TimeUsernameProblemLanguageResultExecution timeMemory
435992qwerasdfzxclDetecting Molecules (IOI16_molecules)C++14
100 / 100
76 ms10184 KiB
#include "molecules.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; vector<int> find_subset(int l, int u, vector<int> w) { int n = w.size(); vector<pair<int, int>> a; for (int i=0;i<n;i++) a.emplace_back(w[i], i); sort(a.begin(), a.end()); vector<ll> prf, suf; prf.push_back(a[0].first); suf.push_back(a[n-1].first); for (int i=1;i<n;i++) prf.push_back(prf.back()+a[i].first); for (int i=n-2;i>=0;i--) suf.push_back(suf.back()+a[i].first); vector<int> ans; int idxr = lower_bound(suf.begin(), suf.end(), l) - suf.begin(); if (idxr<n && suf[idxr]<=u){ for (int i=0;i<=idxr;i++) ans.push_back(a[n-1-i].second); return ans; } if (idxr==n) return ans; for (int i=0;i<n;i++){ if (prf[i]>u) break; if (l<=prf[i] && prf[i]<=u){ for (int j=0;j<=i;j++) ans.push_back(a[j].second); break; } idxr = lower_bound(suf.begin(), suf.end(), l-prf[i]) - suf.begin(); if (prf[i]+suf[idxr]<=u){ for (int j=0;j<=i;j++) ans.push_back(a[j].second); for (int j=0;j<=idxr;j++) ans.push_back(a[n-1-j].second); 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...