Submission #1252968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252968		kkzyr	Festival (IOI25_festival)	C++20	Compilation error	0 ms	0 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 = {binary_search(A) + 1, 0};
    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){
            break;
        }
        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 + 2) > best_val){
            best_val = i + binary_search_value + 2;
            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;
}

int n;

int main(){
    cin >> n;
    vector<int> p;
    vector<int> t;
    for (int i = 1;i <= n;i++){
        int a;
        cin >> a;
        p.push_back(a);
    }
    for (int i = 1;i <= n;i++){
        int a;
        cin >> a;
        t.push_back(a);
    }
    vector<int> x = max_coupons(n, p, t);
    for (int i = 0;i < x.size();i++){
        cout << x[i] << ' ';
    }
    cout << '\n';
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cc53MHSU.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccKEPy0q.o:festival.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status