Submission #1274814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274814		mehrzad	선물 (IOI25_souvenirs)	C++20	100 / 100	13 ms	400 KiB

souvenirs

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

struct Equation {
    vector<int> L;   // indices of bought types
    long long sum;   // M - R  = Σ_{i∈L} P[i]
};

void buy_souvenirs(int N, long long P0) {
    // ------------------------------------------------------------
    // data
    vector<long long> price(N, -1);       // unknown -> -1, price[0] known
    price[0] = P0;

    vector<int> need(N, 0);               // need[i] = i
    for (int i = 0; i < N; ++i) need[i] = i;
    vector<int> have(N, 0);               // already bought copies

    vector<Equation> eqs;                 // all equations obtained

    long long UB = P0 - 1;                // safe upper bound for the cheapest unknown

    // ------------------------------------------------------------
    // Phase A – discover all prices
    while (true) {
        bool allKnown = true;
        for (int i = 1; i < N; ++i)
            if (price[i] == -1) { allKnown = false; break; }
        if (allKnown) break;                      // finished

        // ----- perform a safe transaction -----
        auto res = transaction(UB);
        const vector<int> &L = res.first;
        long long R = res.second;

        // update bought counters
        for (int idx : L) {
            // type 0 must never appear, but we ignore it if it does
            if (idx == 0) continue;
            ++have[idx];
        }

        long long sum = UB - R;                    // Σ P[i] of the bought types
        eqs.push_back({L, sum});

        // ----- try to deduce new prices -----
        bool changed = true;
        while (changed) {
            changed = false;
            for (auto &e : eqs) {
                long long knownSum = 0;
                int unknownCnt = 0;
                int unknownIdx = -1;
                for (int idx : e.L) {
                    if (price[idx] != -1) knownSum += price[idx];
                    else {
                        ++unknownCnt;
                        unknownIdx = idx;
                    }
                }
                if (unknownCnt == 1) {
                    long long val = e.sum - knownSum;
                    if (price[unknownIdx] == -1) {
                        price[unknownIdx] = val;
                        changed = true;
                    }
                }
            }
        }

        // ----- compute a new safe upper bound -----
        long long newUB = P0 - 1;                  // start with a trivial bound

        // from equations (average of still unknown part)
        for (const auto &e : eqs) {
            long long knownSum = 0;
            int unknownCnt = 0;
            for (int idx : e.L) {
                if (price[idx] != -1) knownSum += price[idx];
                else ++unknownCnt;
            }
            if (unknownCnt > 0) {
                long long cand = (e.sum - knownSum) / unknownCnt;
                if (cand < newUB) newUB = cand;
            }
        }

        // from already known, more expensive prices
        int maxUnknown = -1;                       // largest index still unknown
        for (int i = N - 1; i >= 1; --i)
            if (price[i] == -1) { maxUnknown = i; break; }

        if (maxUnknown != -1) {
            for (int i = 1; i < maxUnknown; ++i)   // more expensive known prices
                if (price[i] != -1) {
                    long long cand = price[i] - 1;
                    if (cand < newUB) newUB = cand;
                }
        }

        if (newUB < 1) newUB = 1;                 // never zero
        UB = newUB;
    }

    // ------------------------------------------------------------
    // Phase B – buy the remaining copies (now all prices are known)
    for (int i = 1; i < N; ++i) {
        while (have[i] < need[i]) {
            // one copy of type i
            transaction(price[i]);    // the returned list must be {i}, R = 0
            ++have[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