Submission #1252951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252951		kkzyr	Festival (IOI25_festival)	C++20	0 / 100	58 ms	6836 KiB

festival

#include <iostream>
#include <algorithm>
using namespace std;

vector<int> prefix_sum;
vector<pair<int, int>> coupons_type1;
vector<pair<int, int>> coupons_type2;

int binary_search(long long coins){
    int lo = 0, hi = (int)coupons_type1.size() - 1, ans = -1;
    while (lo <= hi){
        int mid = (lo + hi)/2;
        if (prefix_sum[mid] <= coins){
            ans = mid;
            lo = mid + 1;
        }
        else{
            hi = mid - 1;
        }
    }
    return ans;
}

std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T){
    for (int i = 0;i < P.size();i++){
        if (T[i] == 1){
            coupons_type1.push_back({P[i], i});
        }
        else{
            coupons_type2.push_back({P[i], i});
        }
    }
    sort(coupons_type1.begin(), coupons_type1.end());
    sort(coupons_type2.begin(), coupons_type2.end());
    for (int i = 0;i < coupons_type1.size();i++){
        if (i == 0){
            prefix_sum.push_back(coupons_type1[i].first);
        }
        else{
            prefix_sum.push_back(prefix_sum[i - 1] + coupons_type1[i].first);
        }
    }
    pair<int, int> num_coupons = {0, binary_search(A) + 1};
    int best_val = binary_search(A) + 1;
    long long coins_left = A;
    for (int i = 0;i < coupons_type2.size();i++){
        if (coins_left < coupons_type2[i].first){
            coins_left = 0;
        }
        else{
            coins_left = (coins_left - coupons_type2[i].first) * 2;
            if (coins_left > 1000000000000000LL){
                coins_left = 1000000000000000LL;
            }
        }
        int binary_search_value = binary_search(coins_left);
        if ((i + binary_search_value + 1) > best_val){
            best_val = i + binary_search_value + 1;
            num_coupons = {binary_search_value + 1, i + 1};
        }
    }
    vector<int> answer;
    for (int i = 0;i < num_coupons.second;i++){
        answer.push_back(coupons_type2[i].second);
    }
    for (int i = 0;i < num_coupons.first;i++){
        answer.push_back(coupons_type1[i].second);
    }
    return answer;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 27
• Subtask 6: 0 / 16
• Subtask 7: 0 / 18