Submission #1273664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273664		lucas110550	Souvenirs (IOI25_souvenirs)	C++20	22 / 100	1 ms	388 KiB

souvenirs

#include "souvenirs.h"
#include <vector>
#include <utility>

void buy_souvenirs(int N, long long P0) {
        // N = 3 in the official tests.
        // For completeness we also handle N = 1 and N = 2.
        if (N == 1) {
                // Need 0 souvenirs of type 0 → do nothing.
                return;
        }
        if (N == 2) {
                // Need exactly one souvenir of type 1.
                // A single transaction with M = P0 - 1 always buys type 1
                // (and never type 0 because M < P0).
                long long M = P0 - 1;
                transaction(M);
                return;
        }

        // ----------- N == 3 ---------------------------------
        // First transaction: M = P0 - 1.
        // It always buys at least one souvenir of type 1.
        long long M0 = P0 - 1;
        auto first = transaction(M0);
        std::vector<int> L0 = first.first;        // types bought in this transaction
        long long   R0 = first.second;            // coins returned

        // Does the first transaction already give us a souvenir of type 2 ?
        bool got_type2 = false;
        for (int t : L0) if (t == 2) { got_type2 = true; break; }

        if (got_type2) {
                // We have bought 1 of type 1 and 1 of type 2.
                // Need one more type 2.  Compute P1 + P2.
                long long sum0 = M0 - R0;                 // = P1 + P2
                long long M2 = sum0 / 2;                   // floor((P1+P2)/2)
                // M2 is < P1 and ≥ P2, therefore the seller will give us exactly one type 2.
                transaction(M2);
                // Now we have 1×type 1 and 2×type 2 → done.
        } else {
                // Only type 1 was bought.  We need two type 2.
                // From the first transaction we already know P1.
                long long sum0 = M0 - R0;                 // = P1
                long long P1 = sum0;
                long long Mtype2 = P1 - 1;               // ≥ P2 and < P1
                // Buy type 2 twice.
                transaction(Mtype2);
                transaction(Mtype2);
                // Now we have 1×type 1 and 2×type 2 → done.
        }
}

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