Submission #591668

#TimeUsernameProblemLanguageResultExecution timeMemory
591668AlperenTDetecting Molecules (IOI16_molecules)C++17
0 / 100
1097 ms304 KiB
#include <bits/stdc++.h> #include "molecules.h" using namespace std; vector<int> find_subset(int l, int u, vector<int> w){ int n = w.size(), sum = 0; set<pair<int, int>> taken, free; sort(w.begin(), w.end()); for(int i = 0; i < n; i++){ if(sum < l){ sum += w[i]; taken.insert({w[i], i}); } else{ free.insert({w[i], i}); } } while(!(sum >= l && sum <= u)){ if(sum > u){ if(free.empty() || free.begin()->first >= prev(taken.end())->first){ sum -= prev(taken.end())->first; free.insert(*prev(taken.end())); taken.erase(prev(taken.end())); } else{ sum += free.begin()->first - prev(taken.end())->first; pair<int, int> p = *free.begin(), p2 = *prev(taken.end()); free.erase(p), taken.erase(p2); free.insert(p2), taken.insert(p); } } else if(sum < l){ if(free.empty() || prev(free.end())->first <= taken.begin()->first){ return vector<int>{}; } else{ sum += prev(free.end())->first - taken.begin()->first; pair<int, int> p = *prev(free.end()), p2 = *taken.begin(); free.erase(p), taken.erase(p2); free.insert(p2), taken.insert(p); } } } vector<int> ans; for(auto p : taken) ans.push_back(p.second); 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...