Submission #1254710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254710		Yelarys	Souvenirs (IOI25_souvenirs)	C++20	3 / 100	12 ms	412 KiB

souvenirs

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

// ----- Judge-provided API (do not modify these signatures) -----
pair<vector<int>, long long> transaction(long long M);
void buy_souvenirs(int N, long long P0);

// ======================================================================
// If you want to test locally with the sample grader format, you can
// compile with -DLOCAL and provide a simple simulator below.
// Comment this whole LOCAL block out on the real judge.
// ======================================================================
#ifdef LOCAL
static int gN;
static vector<long long> gP; // true prices
static long long gP0;

pair<vector<int>, long long> transaction(long long M) {
    // Validate constraints
    long long P0 = gP[0];
    long long Pmin = gP.back();
    if (!(P0 > M && M >= Pmin)) {
        cerr << "Invalid argument in transaction: M=" << M << " P0=" << P0 << " Pmin=" << Pmin << "\n";
        exit(0);
    }
    long long pile = M;
    vector<int> L;
    for (int i = 0; i < gN; ++i) {
        if (pile >= gP[i]) {
            if (i == 0) { // should never happen since M < P0
                // no-op, but guard
            }
            pile -= gP[i];
            L.push_back(i);
        }
    }
    // The problem says L is returned in increasing order (we already add in increasing i)
    return {L, pile};
}

// A small local main for testing: reads full P, then runs our solution and prints counts.
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> gN;
    gP.resize(gN);
    for (int i = 0; i < gN; ++i) cin >> gP[i];
    gP0 = gP[0];

    // We'll wrap the counting by intercepting transaction calls:
    // Track counts per type as we go to print final answer like the sample grader expects.
    static vector<long long> buyCount;
    buyCount.assign(gN, 0);

    // Interpose transaction to count
    auto orig_transaction = transaction;
    function<pair<vector<int>, long long>(long long)> hooked = [&](long long M) {
        auto res = orig_transaction(M);
        for (int x : res.first) buyCount[x]++;
        return res;
    };

    // Replace the global function pointer (simulate by capturing lambda in a wrapper)
    // In this simple LOCAL harness, we just shadow the name via another function.
    // We'll provide a local alias and call that in buy_souvenirs_local.
    // To avoid refactoring, define a macro to redirect:
    #undef transaction
    #define transaction(M) hooked(M)

    buy_souvenirs(gN, gP0);

    for (int i = 0; i < gN; ++i) {
        if (i) cout << ' ';
        cout << buyCount[i];
    }
    cout << "\n";
    return 0;
}
#endif
// ======================================================================


// Helper: simulate a transaction for a *candidate* price array P with M
static pair<vector<int>, long long> simulate_with_P(const vector<long long>& Pcand, long long M) {
    long long pile = M;
    vector<int> L;
    int N = (int)Pcand.size();
    for (int i = 0; i < N; ++i) {
        if (pile >= Pcand[i]) {
            pile -= Pcand[i];
            L.push_back(i);
        }
    }
    return {L, pile};
}

