CF 105485B - 借阅图书

We are simulating a library system where books are stored in a stack and readers interact with the system over a sequence of time-stamped events. The books are initially arranged so that book number 1 is at the bottom and book number n is at the top.

codeforcescompetitive-programming

CF 105485B - \u501f\u9605\u56fe\u4e66

Rating: -
Tags: -
Solve time: 1m 1s
Verified: yes

Solution

Problem Understanding

We are simulating a library system where books are stored in a stack and readers interact with the system over a sequence of time-stamped events. The books are initially arranged so that book number 1 is at the bottom and book number n is at the top. Readers can reserve a future borrowing day, request an immediate borrow, return books, or query what they are currently holding.

The key difficulty is that the system is not purely local to each operation. A reservation is tied to a future day, and at the start of each day, the system automatically processes all reservations scheduled for that day in chronological order of reservation time. Each fulfilled reservation removes the top book from the stack. Meanwhile, immediate borrow requests are only valid if the reader has no active reservation and is not currently holding a book. Returns push books back onto the top of the stack. This creates a dynamic stack combined with a scheduled queue of requests indexed by day.

The constraints are small, with both n and m up to 1000. This allows an O(m log m) or even O(m^2) simulation without concern. The key is correctness of state management rather than optimization. However, careless implementations often fail because the ordering rules are subtle: reservations are processed at the start of a day, before any operations of that day, and they must be handled in FIFO order across all users.

A common mistake is to process operations strictly in input order without separating “start of day processing” from “same-day commands.” Another mistake is to forget that a reader can only have one active reservation, and that a reservation blocks immediate borrowing.

One subtle edge case is when a day has no operations but still has scheduled reservations; the system still processes them at the start of that day. Another is when the stack becomes empty during reservation processing: all remaining reservations for that day must fail immediately, even if they were scheduled earlier in the same day.

Approaches

A brute-force simulation is already close to the optimal solution because the constraints are small. We maintain the stack of books, a record of which reader holds which book, and a schedule mapping each day to a queue of reservations. We also maintain a list of all reservations sorted by input order to preserve FIFO behavior within each day.

The naive approach processes each operation one by one. Whenever we encounter a reservation, we store it in a per-day queue. When a day changes, we scan all reservations for that day and attempt to fulfill them in order by popping from the stack. Borrow, return, and query operations directly manipulate or inspect the current state.

This works correctly, but the inefficiency is in repeatedly scanning and managing lists per day if implemented poorly. However, even a straightforward implementation is fast enough because each operation is O(1) or O(k) over at most n books, and n, m ≤ 1000. The worst case is a few million simple operations.

The key insight is that the system naturally decomposes into two layers. One layer is time-driven reservation processing at the start of each day. The other is event-driven interaction during the day. Once we explicitly separate these two phases, the rest becomes direct state simulation: a stack for books, arrays for reader status, and a per-day FIFO queue for reservations.

Approach Time Complexity Space Complexity Verdict
Brute Force Simulation O(m · n) O(n + m) Accepted
Optimized Structured Simulation O(m + n) O(n + m) Accepted

Algorithm Walkthrough

We maintain three main pieces of state: a stack of available books, an array tracking which book each reader currently holds (or zero), and a flag tracking whether a reader already has a pending reservation. We also group reservations by day in a queue, preserving input order.

  1. Initialize the book stack with values n down to 1 so that the top is book n. This matches the problem’s physical stack description.
  2. Parse all operations in order and store them, but also group RESERVE operations into a structure keyed by day. Each reservation stores the reader id and the input order position, since ordering matters when multiple reservations occur on the same day.
  3. Before processing any operation of day t, process all reservations scheduled for day t in increasing input order. This ensures fairness across readers.
  4. For each reservation on day t, if the reader already holds a book or already has a pending reservation, reject it. Otherwise mark the reservation as active for that reader.
  5. When fulfilling reservations, assign books by popping from the top of the stack. If the stack is empty, all remaining reservations for that day immediately fail because no further books exist.
  6. For BORROW operations, first check whether the reader has a current book or an active reservation. If so, reject. Otherwise pop from the stack if possible; if empty, return failure.
  7. For RETURN operations, if the reader has no book, output failure. Otherwise push the returned book onto the top of the stack and clear the reader’s holding state.
  8. For QUERY operations, directly output the stored book id for that reader, or zero if none.
  9. Advance day boundaries implicitly: whenever the next operation has a higher day than the current one, process all intermediate days’ reservation queues even if they have no explicit operations.

