fork download
  1. def solve():
  2. n, q = map(int, input().split()) # Number of snakes and events
  3. events = [input().strip() for _ in range(q)] # List of events
  4.  
  5. # Initialize the snake positions: all snakes start in their own cell, so (1, 1) for each snake.
  6. snakes = [(1, 1)] * n # List of tuples representing the (left, right) positions of each snake.
  7.  
  8. # Set to track occupied cells to avoid collisions
  9. occupied = set(range(1, n + 1)) # Initially, each snake occupies one cell from 1 to n
  10.  
  11. # To keep track of the maximum occupied cell after each step
  12. max_occupied = n # Initially, the maximum occupied cell is n (since the snakes occupy 1 to n).
  13.  
  14. # Process each event
  15. for event in events:
  16. snake_idx = int(event[0]) - 1 # Snake index is 1-based, so we adjust to 0-based.
  17. if event[2] == '+': # Grow the snake
  18. # Current position of the snake
  19. left, right = snakes[snake_idx]
  20. # Try to grow the snake
  21. new_right = right + 1
  22. if new_right not in occupied:
  23. # Update snake's position and mark new cell as occupied
  24. snakes[snake_idx] = (left, new_right)
  25. occupied.add(new_right)
  26. # Update max_occupied
  27. max_occupied = max(max_occupied, new_right)
  28. elif event[2] == '-': # Shrink the snake
  29. # Current position of the snake
  30. left, right = snakes[snake_idx]
  31. # Try to shrink the snake
  32. new_left = left + 1
  33. # Update snake's position
  34. snakes[snake_idx] = (new_left, right)
  35. # Mark the cell we just freed as unoccupied
  36. occupied.remove(left)
  37.  
  38. # Output the minimum possible score (maximum occupied cell after all events)
  39. print(max_occupied)
  40.  
Success #stdin #stdout 0.04s 9664KB
stdin
5 13
5 +
3 +
5 -
2 +
4 +
3 +
5 +
5 -
2 +
3 -
3 +
3 -
2 +
stdout
Standard output is empty