Submission #1256260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256260		nibert	Souvenirs (IOI25_souvenirs)	C++20	0 / 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);

static const long long INF = (1LL<<62);

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

    // Track how many of each type we've already bought (counts all queries).
    vector<long long> bought(N, 0);

    auto call = [&](long long M)->int {
        auto [L, R] = transaction(M);
        for (int t: L) bought[t]++;          // count all purchases
        if (L.empty()) return N;             // "none"
        return L[0];                         // first bought index
    };

    // Helper: do a safe call that buys at most one item when it hits index k.
    auto call_capped = [&](long long M, int k)->int {
        // If we know P[k+1], cap M so that after buying k, remainder < P[k+1].
        if (k+1 < N && P[k+1] > 0) {
            // Ensure M <= P[k] + P[k+1] - 1 when searching "in the zone".
            // We'll clamp downwards if needed (P[k] might still be unknown during search;
            // in that case we can't cap by it yet and just use M).
            if (P[k] > 0) {
                long long cap = P[k] + P[k+1] - 1;
                if (cap < M) M = cap;
            }
        }
        return call(M);
    };

    // ----- Phase A: recover all P[k], k = N-1..1 -----
    // We keep dynamic search bounds per k: [lo_k, hi_k] such that P[k] in [lo_k, hi_k].
    vector<long long> lo(N, 1), hi(N, P0-1);
    // Unknowns are P[1..N-1]. We'll find from bottom to top to learn P[k+1] first.
    // For k=N-1 initially we don't know hi; it's P[N-2]-1, but we can start with P0-1 safely.
    // We will progressively tighten using known neighbors.
    for (int k = N-1; k >= 1; --k) {
        // If we already know next and prev thresholds, shrink bounds.
        if (k+1 < N && P[k+1] > 0) lo[k] = max(lo[k], P[k+1] + 1);
        if (k-1 >= 1 && P[k-1] > 0) hi[k] = min(hi[k], P[k-1] - 1);
        // Binary search minimal M with f(M) <= k
        long long L = lo[k], R = hi[k];
        // Guard: ensure L<=R (it will be, but be safe)
        if (L < 1) L = 1;
        if (R >= P0) R = P0-1;

        // We’ll use standard binary search. To reduce extra buys,
        // when we detect f(M)==k we try to keep M <= P[k]+P[k+1]-1 once P[k] is known
        // (not known on first hits; it's okay).
        while (L < R) {
            long long mid = L + ((R - L) >> 1);
            int first = call(mid);  // single call; counts purchases
            if (first <= k) {
                R = mid;
            } else {
                L = mid + 1;
            }
        }
        // L=R is the minimal M where first<=k; this equals P[k].
        // Do one more call at M=L to also capture the remainder if you want (not necessary).
        // But we may have already called it as last 'mid'; if not, call it now.
        // We need the value P[k], not the items from the call. To avoid another call,
        // just set P[k]=L directly; correctness: by the monotonicity argument, the minimal M is exactly P[k].
        P[k] = L;
    }

    // ----- Phase B: top-up to exact targets with few calls -----
    // Target: T[0]=0, T[i]=i for i>=1
    for (int i = 1; i < N; ++i) {
        long long need = i - bought[i];
        while (need > 0) {
            // Buy exactly one item of type i.
            long long padBelow = (i+1 < N ? P[i+1]-1 : (P0-1 - P[i])); // safe tail pad
            if (padBelow < 0) padBelow = 0;
            long long M = P[i] + min(padBelow, P0-1 - P[i]); // ensure < P0
            // Edge case: if M < P[N-1] (very tiny), bump to P[N-1]
            if (M < P[N-1]) M = P[N-1];
            auto [L, R] = transaction(M);
            for (int t: L) bought[t]++;
            // Assert we bought exactly type i
            // (In a contest, you can assert and abort; here we just trust the construction.)
            need--;
        }
    }
}

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