Submission #1273678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273678		lucas110550	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	13 ms	400 KiB

souvenirs

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

const int MAXN = 105;          // N ≤ 100

struct Equation {
    bitset<MAXN> mask;   // unknown indices (0‑based for types 1..N‑1)
    long long rhs;       // sum of their prices
};

int N_;
long long P0_;

vector<long long> price;          // -1 while unknown, size N (0..N‑1)
vector<int> bought;               // how many copies we already have
vector<Equation> eqs;             // linear equations for unknowns

/*---------------------------------------------------------------*/

static long long min_unknown_higher_price(int idx)   // smallest known price among types < idx, -1 if none
{
    long long best = -1;
    for (int i = 0; i < idx; ++i) {
        if (price[i] != -1) {
            if (best == -1 || price[i] < best) best = price[i];
        }
    }
    return best;                 // -1 means “none known”
}

/* try to solve all equations that became singletons */
static void reduce_system() {
    bool changed = true;
    while (changed) {
        changed = false;
        for (size_t e = 0; e < eqs.size(); ++e) {
            if (eqs[e].mask.none()) continue;
            if (eqs[e].mask.count() == 1) {
                int idx = (int)eqs[e].mask._Find_first();   // index 0..N-2  (type = idx+1)
                long long val = eqs[e].rhs;
                if (price[idx] == -1) {
                    price[idx] = val;
                }
                // substitute into all equations
                for (size_t k = 0; k < eqs.size(); ++k) {
                    if (eqs[k].mask[idx]) {
                        eqs[k].rhs -= val;
                        eqs[k].mask.reset(idx);
                    }
                }
                // also subtract from bought counts –
                // the copy obtained in the transaction that gave this equation
                // has already been counted when the transaction was processed.
                eqs[e].mask.reset();   // make it empty
                changed = true;
            }
        }
    }
}

/*---------------------------------------------------------------*/

void buy_souvenirs(int N, long long P0) {
    N_ = N;
    P0_ = P0;

    price.assign(N, -1);          // price[0] is known (P0), others -1
    price[0] = P0;
    bought.assign(N, 0);          // counts for all types, we never buy type 0

    // ---------- discovery phase ----------
    // start with a safe upper bound for the cheapest unknown price
    long long UB_initial = P0 - (N - 1);          // Lemma 1

    // we will repeat until all prices (1..N-1) are known
    while (true) {
        bool all_known = true;
        for (int i = 1; i < N; ++i) if (price[i] == -1) { all_known = false; break; }
        if (all_known) break;

        // 1) compute an upper bound for the smallest unknown price
        long long bound1 = (long long)4e18;   // INF
        // find the smallest known price among indices smaller than the current smallest unknown
        int smallest_unknown = -1;
        for (int i = N - 1; i >= 1; --i) if (price[i] == -1) { smallest_unknown = i; break; }
        long long higher = min_unknown_higher_price(smallest_unknown);
        if (higher != -1) bound1 = higher - 1;          // must be < any more expensive known price

        long long bound2 = (long long)4e18;
        for (auto &eq : eqs) {
            if (eq.mask.none()) continue;
            long long cnt = (long long)eq.mask.count();
            long long cand = eq.rhs / cnt;   // floor
            if (cand < bound2) bound2 = cand;
        }

        long long UB = min(bound1, bound2);
        if (UB == (long long)4e18) UB = UB_initial;    // fallback, should not happen

        // 2) perform the transaction
        auto resp = transaction(UB);
        const vector<int> &L = resp.first;
        long long R = resp.second;
        long long sum = UB - R;          // Σ P[t] over all bought types

        // 3) update data structures
        bitset<MAXN> curMask;
        for (int t : L) {
            ++bought[t];                 // we obtained one copy of this type
            int idx = t;                 // type number = index (0..N-1)
            if (idx == 0) continue;     // we never get type 0 because M < P0
            if (price[idx] != -1) {
                sum -= price[idx];       // known contribution
            } else {
                curMask.set(idx);
            }
        }

        if (curMask.any()) {
            Equation ne;
            ne.mask = curMask;
            ne.rhs = sum;
            eqs.push_back(ne);
        }

        // 4) try to solve singletons that appeared
        reduce_system();
    }

    // ---------- finishing purchases ----------
    for (int i = 1; i < N; ++i) {
        int need = i - bought[i];
        for (int k = 0; k < need; ++k) {
            transaction(price[i]);      // buys exactly one copy of type i
        }
    }
}

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