Submission #1251543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251543		fv3	Festival (IOI25_festival)	C++20	0 / 100	43 ms	8104 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define all(x) x.begin(), x.end()

vector<int> max_coupons(int A_, vector<int> P, vector<int> T) {
    const int n = P.size();
    ll A = A_;

    vector<pair<ll, int>> ones, twos;
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        if (T[i] == 1) {
            ones.push_back({P[i], i});
        } else {
            twos.push_back({P[i], i});
        }

        sum += P[i];
    }

    sort(all(ones));

    vector<ll> ps(int(ones.size()) + 1);
    for (int i = 0; i < int(ones.size()); i++) {
        ps[i+1] = ps[i] + ones[i].first;
    }

    sort(all(twos));

    int best_two_cnt = 0;
    auto Count = [&](ll M) -> int {
        int lo = 0, hi = ones.size();
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (ps[mid] > M) {
                hi = mid - 1;
            } else {
                lo = mid;
            }
        }
        return lo;
    };
    int best_score = Count(A);

    for (int i = 0; i < n; i++) {
        if (twos[i].first> A) break;

        A = (A - twos[i].first) * 2ll;
        sum -= twos[i].first;

        if (A >= sum) {
            vector<int> res;
            for (auto [x, j] : twos) {
                res.push_back(j);
            }
            for (auto [x, j] : ones) {
                res.push_back(j);
            }
            return res;
        }

        int score = Count(A);
        if (i + 1 + score > best_two_cnt + best_score) {
            best_two_cnt = i + 1;
            best_score = score;
        }
    }

    vector<int> res;
    for (int i = 0; i < best_two_cnt; i++) {
        res.push_back(twos[i].second);
    }
    for (int i = 0; i < best_score; i++) {
        res.push_back(ones[i].second);
    }

    return res;
}

//#include "grader.cpp"

• 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