제출 #1276452

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276452		mehrzad	Festival (IOI25_festival)	C++20	51 / 100	106 ms	16168 KiB

festival

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

struct MultiCoupon {
    long long P;          // price
    int T;                // type (>1)
    int idx;              // original index
    long long S_num;      // Pi * Ti
    int S_den;            // Ti - 1
};

class SegTree {
    const vector<MultiCoupon>* arr;
    int n;
    vector<int> tree;   // stores index of best coupon, -1 means empty

    // compare two indices, return the better (smaller S, then smaller T, then smaller price)
    int better(int i, int j) const {
        if (i == -1) return j;
        if (j == -1) return i;
        const MultiCoupon& a = (*arr)[i];
        const MultiCoupon& b = (*arr)[j];
        __int128 lhs = (__int128)a.S_num * b.S_den;
        __int128 rhs = (__int128)b.S_num * a.S_den;
        if (lhs != rhs) return lhs < rhs ? i : j;          // smaller S
        if (a.T != b.T) return a.T < b.T ? i : j;        // smaller multiplier is better (less loss when S equal)
        if (a.P != b.P) return a.P < b.P ? i : j;        // smaller price
        return i;                                          // arbitrary
    }

    void build(int node, int l, int r) {
        if (l == r) {
            tree[node] = l;
            return;
        }
        int mid = (l + r) >> 1;
        build(node << 1, l, mid);
        build(node << 1 | 1, mid + 1, r);
        tree[node] = better(tree[node << 1], tree[node << 1 | 1]);
    }

    int query(int node, int l, int r, int ql, int qr) const {
        if (qr < l || r < ql) return -1;
        if (ql <= l && r <= qr) return tree[node];
        int mid = (l + r) >> 1;
        int left = query(node << 1, l, mid, ql, qr);
        int right = query(node << 1 | 1, mid + 1, r, ql, qr);
        return better(left, right);
    }

    void update(int node, int l, int r, int pos, int val) {
        if (l == r) {
            tree[node] = val;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) update(node << 1, l, mid, pos, val);
        else update(node << 1 | 1, mid + 1, r, pos, val);
        tree[node] = better(tree[node << 1], tree[node << 1 | 1]);
    }

public:
    SegTree() : arr(nullptr), n(0) {}
    explicit SegTree(const vector<MultiCoupon>* a) : arr(a) {
        n = (int)arr->size();
        if (n) {
            tree.assign(4 * n, -1);
            build(1, 0, n - 1);
        }
    }

    // query best index in [l,r]; returns -1 if none
    int query(int l, int r) const {
        if (n == 0 || l > r) return -1;
        return query(1, 0, n - 1, l, r);
    }

    // remove index pos (mark as unavailable)
    void remove(int pos) {
        if (n == 0) return;
        update(1, 0, n - 1, pos, -1);
    }
};

std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
    const long long INF = (long long)4e18;   // large enough sentinel

    int N = (int)P.size();

    // separate coupons
    vector<MultiCoupon> mult;                 // T > 1
    vector<pair<long long,int>> cheap;        // T == 1  (price , index)

    for (int i = 0; i < N; ++i) {
        if (T[i] == 1) {
            cheap.emplace_back(P[i], i);
        } else {
            MultiCoupon c;
            c.P = P[i];
            c.T = T[i];
            c.idx = i;
            c.S_num = (long long)P[i] * T[i];
            c.S_den = T[i] - 1;
            mult.push_back(c);
        }
    }

    // sort cheap coupons by price and build prefix sums
    sort(cheap.begin(), cheap.end(),
         [](const pair<long long,int>& a, const pair<long long,int>& b){
             return a.first < b.first;
         });
    int C = (int)cheap.size();
    vector<long long> cheapPref(C+1, 0);
    for (int i = 0; i < C; ++i) cheapPref[i+1] = cheapPref[i] + cheap[i].first;

    auto cheapCount = [&](long long tokens)->int{
        // maximum number of cheap coupons we could afford (price-sum <= tokens)
        int pos = (int)(upper_bound(cheapPref.begin(), cheapPref.end(), tokens) - cheapPref.begin() - 1);
        return pos; // 0 .. C
    };

    // sort mult coupons by price (needed for binary search on affordability)
    sort(mult.begin(), mult.end(),
         [](const MultiCoupon& a, const MultiCoupon& b){
             return a.P < b.P;
         });
    int M = (int)mult.size();
    vector<long long> multPrice(M);
    for (int i = 0; i < M; ++i) multPrice[i] = mult[i].P;

    // segment tree over mult to retrieve coupon with minimal S among a price prefix
    SegTree seg(&mult);

    vector<int> answer;
    long long cur = A;

    while (true) {
        // find rightmost index whose price <= cur
        int r = -1;
        if (M > 0) {
            auto it = upper_bound(multPrice.begin(), multPrice.end(), cur);
            r = (int)(it - multPrice.begin()) - 1;
        }
        if (r < 0) break;                     // no mult coupon affordable

        int bestIdx = seg.query(0, r);
        if (bestIdx == -1) break;              // all affordable mult coupons already taken

        const MultiCoupon& c = mult[bestIdx];

        // compute new token amount after taking this coupon
        __int128 tmp = (__int128)(cur - c.P) * c.T;
        long long newCur = (tmp > INF) ? INF : (long long)tmp;

        // counts of cheap coupons before and after this move
        int cheapNow = cheapCount(cur);
        int cheapAfter = cheapCount(newCur);

        if (newCur >= cur) { // net‑positive (or neutral)
            answer.push_back(c.idx);
            cur = newCur;
            seg.remove(bestIdx);
            continue;
        } else {
            if (cheapAfter >= cheapNow - 1) {
                // taking it does not reduce the total possible coupons
                answer.push_back(c.idx);
                cur = newCur;
                seg.remove(bestIdx);
                continue;
            } else {
                // would lose more than one cheap coupon – stop taking mult coupons
                break;
            }
        }
    }

    // finally take cheap coupons (type 1) in order of increasing price
    int pos = 0;
    while (pos < C && cheap[pos].first <= cur) {
        cur -= cheap[pos].first;
        answer.push_back(cheap[pos].second);
        ++pos;
    }

    return answer;
}

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