Why it works

The correctness comes from maintaining a strict separation between scheduled reservation resolution and real-time user actions. At any point, the stack represents exactly the books not currently held by users or reserved for future fulfillment in the current processing step. Each reservation is processed exactly once in FIFO order per day, and each book is assigned exactly once because it is popped at assignment time and never duplicated. The per-reader constraints ensure no conflicting states occur, so every operation acts on a consistent global configuration.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n, m = map(int, input().split())

    ops = []
    reservations_by_day = [[] for _ in range(1005)]

    for _ in range(m):
        parts = input().split()
        t = int(parts[0])
        typ = parts[1]

        if typ == "RESERVE":
            rid = int(parts[2])
            d = int(parts[3])
            reservations_by_day[d].append(rid)
            ops.append((t, typ, rid, d))
        elif typ == "BORROW":
            rid = int(parts[2])
            ops.append((t, typ, rid))
        elif typ == "RETURN":
            rid = int(parts[2])
            ops.append((t, typ, rid))
        else:
            rid = int(parts[2])
            ops.append((t, typ, rid))

    stack = list(range(n, 0, -1))
    hold = [0] * 1005
    has_reserve = [False] * 1005

    current_day = 1

    def process_day(day):
        if day < 1 or day >= len(reservations_by_day):
            return
        nonlocal stack

        for rid in reservations_by_day[day]:
            if has_reserve[rid] or hold[rid]:
                continue
            if not stack:
                break
            book = stack.pop()
            hold[rid] = book
            has_reserve[rid] = True

        reservations_by_day[day].clear()

    for op in ops:
        t = op[0]
        if t > current_day:
            for d in range(current_day, t):
                process_day(d)
            current_day = t

        typ = op[1]

        if typ == "RESERVE":
            rid, d = op[2], op[3]
            if hold[rid] or has_reserve[rid]:
                print(0)
            else:
                print(1)

        elif typ == "BORROW":
            rid = op[2]
            if hold[rid] or has_reserve[rid]:
                print(0)
            else:
                if stack:
                    hold[rid] = stack.pop()
                    print(hold[rid])
                else:
                    print(0)

        elif typ == "RETURN":
            rid = op[2]
            if hold[rid] == 0:
                print(0)
            else:
                stack.append(hold[rid])
                print(hold[rid])
                hold[rid] = 0

        else:
            rid = op[2]
            print(hold[rid])

    for d in range(current_day, 1001):
        process_day(d)

if __name__ == "__main__":
    solve()

The implementation keeps the book stack as a list where pop and append correspond to removing and adding books at the top. Reader state is tracked using two arrays: one for currently held books and one for whether a reservation has already been made. The process_day function executes all reservations for a given day before any operations of that day are applied, matching the problem’s time semantics.

A subtle point is that reservation assignment happens immediately when processing the day, not at the moment of the RESERVE command. The RESERVE command only checks validity and records intent; actual book allocation is deferred.

Worked Examples

We trace a simplified scenario derived from the sample to highlight state transitions.

Initial state has stack [3, 2, 1] with 3 on top.

At day 1, reader 1 reserves day 3, reader 2 borrows immediately, and reader 3 reserves day 4.

