Submission #1253539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253539		alex_2008	Souvenirs (IOI25_souvenirs)	C++20	7 / 100	12 ms	412 KiB

souvenirs

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

// Provided by the grader
extern pair<vector<int>, long long> transaction(long long M);

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

    auto buy = [&](long long M, vector<int>& got, long long& change){
        auto res = transaction(M);
        got = res.first;
        change = res.second;
    };

    // 1) Buy type 1 and deduce P1
    {
        vector<int> L; long long R;
        buy(P0 - 1, L, R);                 // must buy type 1
        P[1] = (P0 - 1) - R;
        cnt[1] += 1;
    }

    // 2) For i=2..N-1, call M = P[i-1]-1 to buy (and learn) type i
    for (int i = 2; i < N; ++i) {
        if (P[i] != -1) continue;          // might already be set by an edge case
        vector<int> L; long long R;
        long long M = P[i-1] - 1;
        buy(M, L, R);

        // L is either {i} or {i, i+1} in the only possible double-buy edge case
        if (!L.empty() && L[0] == i) {
            cnt[i] += 1;
            if (L.size() == 2 && L[1] == i+1) { // leftover==1 and P[i+1]==1
                P[i]   = (M - R) - 1;
                P[i+1] = 1;
                cnt[i+1] += 1;
            } else {
                P[i] = (M - R);
            }
        } else {
            // Should not happen under subtask-3 constraints; keep safe fallback
            // If we ever land here, we could binary-search with valid Ms,
            // but spec guarantees our M is >= P[i] and < P[i-1].
            // (Omitted for subtask-3, by design.)
        }
    }

    // 3) Top-up: for each i>=1, reach exactly i items using M = P[i]
    for (int i = 1; i < N; ++i) {
        while (cnt[i] < i) {
            vector<int> L; long long R;
            buy(P[i], L, R);               // spends exactly P[i], buys exactly type i
            cnt[i] += 1;
        }
    }
}

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