#include "festival.h" using namespace std; #include <bits/stdc++.h> int how_many_type_1_can_we_buy(int A, std::vector<int>& type1_prefix){ int l = -1; int r = type1_prefix.size(); int mid; while(r - l > 1){ mid = (l + r) / 2; if(type1_prefix[mid] > A){ r = mid; } else { l = mid; } } return l; } std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) { 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<int> 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 */ int max_coupons = how_many_type_1_can_we_buy(A, type1_prefix); int num_type1 = max_coupons; int num_type2 = 0; for(int i = 0; i < type2.size(); i ++){ if(A >= type2[i].cost){ A -= type2[i].cost; A *= 2; //cout << A << " "; // int type1_we_buy = how_many_type_1_can_we_buy(A, 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 7 10 1 1 2 1 5 1 5 1 5 1 20 1 25 1 */