Submission #1069545

#TimeUsernameProblemLanguageResultExecution timeMemory
1069545IgnutDetecting Molecules (IOI16_molecules)C++17
100 / 100
46 ms7364 KiB
// Ignut #include <bits/stdc++.h> using namespace std; using ll = long long; vector<int> find_subset(int L, int U, vector<int> w) { int n = w.size(); vector<pair<int, int>> v; for (int i = 0; i < n; i ++) v.push_back({w[i], i}); sort(v.begin(), v.end()); ll pref[n + 1] = {}; for (int i = 0; i < n; i ++) pref[i + 1] = pref[i] + v[i].first; for (int l = 0; l < n; l ++) { int lo = l, hi = n - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (pref[mid + 1] - pref[l] < L) lo = mid + 1; else hi = mid; } if (pref[lo + 1] - pref[l] >= L && pref[lo + 1] - pref[l] <= U) { vector<int> res; for (int i = l; i <= lo; i ++) res.push_back(v[i].second); return res; } } 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...