Overview

This problem involves simulating the process of toppling dominoes from left to right, and determining for each domino whether it was knocked down by “Takahashi’s finger” or by “the immediately preceding domino,” using pointer traversal in \(O(N)\).

Analysis

Key Insight

The key point of this problem lies in the rule of “processing from left to right.”

1. Determining the next domino to push with a finger When examining dominoes from left to right, dominoes that have already fallen are skipped. Therefore, at any given point, “the leftmost domino among those still standing” is a domino that the chain reaction from the left did not reach. This domino must be directly pushed by Takahashi’s finger.

2. Chain reaction behavior Let domino \(i\) be the one pushed by finger. The domino \(i+1\) to its right has not yet fallen.

   • If \(A_{i+1} < A_i\), then domino \(i\) knocks down domino \(i+1\). In this case, the direct cause of domino \(i+1\) falling is domino \(i\).
   • Next, starting from the newly fallen domino \(i+1\), we check whether domino \(i+2\) further to the right can be knocked down. The reference height is updated to \(A_{i+1}\).
   • This chain continues one step at a time to the right until the height of the next domino is greater than or equal to the current domino’s height (\(A_j \geq A_{curr}\)), or until the right end is reached.

Why can this be solved in \(O(N)\)?

If the chain stops at position \(R\), then all dominoes to the left of \(R\) have already fallen. The next domino to push with a finger is domino \(R\), the leftmost among those still standing.

In this way, by scanning the dominoes only once from left to right, we can simulate which domino was knocked down by whom. Since there is no need to go back and re-examine dominoes that have already been scanned, the processing is extremely fast.

---

Algorithm

Using a pointer \(R\), we manage the position of the current domino of interest (the leftmost one that has not yet fallen).

1. Prepare an array ans of size \(N\) to store the answers, initialized to \(0\).
2. Starting from \(R = 0\), repeat the following process as long as \(R < N\):
   • Finger push process:
     • Since domino \(R\) is directly pushed by Takahashi, set ans[R] = 0.
     • Assign \(R\) to the variable curr representing the current starting point, and advance pointer \(R\) by \(1\).
   • Chain reaction process:
     • As long as \(R < N\) and \(A_R < A_{curr}\) (the domino to the right is strictly shorter than the previous domino), continue the chain.
     • Since domino \(R\) is knocked down by domino curr, record ans[R] = curr + 1 (adding \(+1\) to convert to 1-indexed).
     • Update curr = R to make it the starting point for the next chain, and advance pointer \(R\) by \(1\).
3. After processing all dominoes, output the contents of ans.

Concrete Example (for \(A = [4, 2, 5, 3, 1]\))

• Step 1: \(R = 0\)
  • Push domino \(1\) (height \(4\)) with finger. ans[0] = 0. Set curr = 0, advance to \(R = 1\).
• Step 2 (chain): \(R = 1\)
  • \(A_1 (2) < A_{curr} (4)\), so the chain continues.
  • Domino \(2\) is knocked down by domino \(1\). ans[1] = 1. Set curr = 1, advance to \(R = 2\).
• Step 3 (chain check): \(R = 2\)
  • \(A_2 (5) \geq A_{curr} (2)\), so the chain stops.
• Step 4: \(R = 2\)
  • Push domino \(3\) (height \(5\)) with finger. ans[2] = 0. Set curr = 2, advance to \(R = 3\).
• Step 5 (chain): \(R = 3\)
  • \(A_3 (3) < A_{curr} (5)\), so the chain continues.
  • Domino \(4\) is knocked down by domino \(3\). ans[3] = 3. Set curr = 3, advance to \(R = 4\).
• Step 6 (chain): \(R = 4\)
  • \(A_4 (1) < A_{curr} (3)\), so the chain continues.
  • Domino \(5\) is knocked down by domino \(4\). ans[4] = 4. Set curr = 4, advance to \(R = 5\).
• End: \(R = 5\), and all dominoes have fallen.
• Output: 0 1 0 3 4

---

Complexity

• Time Complexity: \(O(N)\)

  • Although there is a nested structure of outer and inner while loops, the pointer \(R\) only ever moves to the right (is incremented) and never goes back to the left. Therefore, each element of array \(A\) is accessed at most a constant number of times, and the overall time complexity is \(O(N)\), which is sufficiently fast for the constraint \(N \le 5 \times 10^5\).

• Space Complexity: \(O(N)\)

  • \(O(N)\) memory is used to store the input array \(A\) and the answer array ans.

---

Implementation Notes

• Conversion to 1-indexed

  • In the program, domino numbers are managed from \(0\) to \(N-1\) (0-indexed), but the output must use \(1\) to \(N\) (1-indexed). Therefore, when recording the source of a chain, we need to use curr + 1.

• Fast I/O

  • Since \(N\) can be as large as \(5 \times 10^5\), in Python we use sys.stdin.read to read all input at once and join to output all at once, preventing I/O from becoming a bottleneck.

    Source Code

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    A = [int(x) for x in input_data[1:]]

    ans = [0] * N
    R = 0
    while R < N:
        ans[R] = 0
        curr = R
        R += 1
        while R < N and A[R] < A[curr]:
            ans[R] = curr + 1
            curr = R
            R += 1

    print(" ".join(map(str, ans)))


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.