Submission #1282969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282969		tschav_	Festival (IOI25_festival)	C++20	0 / 100	54 ms	9580 KiB

festival

#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " -> " << x << "\n"
using namespace std; 

using ll = long long;
using pii = pair<int,int>;

struct ticket {
    int p;
    int t;
    int idx;
};

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

    vector<ticket> arr1;
    vector<pii> arr2;
    
    for(int i = 0; i < n; ++i){
        ticket t;
        t.p = P[i];
        t.t = T[i];
        t.idx = i;
        if(T[i] == 2)
        arr1.push_back(t);
        else
        arr2.push_back(pii{t.p,i});
    }
    
    sort(arr1.begin(),arr1.end(),[&](auto a, auto b) {
        return (-a.p*a.t*b.t - b.p*b.t < -b.p*b.t*a.t - a.p*a.t);
    });
    
    int m = arr1.size();
    int k = arr2.size();
    sort(arr2.begin(),arr2.end());
    
    ll curr = A;
    vector<int> R;
    vector<int> pref(k,0);
    pref[0] = arr2[0].first;
    for(int i = 1; i < k; ++i){
        pref[i] = pref[i-1] + arr2[i].first;
    }
    int cnt = 0;
    int L,Rt;
    for(int i = -1; i < m; ++i){
        if(i == -1){
            int l = -1;
            int r = k-1;
            while(r - l > 0){
                int m = (l+r)/2;
                if(r - l == 1) {
                if(pref[r] > curr) {
                    break;
                }else l=r;
                break;
            }
                int H = 0;
                if(m >= 0) H = pref[m];
                if(H > curr) {
                    r = m-1;
                } else l = m;
            }
            cnt = l+1;
            L=-1;
            Rt=l;
            continue;
        }
        curr -= arr1[i].p;
        curr *= arr1[i].t;
        if(curr < 0) break;
        if(curr > 2e14) curr = 2e14;
        int l = -1;
        int r = k-1;
        while(r - l > 0){
            int m = (l+r)/2;
            if(r - l == 1) {
                if(pref[r] > curr) {
                    break;
                }else l=r;
                break;
            }
            int H = 0;
            if(m >= 0) H = pref[m];
            if(H > curr) {
                r = m-1;
            } else l = m;
        }
        if(l+1+i+1 > cnt) {
            L=i;
            Rt=l;
            cnt = l+1+i+1;
        }
    }
    for(int i = 0; i <= L;++i){
        R.emplace_back(arr1[i].idx);
    }
    for(int j = 0; j <= Rt;++j){
        R.emplace_back(arr2[j].second);
    }
    return R;
}

// int main() {
//     vector<int> R;
    
//     R = max_coupons(9, vector<int>{1,1,1,1}, vector<int>{1,2,2,2});
    
//     for(auto &i : R) cout << i << " ";
// }

• 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