Submission #1256391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256391		ro9669	Festival (IOI25_festival)	C++20	24 / 100	61 ms	9912 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define fi first
#define se second
using namespace std;

typedef long long ll;
typedef pair<int , int> ii;

int w; vector<int> p , t;

namespace sub1{
    const int maxN = int(2e5)+7;
    const ll inf = ll(1e18);

    bool check(){
        int n = sz(p);
        for (int i = 0 ; i < n ; i++){
            if (t[i] > 2) return false;
        }
        return true;
    }

    vector<ii> g[2];

    ll cost(ll cur , int i){
        ll tmp = cur - 1ll * p[i];
        if (tmp <= inf / t[i]) return 1ll * tmp * t[i]; else return inf;
    }

    ll S[maxN];

    int calc(ll x){
        int l = 0 , r = sz(g[0]) , ans = 0;
        while (l <= r){
            int mid = (l + r) / 2;
            if (x >= S[mid]){
                ans = mid;
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }
        return ans;
    }

    vector<int> solve(){
        int n = sz(p);
        for (int i = 0 ; i < n ; i++){
            g[t[i] - 1].push_back({p[i] , i});
        }
        sort(all(g[0])); sort(all(g[1]));
        S[0] = 0;
        for (int i = 0 ; i < sz(g[0]) ; i++){
            S[i + 1] = S[i] + 1ll * g[0][i].fi;
        }
        pair<int , int> res = {calc(w) , 0};
        ll cur = w;
        for (int i = 0 ; i < sz(g[1]) ; i++){
            if (cur > g[1][i].fi){
                cur = cost(cur , g[1][i].se);
                if (res.fi < i + 1 + calc(cur)){
                    res = {i + 1 + calc(cur) , i + 1};
                }
            }
        }
        vector<int> ans;
        for (int i = 0 ; i < res.se ; i++) ans.push_back(g[1][i].se);
        for (int i = 0 ; i < res.fi - res.se ; i++) ans.push_back(g[0][i].se);
        return ans;
    }
}

namespace sub5{
    vector<ii> g[4];

    vector<int> solve(){
        int n = sz(p);
        for (int i = 0 ; i < n ; i++){
            g[t[i] - 1].push_back({p[i] , i});
        }
        for (int i = 0 ; i < 4 ; i++){
            sort(all(g[i]));
        }
        vector<int> ans;
        for (int i = 3 ; i >= 0 ; i--){
            for (ii it : g[i]) ans.push_back(it.se);
        }
        return ans;
    }
}

vector<int> max_coupons(int W , vector<int> P , vector<int> T){
    w = W; p = P; t = T;
    if (sub1::check()) return sub1::solve();
    return sub5::solve();
}

// int main(){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//     freopen("templete.inp" , "r" , stdin);
//     freopen("templete.out" , "w" , stdout);
//     int n , W; cin >> n >> W;
//     vector<int> P(n) , T(n);
//     for (int &x : P) cin >> x;
//     for (int &x : T) cin >> x;
//     vector<int> ans = max_coupons(W , P , T);
//     cout << sz(ans) << "\n";
//     return 0;
// }

• 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