Submission #1273680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273680		lucas110550	Festival (IOI25_festival)	C++20	100 / 100	308 ms	139604 KiB

festival

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

struct Coupon {
    int idx;
    long long P;
    int T;
};

struct Node {
    __int128 token;   // tokens after processing this state
    int cnt;          // number of multipliers taken
    int prev;         // previous node id
    int couponIdx;    // original index of the coupon taken to reach here (-1 for start)
};

static const __int128 INF = (__int128)4'000'000'000'000'000'000LL; // sufficiently large

// comparator based on K = P*T/(T-1)
bool cmpCoupon(const Coupon& a, const Coupon& b) {
    if (a.T == 1 && b.T == 1) return a.idx < b.idx;
    if (a.T == 1) return false;          // a after b
    if (b.T == 1) return true;           // a before b
    // both T > 1
    __int128 left  = (__int128)a.P * a.T * (b.T - 1);
    __int128 right = (__int128)b.P * b.T * (a.T - 1);
    if (left != right) return left < right;
    return a.idx < b.idx;
}

// count of cheap coupons (T==1) we can afford with token X
int cheapCount(__int128 X,
               const vector<unsigned long long>& pref,
               unsigned long long totalCheapSum) {
    if (X <= 0) return 0;
    if (X >= ( __int128)totalCheapSum) return (int)pref.size() - 1;
    unsigned long long x = (unsigned long long)X;
    // pref[0]=0, pref[i] = sum of first i cheap coupons (i from 0..M)
    int pos = upper_bound(pref.begin(), pref.end(), x) - pref.begin() - 1;
    return pos;
}

std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
    int N = (int)P.size();
    vector<Coupon> all;
    all.reserve(N);
    for (int i = 0; i < N; ++i) {
        all.push_back({i, (long long)P[i], T[i]});
    }
    sort(all.begin(), all.end(), cmpCoupon);

    // split into multipliers (T>1) and cheap (T==1)
    vector<Coupon> mult;   // T>1
    vector<Coupon> cheap;  // T==1
    for (auto &c : all) {
        if (c.T == 1) cheap.push_back(c);
        else mult.push_back(c);
    }

    // cheap coupons: sort by price asc for later selection
    sort(cheap.begin(), cheap.end(),
         [](const Coupon& a, const Coupon& b){ return a.P < b.P; });

    vector<unsigned long long> cheapPref;
    cheapPref.push_back(0);
    for (auto &c : cheap) {
        cheapPref.push_back(cheapPref.back() + (unsigned long long)c.P);
    }
    unsigned long long totalCheapSum = cheapPref.back();

    // DP over multipliers
    vector<Node> nodes;
    nodes.reserve(500000);
    // start node
    nodes.push_back({ (__int128)A, 0, -1, -1 });
    vector<int> cur;           // ids of nondominated states
    cur.push_back(0);

    // best answer variables
    long long bestTotal = cheapCount((__int128)A, cheapPref, totalCheapSum);
    int bestNodeId = -1;   // -1 denotes using no multipliers
    __int128 bestToken = (__int128)A;

    for (size_t i = 0; i < mult.size(); ++i) {
        const Coupon& curC = mult[i];
        // map: cnt -> node id with maximal token for that cnt
        unordered_map<int,int> best;
        best.reserve(cur.size()*2 + 4);

        for (int nid : cur) {
            const Node& nd = nodes[nid];
            // skip this coupon
            auto it = best.find(nd.cnt);
            if (it == best.end() || nodes[it->second].token < nd.token)
                best[nd.cnt] = nid;

            // take this coupon if possible
            if (nd.token >= (__int128)curC.P) {
                __int128 newTok = (nd.token - (__int128)curC.P) * (__int128)curC.T;
                if (newTok > INF) newTok = INF;
                int newCnt = nd.cnt + 1;
                Node newNode{newTok, newCnt, nid, curC.idx};
                int newId = (int)nodes.size();
                nodes.push_back(newNode);
                auto it2 = best.find(newCnt);
                if (it2 == best.end() || nodes[it2->second].token < newTok)
                    best[newCnt] = newId;
            }
        }

        // collect and prune dominated states
        vector<pair<int,int>> vec;
        vec.reserve(best.size());
        for (auto &kv : best) vec.emplace_back(kv.first, kv.second);
        sort(vec.begin(), vec.end(),
             [](const pair<int,int>& a, const pair<int,int>& b){ return a.first < b.first; });

        cur.clear();
        __int128 bestTokenSeen = -1;
        for (int idx = (int)vec.size() - 1; idx >= 0; --idx) {
            int nid = vec[idx].second;
            __int128 tok = nodes[nid].token;
            if (tok > bestTokenSeen) {
                cur.push_back(nid);
                bestTokenSeen = tok;
            }
        }

        // update answer using current states
        for (int nid : cur) {
            const Node& nd = nodes[nid];
            int cheapCan = cheapCount(nd.token, cheapPref, totalCheapSum);
            long long total = (long long)nd.cnt + cheapCan;
            if (total > bestTotal) {
                bestTotal = total;
                bestNodeId = nid;
                bestToken = nd.token;
            }
        }
    }

    // also consider the case of using no multipliers (already handled)

    // reconstruct answer
    vector<int> answer;
    if (bestNodeId != -1) {
        // backtrack multiplier indices
        int curId = bestNodeId;
        while (curId != -1 && nodes[curId].couponIdx != -1) {
            answer.push_back(nodes[curId].couponIdx);
            curId = nodes[curId].prev;
        }
        reverse(answer.begin(), answer.end());
        // token after taking those multipliers
    } else {
        // no multipliers taken
        bestToken = (__int128)A;
    }

    // add cheap coupons (as many as possible)
    int cheapCan = cheapCount(bestToken, cheapPref, totalCheapSum);
    for (int i = 0; i < cheapCan; ++i) {
        answer.push_back(cheap[i].idx);
    }

    return answer;
}

• 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