Submission #1035572

#TimeUsernameProblemLanguageResultExecution timeMemory
1035572ArthuroWichDetecting Molecules (IOI16_molecules)C++17
100 / 100
43 ms8788 KiB
#include "molecules.h" #include <bits/stdc++.h> using namespace std; vector<int> find_subset(int a, int b, vector<int> in) { int n; n = in.size(); vector<pair<long long int, long long int>> w(n+1, {INT64_MIN, INT64_MIN}); for (int i = 1; i <= n; i++) { w[i] = {in[i-1], i-1}; } sort(w.begin(), w.end()); vector<long long int> pref(n+1, 0); for (int i = 1; i <= n; i++) { pref[i] = pref[i-1] + w[i].first; } for (int l = 0; l < n; l++) { int r = upper_bound(pref.begin(), pref.end(), pref[l]+b) - pref.begin(); r--; if (a <= pref[r]-pref[l] && pref[r]-pref[l] <= b) { vector<int> ans; for (int i = l+1; i <= r; i++) { ans.push_back(w[i].second); } return ans; } } return {}; }
#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...