Submission #1250252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250252		gptopenai	Souvenirs (IOI25_souvenirs)	C++20	0 / 100	0 ms	400 KiB

souvenirs

#include "souvenirs.h"
#include <vector>
#include <algorithm>
#include <numeric>
#include <cassert>
using namespace std;

// transaction(M) ↦ { list of bought types in increasing order, remainder }

// 1) Learn P[1..N-1] by binary search with offset-sums.
//    We maintain prefix-sum S = sum_{j< i} P[j].  To test P[i], we
//    hand M = S + mid.  Because mid < P[i-1], the seller will first
//    remove exactly P[1],…,P[i-1], leaving mid in the pile, so the
//    only possible purchase is type i.  Checking its presence tells us
//    whether mid >= P[i].

// 2) Build a list of required items: i copies of price P[i] (for i=1..N-1).
//    Do a first-fit‐decreasing pack into bins of capacity P0-1, disallowing
//    two of the same type in one bin.  Each bin becomes one transaction
//    (hand exactly the sum of its weights) and buys exactly those types.

void buy_souvenirs(int N, long long P0) {
    vector<long long> P(N);
    P[0] = P0;

    // --- 1) Learn all P[i] ---
    long long prefixSum = 0;
    for (int i = 1; i < N; i++) {
        long long lo = 1, hi = P[i-1] - 1;
        // binary search P[i] in [1 .. P[i-1]-1]
        while (lo < hi) {
            long long mid = (lo + hi) >> 1;
            auto res = transaction(prefixSum + mid);
            const auto &bought = res.first;
            // did we buy type i?
            bool got = binary_search(bought.begin(), bought.end(), i);
            if (got) {
                // mid >= P[i]
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        P[i] = lo;
        prefixSum += P[i];
    }

    // --- 2) Pack i copies of price P[i] into bins ---
    struct Bin {
        long long rem;
        vector<bool> used;  // used[type] = true once that type is in this bin
        Bin(long long cap, int N): rem(cap), used(N,false) {}
    };
    vector<Bin> bins;
    // Build a list of (type,weight) entries
    vector<pair<int,long long>> items;
    for (int i = 1; i < N; i++) {
        for (int cnt = 0; cnt < i; cnt++) {
            items.emplace_back(i, P[i]);
        }
    }
    // Sort by descending weight so FFD works best
    sort(items.begin(), items.end(),
         [&](auto &a, auto &b){ return a.second > b.second; });

    // First-fit: for each item, try each bin, else open new
    for (auto &it : items) {
        int t = it.first;
        long long w = it.second;
        bool placed = false;
        for (auto &B : bins) {
            if (!B.used[t] && B.rem >= w) {
                B.used[t] = true;
                B.rem -= w;
                placed = true;
                break;
            }
        }
        if (!placed) {
            bins.emplace_back(P0-1, N);
            bins.back().used[t] = true;
            bins.back().rem -= w;
        }
    }

    // 3) Finally, for each bin, hand exactly (P0-1 - rem) coins,
    //    which is the sum of its selected weights.
    for (auto &B : bins) {
        long long M = (P0 - 1) - B.rem;
        auto res = transaction(M);
        // we ignore the result vector here; it must match exactly our
        // chosen set for this bin by construction.
    }
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 4
• Subtask 2: 0 / 3
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 0 / 28
• Subtask 6: 0 / 33