void buy_souvenirs(int N, long long P0) {
    // Target counts: q[i] = i, and q[0] = 0
    vector<int> need(N, 0);
    for (int i = 1; i < N; ++i) need[i] = i;

    // Current counts (we'll update as we transact)
    vector<int> got(N, 0);

    // Build all candidate price sequences consistent with constraints:
    // P[0] = P0, strictly decreasing, each P[i] in [1..10], distinct.
    // So pick N-1 distinct numbers from [1..P0-1], sort descending, append P0 at front.
    vector<vector<long long>> candidates;
    vector<int> vals;
    for (int v = 1; v <= (int)P0 - 1; ++v) vals.push_back(v);
    // choose N-1 of these
    // we select combinations in descending order later
    int K = (int)vals.size();
    if (N - 1 > K) {
        // invalid input combo; but assume judge inputs are valid
    } else {
        vector<int> mask(K, 0);
        fill(mask.begin(), mask.begin() + (N - 1), 1);
        do {
            vector<int> pick;
            for (int i = 0; i < K; ++i) if (mask[i]) pick.push_back(vals[i]);
            sort(pick.begin(), pick.end(), greater<int>());
            vector<long long> P;
            P.reserve(N);
            P.push_back(P0);
            for (int x : pick) P.push_back(x);
            // ensure strictly decreasing
            bool ok = true;
            for (int i = 0; i + 1 < N; ++i) if (!(P[i] > P[i + 1])) ok = false;
            if (ok) candidates.push_back(P);
        } while (prev_permutation(mask.begin(), mask.end()));
    }

    // Known (agreed) prices (excluding P0 which is known)
    vector<long long> knownP(N, -1);
    knownP[0] = P0;

    auto recompute_agreed = [&]() {
        // For each i, if all candidates have same P[i], set knownP[i]
        for (int i = 1; i < N; ++i) {
            long long v = candidates[0][i];
            bool same = true;
            for (size_t c = 1; c < candidates.size(); ++c) {
                if (candidates[c][i] != v) { same = false; break; }
            }
            if (same) knownP[i] = v;
        }
    };

    recompute_agreed();

    auto all_done = [&]() {
        for (int i = 1; i < N; ++i) if (got[i] < need[i]) return false;
        return true;
    };

    // Helper: attempt to finish purchasing type i using known price
    auto finish_type_if_known = [&](int i) {
        if (i == 0) return;
        if (knownP[i] != -1) {
            int rem = need[i] - got[i];
            while (rem > 0) {
                auto [L, R] = transaction(knownP[i]); // buys exactly type i, once
                (void)R;
                for (int x : L) got[x]++;
                rem--;
            }
        }
    };

    // While we still have ambiguity or unfinished counts, keep going
    while (!all_done()) {
        // Finish any type whose price is known (and still has remaining need)
        bool progressed = false;
        for (int i = 1; i < N; ++i) {
            if (knownP[i] != -1 && got[i] < need[i]) {
                finish_type_if_known(i);
                progressed = true;
            }
        }
        if (all_done()) break;
        // Check if all prices known
        bool all_prices_known = true;
        for (int i = 1; i < N; ++i) if (knownP[i] == -1) { all_prices_known = false; break; }
        if (all_prices_known) {
            // Just finish any leftovers
            for (int i = 1; i < N; ++i) finish_type_if_known(i);
            break;
        }

        // Choose a SAFE M (valid for all remaining candidates) that:
        //  (1) doesn't exceed remaining capacities for any candidate,
        //  (2) splits candidates as much as possible.
        long long lowerSafe = 0;
        for (auto &Pc : candidates) lowerSafe = max(lowerSafe, Pc.back()); // max Pmin among candidates
        long long upperSafe = P0 - 1;

        // Precompute candidate outputs per M and whether they are capacity-safe
        struct Key {
            vector<int> L;
            long long R;
            bool operator<(Key const& o) const {
                if (R != o.R) return R < o.R;
                return L < o.L;
            }
        };

        long long bestM = -1;
        int bestDiversity = -1;

        for (long long M = lowerSafe; M <= upperSafe; ++M) {
            bool capacity_ok = true;
            map<Key, int> bucket;
            for (auto &Pc : candidates) {
                auto [L, R] = simulate_with_P(Pc, M);
                // capacity check: this transaction should not cause any got[i] to exceed need[i]
                bool ok_for_this_candidate = true;
                // NOTE: Type 0 must never be included since M < P0; simulation respects that.
                for (int i : L) {
                    if (got[i] + 1 > need[i]) { ok_for_this_candidate = false; break; }
                }
                if (!ok_for_this_candidate) { capacity_ok = false; break; }
                bucket[{L, R}]++;
            }
            if (!capacity_ok) continue;

            int diversity = (int)bucket.size();
            if (diversity > bestDiversity) {
                bestDiversity = diversity;
                bestM = M;
            }
        }

        if (bestM == -1) {
            // No safe discriminating M found that respects capacities.
            // Fall back: try to *force* agreement by finishing any single type whose price
            // is agreed (if any remaining). If none, pick the smallest i with the smallest
            // agreed price across candidates (they must agree on some price eventually).
            // In practice with tiny domains, there will be an agreed price quickly. But just in case:
            bool did_any = false;
            recompute_agreed();
            for (int i = 1; i < N; ++i) {
                if (knownP[i] != -1 && got[i] < need[i]) {
                    finish_type_if_known(i);
                    did_any = true;
                }
            }
            if (did_any) continue;

            // As a last resort: pick an i such that *all candidates* have the same P[i]
            // (this is what knownP tracks); if none exist (extremely unlikely here), just
            // pick M = lowerSafe to continue; capacity shouldn’t be violated since we already tried.
            for (int i = 1; i < N; ++i) {
                if (knownP[i] != -1 && got[i] < need[i]) {
                    finish_type_if_known(i);
                    did_any = true;
                    break;
                }
            }
            if (did_any) continue;

            // If still stuck, just transact at lowerSafe once (it’s valid),
            // but **guard** to ensure no capacity overflow in the actual result.
            auto [L, R] = transaction(lowerSafe);
            bool real_ok = true;
            for (int x : L) if (got[x] + 1 > need[x]) real_ok = false;
            if (!real_ok) {
                // Should not happen under constraints/logic above.
                // To be safe, do a known price if any (even if none earlier).
                // Find the smallest i where all candidates have the same P[i].
                recompute_agreed();
                bool did = false;
                for (int i = 1; i < N; ++i) {
                    if (knownP[i] != -1 && got[i] < need[i]) {
                        finish_type_if_known(i);
                        did = true;
                        break;
                    }
                }
                if (!did) {
                    // As absolute fallback (shouldn’t be reached), pick the smallest i that still has room
                    // and use the *minimum* possible price among candidates for that i (guaranteed >= Pmin)
                    // so M will be valid. This preserves safety; it might not discriminate candidates well,
                    // but we’ll keep moving and stay within capacities.
                    int target = -1;
                    for (int i = 1; i < N; ++i) if (got[i] < need[i]) { target = i; break; }
                    long long m_guess = LLONG_MAX;
                    for (auto &Pc : candidates) m_guess = min(m_guess, Pc[target]);
                    auto [L2, R2] = transaction(m_guess);
                    for (int x : L2) got[x]++;
                    // filter candidates
                    vector<vector<long long>> next;
                    for (auto &Pc : candidates) {
                        auto [LL, RR] = simulate_with_P(Pc, m_guess);
                        if (LL == L2 && RR == R2) next.push_back(Pc);
                    }
                    candidates.swap(next);
                    recompute_agreed();
                    continue;
                }
                continue;
            } else {
                for (int x : L) got[x]++;
                // filter candidates by the real observation we just made
                vector<vector<long long>> next;
                for (auto &Pc : candidates) {
                    auto [LL, RR] = simulate_with_P(Pc, lowerSafe);
                    if (LL == L && RR == R) next.push_back(Pc);
                }
                candidates.swap(next);
                recompute_agreed();
                continue;
            }
        }

        // Perform the chosen bestM, update counts, and filter candidates
        auto [Lreal, Rreal] = transaction(bestM);
        for (int x : Lreal) got[x]++;

        vector<vector<long long>> next;
        for (auto &Pc : candidates) {
            auto [LL, RR] = simulate_with_P(Pc, bestM);
            if (LL == Lreal && RR == Rreal) next.push_back(Pc);
        }
        candidates.swap(next);
        recompute_agreed();
    }

    // If anything left (shouldn’t be), finish with known prices
    for (int i = 1; i < N; ++i) {
        while (got[i] < need[i]) {
            long long M = knownP[i];
            if (M == -1) {
                // if somehow unknown, pick it from the (now tiny) candidate set
                M = candidates[0][i];
                knownP[i] = M;
            }
            auto [L, R] = transaction(M);
            (void)R;
            for (int x : L) got[x]++;
        }
    }
}

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