Submission #934780

#TimeUsernameProblemLanguageResultExecution timeMemory
934780ntminDetecting Molecules (IOI16_molecules)C++14
100 / 100
48 ms7872 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<int, ll> pil; #define fi first #define sc second vector<int> getans(set<pii> s){ vector<int> t; for(auto c : s){ t.push_back(c.second); } sort(t.begin(), t.end()); return t; } vector<int> find_subset(int l, int u, vector<int> w){ int n = w.size(); ll ans = 0; for(int i : w) ans += i; if(l <= ans && ans <= u){ vector<int> ans(n); iota(ans.begin(), ans.end(), 0); return ans; }; vector<pii> p; for(int i = 0; i < n; ++i){ p.push_back({w[i], i}); } sort(p.begin(), p.end()); if(ans < l) return {}; set<pii> s; ans = 0; for(int i = 0; i < n; ++i){ ans += p[i].first; s.insert(p[i]); if(ans < l) continue; if(l <= ans && ans <= u){ return getans(s); } if(ans > u){ auto itr = s.lower_bound(make_pair(ans - u, INT_MIN)); if(itr == s.end()) itr--; ans -= itr->first; s.erase(itr); if(l <= ans && ans <= u) return getans(s); } } return {}; } // int main(){ // int n, l, u; cin >> n >> l >> u; // vector<int> a(n); // for(int &x : a) cin >> x; // vector<int> ans = find_subset(l, u, a); // for(int i : ans) cout << i << ' '; // return 0; // }
#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...