Advance Cyclic Ball Flips Efficiently

Advance Cyclic Ball Flips

You are given a circle of n balls indexed from 0 to n - 1 in clockwise order, where the next ball after n - 1 is 0. Each ball is initially in state 0 or 1.

You are also given a list of m markers placed at initial positions on the circle (multiple markers may occupy the same position), and an integer k representing the number of operational steps.

At each step:

1. For every marker currently on ball i, ball i flips its state (0 becomes 1, and 1 becomes 0). If multiple markers are on the same ball, the ball flips once for each marker present.
2. Every marker simultaneously advances by one position clockwise: a marker at position p moves to (p + 1) % n.

Determine the state of all n balls after k steps.

Function Signature

def advance_cyclic_flips(n: int, colors: list[int], markers: list[int], k: int) -> list[int]:
    pass

Constraints

• 1 <= n <= 100,000
• 1 <= len(colors) == n
• colors[i] in {0, 1}
• 1 <= len(markers) <= 100,000
• 0 <= markers[i] < n
• 0 <= k [1, 0, 1, 0]`. Markers move to 1 and 3.
• Step 1: Markers at 1 and 3. Balls 1 and 3 flip -> [1, 1, 1, 1]. Markers move to 2 and 0.
• Step 2: Markers at 2 and 0. Balls 2 and 0 flip -> [0, 1, 0, 1]. Markers move to 3 and 1. Wait, let's trace carefully: 3 steps means flipping at step 0, 1, 2.
• Step 0: balls 0 and 2 flip (now [1, 0, 1, 0]).
• Step 1: balls 1 and 3 flip (now [1, 1, 1, 1]).
• Step 2: balls 2 and 0 flip (now [0, 1, 0, 1]). Output is [0, 1, 0, 1].

Example 2:

Input: n = 5, colors = [1, 0, 1, 1, 0], markers = [1], k = 5
Output: [0, 1, 0, 0, 1]

Explanation: The single marker completes exactly one full cycle of length 5, flipping every ball exactly once. Each bit is inverted.

Edge Cases

• k = 0: No flips occur; return colors as is.
• k >= n: Markers complete full laps around the circle. Each full lap visits every position on the ring.
• Markers can start at identical positions.