Submission #1282995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282995		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 < b.p);
    });
    
    int m = arr1.size();
    int k = arr2.size();
    sort(arr2.begin(),arr2.end());
    
    ll curr = A;
    vector<int> R;
    vector<int> pref(k+1,0);
    for(int i = 1; i <= k; ++i){
        pref[i] = pref[i-1] + arr2[i-1].first;
    }
    int cnt = 0;
    int L,Rt;
    for(int i = -1; i < m; ++i){
        if(i == -1){
            int l = 0;
            int r = k;
            while(r - l > 0){
				int m = (l+r+1)/2;
				if(pref[m] <= curr) l = m;
				else r = m-1;
			}
            cnt = l;
            L=-1;
            Rt=l-1;
            continue;
        }
        curr -= arr1[i].p;
        curr *= arr1[i].t;
        if(curr < 0) break;
        if(curr > 2e15) curr = 2e15;
        int l = 0;
        int r = k;
        while(r - l > 0){
            int m = (l+r+1)/2;
			if(pref[m] <= curr) l = m;
			else r = m-1;
        }
        if(l+i+1 > cnt) {
            L=i;
            Rt=l-1;
            cnt = l+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