Submission #1254554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254554		vpinx	Festival (IOI25_festival)	C++20	24 / 100	55 ms	6836 KiB

festival

#include "festival"
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()

int upb(vector<pair<int, int>> &t1, int val) {
    int idx = t1.size(), l = 0, r = t1.size() - 1;
    while (l <= r) {
        int m = (l + r) / 2;
        if (t1[m].first > val) {
            r = m - 1;
            idx = m;
        }else l = m + 1;
    }
    return idx;
}

vector<int> max_coupons(int a, vector<int> p, vector<int> t) {
    vector<pair<int, int>> t1, t2;
    for (int i = 0; i < p.size(); i++) {
        if (t[i] == 1) t1.push_back({p[i], i});
        else t2.push_back({p[i], i});
    }

    sort(all(t1));
    sort(all(t2));
    for (int i = 1; i < t1.size(); i++) t1[i].first += t1[i - 1].first;
    
    long long cur = a;
    int idx = -1, ans = upb(t1, a);
    for (int i = 0; i < t2.size(); i++) {
        if (cur < t2[i].first) break;
        if (cur - t2[i].first > LLONG_MAX / 2) {
            vector<int> ret;
            for (int j = 0; j < t2.size(); j++) ret.push_back(t2[j].second);
            for (int j = 0; j < t1.size(); j++) ret.push_back(t1[j].second);
            return ret;
        }
        
        cur = (cur - t2[i].first) * 2;
        int cur_val = upb(t1, cur) + i + 1;
        if (cur_val > ans) {
            ans = cur_val;
            idx = i;
        }
    }
    
    vector<int> v;
    long long cur_ans = a;
    for (int i = 0; i <= idx; i++) {
        cur_ans = (cur_ans - t2[i].first) * 2;
        v.push_back(t2[i].second);
    }
    
    int cur_idx = 0;
    while (cur_idx < t1.size()) {
        if (cur_ans < t1[cur_idx].first) break;
        v.push_back(t1[cur_idx++].second);
    }
    return v;
}

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