Submission #1305016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305016		Math4Life2020	Festival (IOI25_festival)	C++20	100 / 100	95 ms	28492 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

ll AMAX = 5e15; //if exceeds this -> can buy everything

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    ll Ac = A;
    vector<pii> vcp[5]; //T -> {P,idx}
    ll N = P.size();
    for (ll i=0;i<N;i++) {
        vcp[T[i]].push_back({P[i],i});
    }
    for (ll t=1;t<=4;t++) {
        sort(vcp[t].begin(),vcp[t].end());
    }
    queue<pii> qcp[5]; 
    for (ll t=1;t<=4;t++) {
        for (pii p0: vcp[t]) {
            qcp[t].push(p0);
        }
    }
    map<ll,ll> m1c; //count how many 1s from total amount available
    m1c[0]=0;
    ll tnum = 0; ll tval = 0;
    for (pii p0: vcp[1]) {
        tnum++; tval+=p0.first;
        m1c[tval]=tnum;
    }
    //first step: all steps that do not decrease Ac
    vector<int> R; //guaranteed R
    while(1) { //Ac = current A
        if (Ac>=AMAX) { //guaranteed can buy everything LOL
            for (ll t=1;t<=4;t++) {
                while (!qcp[t].empty()) {
                    pii p0 = qcp[t].front(); qcp[t].pop();
                    R.push_back(p0.second);
                }
            }
            return R; //terminated here!
        }
        ll xc = 6*Ac+1; ll tc = -1;
        for (ll t=2;t<=4;t++) {
            if (!qcp[t].empty()) {
                ll xn = (6*t*(qcp[t].front().first))/(t-1);
                if (xn<xc) {
                    xc = xn; tc = t;
                }
            }
        }
        if (tc==-1) {
            break;
        } else {
            pii p0 = qcp[tc].front(); qcp[tc].pop();
            R.push_back(p0.second);
            assert((tc*(Ac-p0.first))>=Ac);
            Ac = tc*(Ac-p0.first);
        }
    }
    // cout << "initial R: \n";
    // for (ll x: R) {
    //     cout << "x="<<x<<"\n";
    // }
    //now all must be decreasing: at most 60 decrements total
    vector<pii> vcp2[5]; //everything that's left
    for (ll t=1;t<=4;t++) {
        while (!qcp[t].empty()) {
            vcp2[t].push_back(qcp[t].front()); qcp[t].pop();
        }
    }
    ll mnc = -1; //maximum number of numbers in this last step
    array<ll,3> cnstr = {-1,-1,-1};
    for (ll n2=0;n2<=(min((ll)vcp2[2].size(),60LL));n2++) {
        for (ll n3=0;n3<=(min((ll)vcp2[3].size(),60LL));n3++) {
            for (ll n4=0;n4<=(min((ll)vcp2[4].size(),60LL));n4++) {
                vector<array<ll,3>> ti0; //{xc,T,P}
                ll Af = Ac;
                for (ll n=0;n<n2;n++) {
                    ti0.push_back({(12*vcp2[2][n].first),2,vcp2[2][n].first});
                }
                for (ll n=0;n<n3;n++) {
                    ti0.push_back({9*vcp2[3][n].first,3,vcp2[3][n].first});
                }
                for (ll n=0;n<n4;n++) {
                    ti0.push_back({8*vcp2[4][n].first,4,vcp2[4][n].first});
                }
                sort(ti0.begin(),ti0.end());
                bool bf = 0; //bool fail
                for (auto A0: ti0) {
                    Af = A0[1]*(Af-A0[2]);
                    if (Af<0) {
                        bf = 1; break;
                    }
                }
                if (bf==1) {
                    break; //should be faster than continue NGL: can prob eliminate
                }
                auto A0 = --m1c.upper_bound(Af);
                ll nctr = (*A0).second+n2+n3+n4;
                if (mnc<nctr) {
                    mnc = nctr;
                    cnstr = {n2,n3,n4};
                }
            }
        }
    }
    assert(mnc>=0);
    ll n2 = cnstr[0]; ll n3 = cnstr[1]; ll n4 = cnstr[2];
    vector<array<ll,4>> qi0; //{xc,T,P,idx}
    ll Af = Ac;
    for (ll n=0;n<n2;n++) {
        qi0.push_back({12*vcp2[2][n].first,2,vcp2[2][n].first,vcp2[2][n].second});
    }
    for (ll n=0;n<n3;n++) {
        qi0.push_back({9*vcp2[3][n].first,3,vcp2[3][n].first,vcp2[3][n].second});
    }
    for (ll n=0;n<n4;n++) {
        qi0.push_back({8*vcp2[4][n].first,4,vcp2[4][n].first,vcp2[4][n].second});
    }
    sort(qi0.begin(),qi0.end());
    for (auto A0: qi0) {
        Af = A0[1]*(Af-A0[2]);
        R.push_back(A0[3]);
        assert(Af>=0);
    }
    for (ll T=0;T<((ll)vcp2[1].size());T++) {
        if (Af>=vcp2[1][T].first) {
            Af -= vcp2[1][T].first;
            R.push_back(vcp2[1][T].second);
        }
    }
    return R;
}

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