#include "festival.h" using namespace std; #include <bits/stdc++.h> int how_many_type_1_can_we_buy(long long A2, std::vector<long long>& type1_prefix){ int l = -1; int r = type1_prefix.size() + 1; int mid; while(r - l > 1){ mid = (l + r) / 2; if(type1_prefix[mid] > A2){ r = mid; } else { l = mid; } } return l; } std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) { long long A2 = A; struct Coupon { int cost; int type; int index; bool operator<(const Coupon& other) const { if (cost != other.cost) return cost < other.cost; return type > other.type; } }; /* Start by buying a specific number of coupons that double. */ vector<Coupon> type2; vector<Coupon> type1; for(int i = 0; i < P.size(); i ++){ if(T[i] == 2){ type2.push_back({P[i], T[i], i}); } else { type1.push_back({P[i], T[i], i}); } } sort(type2.begin(), type2.end()); sort(type1.begin(), type1.end()); // vector<long long> type1_prefix(1, 0); for(Coupon& coupon : type1){ type1_prefix.push_back(type1_prefix.back() + coupon.cost); } //cout << "We can buy: " << how_many_type_1_can_we_buy(10, type1_prefix) << "\n"; /* Iterate through type 2 coupons TODO: case where we ONLY buy type 1 coupons */ //for(int i : type1_prefix) cout << i << " "; //cout << "\n"; int max_coupons = how_many_type_1_can_we_buy(A2, type1_prefix); int num_type1 = max_coupons; int num_type2 = 0; for(int i = 0; i < type2.size(); i ++){ if(A2 >= type2[i].cost){ A2 -= type2[i].cost; A2 *= 2; //cout << A << " "; // int type1_we_buy = how_many_type_1_can_we_buy(A2, type1_prefix); if(i + 1 + type1_we_buy > max_coupons){ max_coupons = i + 1 + type1_we_buy; num_type2 = i + 1; num_type1 = type1_we_buy; } } } //cout << "\n"; //cout << "Max coupons: " << max_coupons << " with " << num_type2 << " type2" << "\n"; vector<int> res; for(int i = 0; i < num_type2; i ++){ res.push_back(type2[i].index); } for(int i = 0; i < num_type1; i ++){ res.push_back(type1[i].index); } return res; } /* g++ -std=gnu++20 -Wall -O2 -pipe -static -g -o festival grader.cpp festival.cpp 5 2 5 1 3 1 2 1 6 1 6 1 7 10 1 2 2 2 5 1 5 1 5 2 20 1 25 1 */