제출 #1269491

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269491		SamAnd	축제 (IOI25_festival)	C++20	27 / 100	89 ms	20636 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 200005;
const ll INF = 200005000000009;

struct ban
{
    int i;
    ll p, t;
};
ll F(ll A, const ban& u)
{
    return (A - u.p) * u.t;
}
bool operator<(const ban& a, const ban& b)
{
    return F(F(0, a), b) < F(F(0, b), a);
}

std::vector<int> max_coupons(int aa, std::vector<int> P, std::vector<int> T)
{
    int n;
    n = sz(P);

    vector<pair<ll, ban> > v;
    for (int i = 0; i < n; ++i)
    {
        ban u;
        u.p = P[i];
        u.t = T[i];
        u.i = i;
        if (u.t == 1)
            v.push_back(m_p(INF, u));
        else
        {
            ll x = u.p * u.t;
            if (x % (u.t + 1) == 0)
                x /= (u.t + 1);
            else
            {
                x /= (u.t + 1);
                ++x;
            }
            v.push_back(m_p(x, u));
        }
    }
    sort(all(v));
    reverse(all(v));

    priority_queue<ban> q;
    ll A = aa;
    vector<int> ans;
    while (1)
    {
        while (!v.empty() && A >= v.back().fi)
        {
            q.push(v.back().se);
            v.pop_back();
        }
        if (q.empty())
            break;
        ban u = q.top();
        q.pop();
        A = min(INF, (A - u.p) * u.t);
        ans.push_back(u.i);
    }

    for (int i = sz(v) - 1; i >= 0; --i)
        swap(v[i], v[rnd() % (i + 1)]);

    for (int i = 0; i < sz(v); ++i)
        ans.push_back(v[i].se.i);
    return ans;
}

/*
4 13
4 1
500 3
8 3
14 4
*/

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