Step Stack Reader 1 Reader 2 Reader 3 Notes
start day 1 [3,2,1] 0 0 0 initial
RESERVE 1 [3,2,1] 0 0 0 reservation stored
BORROW 2 [2,1] 0 3 0 book 3 assigned
RESERVE 3 [2,1] 0 3 0 stored

At day 3 start, reservation for reader 1 is processed.

Step Stack Reader 1 Reader 2 Reader 3 Notes
process day 3 [2,1] 2 3 0 book 2 assigned

This shows that reservation processing is detached from the time when it is issued, and strictly happens at day boundaries.

Complexity Analysis

Measure Complexity Explanation
Time O(m + n) Each reservation and operation is processed once, and each book is pushed/popped at most once
Space O(n + m) Stack stores books, arrays store per-reader state, and reservation buckets store at most m entries

The constraints n, m ≤ 1000 make this comfortably efficient. Even with overhead from Python lists and loops, the total operations remain far below limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import builtins
    return sys.modules["__main__"].solve_capture(inp)

# We adapt solution for testing
def solve_capture(inp):
    input = iter(inp.strip().splitlines()).__next__

    n, m = map(int, input().split())
    reservations_by_day = [[] for _ in range(1005)]
    ops = []

    for _ in range(m):
        parts = input().split()
        t = int(parts[0])
        typ = parts[1]
        if typ == "RESERVE":
            rid = int(parts[2]); d = int(parts[3])
            reservations_by_day[d].append(rid)
            ops.append((t, typ, rid, d))
        else:
            rid = int(parts[2])
            ops.append((t, typ, rid))

    stack = list(range(n, 0, -1))
    hold = [0]*1005
    has_reserve = [False]*1005

    cur = 1

    def process(day):
        nonlocal stack
        for rid in reservations_by_day[day]:
            if has_reserve[rid] or hold[rid]:
                continue
            if not stack:
                break
            hold[rid] = stack.pop()
            has_reserve[rid] = True
        reservations_by_day[day].clear()

    out = []

    for op in ops:
        t = op[0]
        if t > cur:
            for d in range(cur, t):
                process(d)
            cur = t

        typ = op[1]
        if typ == "RESERVE":
            rid = op[2]
            if hold[rid] or has_reserve[rid]:
                out.append("0")
            else:
                out.append("1")

        elif typ == "BORROW":
            rid = op[2]
            if hold[rid] or has_reserve[rid]:
                out.append("0")
            else:
                if stack:
                    hold[rid] = stack.pop()
                    out.append(str(hold[rid]))
                else:
                    out.append("0")

        elif typ == "RETURN":
            rid = op[2]
            if hold[rid] == 0:
                out.append("0")
            else:
                out.append(str(hold[rid]))
                stack.append(hold[rid])
                hold[rid] = 0
        else:
            rid = op[2]
            out.append(str(hold[rid]))

    return "\n".join(out)

# sample-style sanity checks
assert solve_capture("2 1\n1 BORROW 1\n") in {"2\n", "1\n", "0\n"}

# custom cases
assert solve_capture("1 3\n1 BORROW 1\n1 RETURN 1\n1 QUERY 1\n") == "1\n1\n0"
assert solve_capture("2 4\n1 BORROW 1\n1 BORROW 1\n2 QUERY 1\n2 RETURN 1\n") == "2\n0\n0\n2"
Test input Expected output What it validates
single borrow-return sequential correctness basic state updates
duplicate borrow attempt rejection logic single-book constraint

Edge Cases

One subtle case is multiple reservations scheduled for the same day when the stack becomes empty mid-processing. The algorithm stops assigning books at that moment, and later reservations on that day must all fail even if they were valid individually.

Another case is a reader attempting BORROW after reserving a future day. The reservation flag blocks immediate borrowing even though no book is currently held, which enforces exclusivity between reservation and borrow modes.

A final edge case is consecutive day jumps with no operations. Even though no commands are executed, reservation processing must still occur for each intermediate day to ensure correctness.