Submission #1254547

#TimeUsernameProblemLanguageResultExecution timeMemory
1254547vpinxFestival (IOI25_festival)C++20
5 / 100
43 ms5564 KiB
#include "festival" #include <bits/stdc++.h> using namespace std; #define all(v) (v).begin(), (v).end() int upb(vector<pair<int, int>> &t1, int val) { int idx = t1.size(), l = 0, r = t1.size() - 1; while (l <= r) { int m = (l + r) / 2; if (t1[m].first > val) { r = m - 1; idx = m; }else l = m + 1; } return idx; } vector<int> max_coupons(int a, vector<int> p, vector<int> t) { vector<pair<int, int>> t1, t2; for (int i = 0; i < p.size(); i++) { if (t[i] == 1) t1.push_back({p[i], i}); else t2.push_back({p[i], i}); } sort(all(t1)); sort(all(t2)); for (int i = 1; i < t1.size(); i++) t1[i].first += t1[i - 1].first; long long cur = a; int idx = -1, ans = upb(t1, a); for (int i = 0; i < t2.size(); i++) { if (cur < t2[i].first) break; if (cur - t2[i].first > LLONG_MAX / 2) { vector<int> ret(p.size()); iota(all(ret), 1); return ret; } cur = (cur - t2[i].first) * 2; int cur_val = upb(t1, cur) + i + 1; if (cur_val > ans) { ans = cur_val; idx = i; } } vector<int> v; long long cur_ans = a; for (int i = 0; i <= idx; i++) { cur_ans = (cur_ans - t2[i].first) * 2; v.push_back(t2[i].second); } int cur_idx = 0; while (cur_idx < t1.size()) { if (cur_ans < t1[cur_idx].first) break; v.push_back(t1[cur_idx++].second); } return v; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...