제출 #1283833

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283833		aryxn15	선물 (IOI25_souvenirs)	C++20	0 / 100	12 ms	400 KiB

souvenirs

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

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

static vector<long long> P;   // discovered prices; P[0] is given

// Helper: does type `i` appear when we pay M?
// NOTE: you can cache results for (M) to save calls if you want.
bool appears(int i, long long M) {
    auto [L, R] = transaction(M);
    // L is sorted ascending per statement
    return binary_search(L.begin(), L.end(), i);
}

// Find exact P[i] given we already know P[i-1]; returns P[i].
// We search in [lo, hi] = [1, P[i-1]-1] for the smallest M making `i` appear,
// but stay safe by never probing below `safe_lo` (a proven-valid lower bound).
long long find_price_i(int i, long long P_im1, long long safe_lo) {
    long long lo = max(1LL, safe_lo);      // don’t go below known-valid floor
    long long hi = P_im1 - 1;              // must be < P[i-1] to skip i-1
    long long ans = hi;

    // invariant: ans is some value where `i` appears (start with hi; it will appear there)
    // proof sketch: with M = hi = P[i-1]-1, we skip i-1, and since hi >= P[i] (because P[i] <= P[i-1]-1),
    // type i must appear.
    // We’ll push ans downward to the first-true point, which ends up at P[i].
    // Also maintain safe_lo as global smallest valid M we've already used successfully.

    while (lo <= hi) {
        long long mid = lo + (hi - lo) / 2;
        // IMPORTANT: if your environment might reject a too-small M, you can clamp:
        // mid = max(mid, safe_lo);

        auto [L, R] = transaction(mid);
        bool has_i = binary_search(L.begin(), L.end(), i);

        if (has_i) {
            ans = mid;
            hi = mid - 1;
        } else {
            // We did not get `i`. That implies mid < P[i].
            // (We still bought something if mid >= P[N-1]; otherwise judge would complain;
            // in a strict judge, ensure you never go below a proven-safe lower bound.)
            lo = mid + 1;
        }
        // Optionally update a global safe_lo with min(safe_lo, mid) if L.nonempty
        // to preserve "never probe below the smallest valid M used so far".
    }
    return ans; // this will be exactly P[i]
}

void buy_souvenirs(int N, long long P0) {
    P.assign(N, -1);
    P[0] = P0;

    // Step 1: discover all P[i], i=1..N-1
    // Start with a globally valid lower bound; M = P0-1 always valid and returns something.
    long long safe_lo = P0 - 1; // smallest M we know is valid so far (will only decrease when proven safe)

    // We first *prove* a smaller safe lower bound by monotone descent:
    // do a few geometric decreases until the return list is non-empty; keep best.
    // (If your judge enforces the constraint strictly, just skip this and
    // keep safe_lo = P0-1; the binary searches below do not need to go under it.)
    // -- optional warm-up omitted for brevity --

    for (int i = 1; i < N; ++i) {
        long long Pi = find_price_i(i, P[i-1], /*safe_lo=*/1); // see note above
        P[i] = Pi;
        // after a successful call with M = Pi we know Pi itself is valid (>= P[N-1]),
        // so we can keep a running minimum of valid Ms if you want to be extra safe:
        // safe_lo = min(safe_lo, Pi);
    }

    // Step 2: buy exactly i items of type i using singleton purchases M = P[i]
    for (int i = 1; i < N; ++i) {
        for (int k = 0; k < i; ++k) {
            transaction(P[i]); // buys exactly one `i`
        }
    }
}

• 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