Submission #1252480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252480		NekoRolly	Festival (IOI25_festival)	C++20	20 / 100	82 ms	14520 KiB

festival

#include "festival.h"
#include<bits/stdc++.h>
using namespace std;

#define sz(x) int(x.size())

typedef long long ll;
typedef pair<ll,ll> pll;

struct coupon{
    ll p,t,id;
};

bool comp(coupon A,coupon B){ // *{P[i], T[i]}
    auto [p, a, ida] = A;
    auto [q, b, idb] = B;
    if (a == b) return p <= q;
    if (a == 1 || b == 1) return b == 1;
    return a*b*p + b*q <= a*b*q + a*p;
}

vector<int> max_coupons(int _A,vector<int> P,vector<int> T){
    int n = P.size(), max_t = 0;
    ll A = _A;
    coupon a[n];

    ll sum = 0;
    for (int i=0; i<n; i++){
        a[i] = {P[i], T[i], i};
        max_t = max(max_t, T[i]);
        sum += P[i];
    }

    sort(a, a+n, comp);
    vector<int> vans;

    if (max_t <= 2){
        vector<coupon> v1,v2;
        for (int i=0; i<n; i++){
            if (a[i].t == 1)
                v1.push_back(a[i]);
            else
                v2.push_back(a[i]);
        }

        int m = v1.size();
        ll pr[m];
        pr[0] = v1[0].p;
        for (int i=1; i<m; i++)
            pr[i] = pr[i-1] + v1[i].p;

        ll aux = A;
        int ans = 0, best=-1;
        for (int i=-1; i<n-m; i++){
            if (i != -1) A = 2*(A - v2[i].p);
            if (A < 0) break;
            if (A >= sum){
                for (int i=0; i<n; i++)
                    vans.push_back(a[i].id);
                return vans;
            }
            int val = i+1;
            val += upper_bound(pr, pr+m, A) - pr;
            if (ans <= val) ans = val, best = i;
        }

        A = aux;
        for (int i=0; i<=best; i++){
            vans.push_back(v2[i].id);
            A = 2*(A - v2[i].p);
        }

        for (int i=0; i<m; i++){
            if (A < v1[i].p) break;
            A -= v1[i].p;
            vans.push_back(v1[i].id);
        }

        return vans;
    }
    else if (n <= 70){
        vector<int> pos[5];
        for (int i=0; i<n; i++)
            pos[a[i].t].push_back(i);

        ll aux = A;
        for (int i2=0; i2<=sz(pos[2]); i2++)
            for (int i3=0; i3<=sz(pos[3]); i3++)
                for (int i4=0; i4<=sz(pos[4]); i4++){
                    int vis[n] = {0};
                    for (int i=0; i<i2; i++)
                        vis[pos[2][i]] = true;
                    for (int i=0; i<i3; i++)
                        vis[pos[3][i]] = true;
                    for (int i=0; i<i4; i++)
                        vis[pos[4][i]] = true;
                    for (int i : pos[1])
                        vis[i] = true;

                    vector<int> vec;
                    A = aux;
                    for (int i=0; i<n; i++){
                        if (!vis[i]) continue;
                        A = a[i].t*(A - a[i].p);
                        if (A < 0) break;
                        if (A >= sum){
                            for (; i<n; i++)
                                if (vis[i])
                                    vec.push_back(a[i].id);
                            break;
                        }
                        vec.push_back(a[i].id);
                    }

                    if (vans.size() < vec.size())
                        vans = vec;
                }

        return vans;
    }

    for (int i=0; i<n; i++)
        vans.push_back(a[i].id);

    return vans;
}

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