Simulate Players Moving Under a Watcher's Gaze

Problem Statement

You are refereeing a game played on a one-dimensional road of length L, spanning integer coordinates from 0 to L inclusive.

There are n players. Each player i starts at an initial position players[i] (0 <= players[i] <= L). Players move strictly to the right (+1 unit per second) toward the finish line at L. A player who reaches position L finishes the game and is permanently safe.

A watcher begins at coordinate watcher_pos with an initial direction watcher_dir (1 for moving right toward L, -1 for moving left toward 0). At certain integer seconds given in flip_times, the watcher reverses direction.

The game proceeds in discrete time steps for T seconds (t = 1, 2, ..., T). At each second t, the following events occur in exact order:

1. Direction Flip: If t is present in flip_times, the watcher toggles direction (watcher_dir = -watcher_dir). If a timestamp appears multiple times in flip_times, each occurrence toggles the direction.
2. Watcher Movement: The watcher advances by watcher_dir. The watcher cannot move beyond [0, L]; if the move would exit this range, the watcher clamps at the boundary (remains at 0 or L).
3. Player Movement: Every active (unfrozen and not yet finished) player advances by +1 unit. If a player reaches L, their position becomes L and they immediately finish.
4. Gaze & Freezing: The watcher gazes in their current watcher_dir:
   • If watcher_dir == 1, the watcher's field of view covers all coordinates x >= watcher_pos.
   • If watcher_dir == -1, the watcher's field of view covers all coordinates x <= watcher_pos.
   • Any active player currently inside the watcher's field of view who has not finished (i.e., pos < L) is caught and becomes permanently frozen at their current coordinate. Frozen players can no longer move for the remainder of the game.

Given L, players, watcher_pos, watcher_dir, flip_times, and T, return a list of tuples (final_position, is_frozen) corresponding to each player in the original input order.

Function Signature

def simulate_game(
    L: int,
    players: list[int],
    watcher_pos: int,
    watcher_dir: int,
    flip_times: list[int],
    T: int
) -> list[tuple[int, bool]]:
    pass

Constraints

• 1 <= L <= 10^5
• 1 <= len(players) <= 2,000
• 0 <= players[i] <= L
• 0 <= watcher_pos <= L
• watcher_dir in {-1, 1}
• 0 <= len(flip_times) <= 10^5
• 1 <= flip_times[k] <= 10^5 (elements may be unsorted and may contain duplicates)
• 1 <= T <= 2,000

Examples

Example 1

Input:
L = 10
players = [0, 4]
watcher_pos = 5
watcher_dir = 1
flip_times = [2]
T = 3

Output:
[(0, True), (7, False)]

Explanation:
t = 0:
  Player 0 is at 0, Player 1 is at 4.
  Watcher is at 5, facing 1.

t = 1:
  1. No flip (flip_times has 2).
  2. Watcher moves to 6 (dir = 1).
  3. Player 0 moves to 1; Player 1 moves to 5.
  4. Watcher faces 1, line of sight is [6, 10]. Neither player is in sight.

t = 2:
  1. t = 2 is in flip_times: watcher reverses direction to -1.
  2. Watcher moves to 5 (dir = -1).
  3. Player 0 moves to 2; Player 1 moves to 6.
  4. Watcher faces -1, line of sight is [0, 5]. Player 0 is at 2 <= 5, so Player 0 freezes! Player 1 is at 6 (not in [0, 5]).

t = 3:
  1. No flip.
  2. Watcher moves to 4 (dir = -1).
  3. Player 0 is frozen at 2. Player 1 moves to 7.
  4. Watcher faces -1, line of sight is [0, 4]. Player 1 is at 7 (not in [0, 4]).

Final result: Player 0 is at (2, True), Player 1 is at (7, False).

Example 2

Input:
L = 5
players = [3]
watcher_pos = 2
watcher_dir = 1
flip_times = []
T = 2

Output:
[(5, False)]

Explanation:
t = 1: Watcher moves to 3 (facing 1). Player moves to 4. Sight is [3, 5], but player has not reached L yet so player at 4 is in [3, 5] -> Player freezes at 4!
Wait: at t = 1, player moves to 4, watcher is at 3, facing 1, sight is [3, 5]. 4 is in [3, 5], so player freezes at (4, True).