| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1283837 | aryxn15 | 선물 (IOI25_souvenirs) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
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`
}
}
}