Submission #1256261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256261		nibert	Souvenirs (IOI25_souvenirs)	C++20	4 / 100	0 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);
    P[0] = P0;

    vector<long long> bought(N, 0);

    auto do_call = [&](long long M) -> int {
        auto [L, R] = transaction(M);
        for (int t: L) bought[t]++;
        return L.empty() ? N : L[0];
    };

    // GLOBAL valid lower bound: all calls must have M >= LB.
    long long LB = P0 - 1;            // guaranteed >= P[N-1]
    // Make one call to record purchases and confirm LB is valid (optional but helpful).
    // (Uncomment if you want at least one data point)
    // do_call(LB);

    // Tight per-index search windows; they must always include LB.
    vector<long long> lo(N, -1), hi(N, P0 - 1);
    for (int k = N - 1; k >= 1; --k) {
        // Set the best-known window using neighbors we may have already found
        long long L = max(LB, (k + 1 < N && P[k + 1] != -1) ? P[k + 1] + 1 : LB);
        long long R = (k - 1 >= 1 && P[k - 1] != -1) ? min(hi[k], P[k - 1] - 1) : hi[k];

        // Safe binary search: mid is always in [LB, R].
        while (L < R) {
            long long mid = L + ((R - L) >> 1);
            // Ensure mid is within [LB, P0-1]
            if (mid < LB) mid = LB;
            int first = do_call(mid);          // ALWAYS valid: mid >= LB
            if (first <= k) {
                R = mid;
            } else {
                L = mid + 1;
            }
            // Any M we just called is valid; if it’s smaller than LB, promote LB down.
            if (mid < LB) LB = mid;           // (redundant due to guard)
            if (L < LB) L = LB;               // keep L >= LB
        }
        P[k] = L;                              // minimal M with first <= k is exactly P[k]
        // After discovering a new smaller valid M (=P[k]), we can lower LB to it.
        if (P[k] < LB) LB = P[k];
    }

    // Phase B: top-up to exact targets T[i] = i (and T[0] = 0), without buying extras
    for (int i = 1; i < N; ++i) {
        long long need = i - bought[i];
        while (need-- > 0) {
            // Buy exactly one i: choose M so higher types can't be bought, and
            // remainder after buying i is < P[i+1] (or no i+1).
            long long headRoom = (i - 1 >= 1 ? P[i - 1] - 1 : P0 - 1);
            long long tailCap  = (i + 1 <  N ? P[i + 1] - 1 : (P0 - 1 - P[i]));
            long long M = P[i] + max(0LL, min(tailCap, headRoom - P[i]));
            if (M < LB) M = LB;               // keep it valid
            auto [Lvec, R] = transaction(M);
            for (int t: Lvec) bought[t]++;
        }
    }
}

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