Design and implement an `EscapeRoomGame` for a fixed set of players and rooms `0` through `R`. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Design and implement an `EscapeRoomGame` for a fixed set of players and rooms `0` through `R`.
- `advance(player_id)` moves that player forward by one room in `O(1)`. A player already in room `R` remains there.
- `get_room(player_id)` returns the current room in `O(1)`.
- `leaderboard(k)` returns up to `k` player IDs ordered by room descending. Players in the same room are ordered by the time they entered that room, earliest first. Its required time is `O(N + k)`, where `N` is the player count.
All players begin in room `0`; their initial tie order is the order in the constructor's player list.
For console evaluation, player IDs are integers and every operation is a homogeneous two-integer row `[opcode, argument]`:
- `[0, player_id]` means `advance(player_id)`.
- `[1, player_id]` means `get_room(player_id)`.
- `[2, k]` means `leaderboard(k)`.
Implement `escape_room_results(players, R, operations)` and return a list of integer lists. Append `[0, room]` for each room query and `[1, player_id_1, ..., player_id_m]` for each leaderboard query. The leading tag keeps every result in one portable nested-integer representation. Advance operations produce no result.
### Constraints
- `1 <= N <= 100000`, and `players` contains unique integer IDs in the inclusive range `0` through `10^9`, in their initial tie order.
- `1 <= R <= 10000`
- At most `200000` operations are supplied.
- Every referenced player exists, every player ID in an operation is in the inclusive range `0` through `10^9`, and `1 <= k <= N`.
```hint Test tie stability after movement
When two players share a room, moving one away and later back changes when that player entered the shared room.
```
```hint Respect all three complexity targets
A design that reorders every player for each leaderboard call may produce correct small examples but miss the required bound.
```
Quick Answer: Design and implement an `EscapeRoomGame` for a fixed set of players and rooms `0` through `R`. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Design and implement an EscapeRoomGame for a fixed set of players and rooms 0 through R.
advance(player_id)
moves that player forward by one room in
O(1)
. A player already in room
R
remains there.
get_room(player_id)
returns the current room in
O(1)
.
leaderboard(k)
returns up to
k
player IDs ordered by room descending. Players in the same room are ordered by the time they entered that room, earliest first. Its required time is
O(N + k)
, where
N
is the player count.
All players begin in room 0; their initial tie order is the order in the constructor's player list.
For console evaluation, player IDs are integers and every operation is a homogeneous two-integer row [opcode, argument]:
[0, player_id]
means
advance(player_id)
.
[1, player_id]
means
get_room(player_id)
.
[2, k]
means
leaderboard(k)
.
Implement escape_room_results(players, R, operations) and return a list of integer lists. Append [0, room] for each room query and [1, player_id_1, ..., player_id_m] for each leaderboard query. The leading tag keeps every result in one portable nested-integer representation. Advance operations produce no result.
Constraints
1 <= N <= 100000
, and
players
contains unique integer IDs in the inclusive range
0
through
10^9
, in their initial tie order.
1 <= R <= 10000
At most
200000
operations are supplied.
Every referenced player exists, every player ID in an operation is in the inclusive range
0
through
10^9
, and
1 <= k <= N
.