#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() + 1;
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-1, 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
5 2
5 1
3 1
2 1
6 1
6 1
7 10
1 1
2 1
5 1
5 1
5 1
20 1
25 1
*/
