제출 #1254704

#제출 시각아이디문제언어결과실행 시간메모리
1254704fasterthanyouFestival (IOI25_festival)C++20
5 / 100
56 ms12712 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; struct Coupon { int idx; ll P; int T; }; static inline ll ceil_div(ll a, ll b) { // b > 0 return (a + b - 1) / b; } // Given an order, check feasibility and also return the actually buyable prefix. static pair<int, vector<int>> simulate_forward(ll A, const vector<Coupon>& order) { ll X = A; vector<int> taken; taken.reserve(order.size()); for (const auto& c : order) { if (X < c.P) break; X = (X - c.P) * c.T; taken.push_back(c.idx); } return { (int)taken.size(), move(taken) }; } // Core heuristic: build an order backwards minimizing the required initial tokens R at each step. vector<int> max_coupons(int A, vector<int> P, vector<int> T) { const int N = (int)P.size(); // 1) Buckets by T, min-heap by P within each T. // We store {P, idx}. array<priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>>, 5> pq; for (int i = 0; i < N; ++i) { int t = T[i]; if (t < 1 || t > 4) continue; // safety pq[t].push({(ll)P[i], i}); } // 2) Backward greedy: maintain current suffix requirement R. ll R = 0; vector<Coupon> built; built.reserve(N); auto peek_val = [&](int t)->pair<ll,int> { if (pq[t].empty()) return { (ll)4e18, -1 }; auto [p, idx] = pq[t].top(); ll val = p + ceil_div(R, (ll)t); return { val, idx }; }; while (true) { // Among T in {1,2,3,4}, choose the class with minimal p + ceil(R/T) ll bestVal = (ll)4e18; int bestT = -1; int bestIdx = -1; for (int t = 1; t <= 4; ++t) { auto [val, idx] = peek_val(t); if (val < bestVal || (val == bestVal && t > bestT)) { // tie-break: larger T first bestVal = val; bestT = t; bestIdx = idx; } } if (bestIdx == -1) break; if (bestVal > (ll)A) break; // cannot extend while keeping requirement <= A // Take it into the backward-built suffix auto [p, idx] = pq[bestT].top(); pq[bestT].pop(); built.push_back(Coupon{ idx, p, bestT }); R = bestVal; // new requirement after appending this coupon at the front } // 3) Reverse built order to play forward. reverse(built.begin(), built.end()); // 4) Simulate forward; by construction this prefix is feasible from A. auto [cnt, ans] = simulate_forward((ll)A, built); // 5) OPTIONAL cheap tail: after the planned order, we may still afford extra T=1 with small P. // Take remaining T=1 coupons in ascending P as much as possible; they cannot hurt feasibility already achieved. // (We do a light pass without altering previously taken.) { // Gather remaining T=1 not used. vector<pair<ll,int>> t1; while (!pq[1].empty()) { t1.push_back(pq[1].top()); pq[1].pop(); } sort(t1.begin(), t1.end()); // ascending P // Re-simulate to the end of planned prefix to get current X, then append T=1 greedily. ll X = A; for (int i = 0; i < cnt; ++i) { int id = ans[i]; ll p = P[id], t = T[id]; X = (X - p) * t; // feasible by construction } for (auto [p, id] : t1) { if (X < p) break; X -= p; ans.push_back(id); } } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...