제출 #591687

#제출 시각아이디문제언어결과실행 시간메모리
591687AlperenTDetecting Molecules (IOI16_molecules)C++17
69 / 100
82 ms12780 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; vector<pair<int, int>> arr; for(int i = 0; i < n; i++) arr.push_back({w[i], i}); sort(arr.begin(), arr.end()); for(int i = 0; i < n; i++){ if(sum < l){ sum += arr[i].first; taken.insert(arr[i]); } else{ free.insert(arr[i]); } } bool flag = false; while(!(sum >= l && sum <= u)){ if(sum > u){ if(flag) return vector<int>{}; if(free.empty() || free.begin()->first - prev(taken.end())->first >= 0){ 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 <= 0){ return vector<int>{}; } else{ flag = true; 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); long long actsum = 0; for(auto i : ans) actsum += w[i]; assert(actsum >= l && actsum <= u); 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...