Overview

Given \(N\) dominoes lined up in a row, we simulate the following rule from left to right: “If a domino has not yet fallen, push it by hand, and if the adjacent domino to the right is shorter than the current one, it falls in a chain reaction.” The problem asks us to determine the direct cause of each domino’s fall (output \(0\) if pushed by hand, or the number of the domino that knocked it over).

Analysis

Naive Approach and Its Issues

Let’s consider naively simulating the chain reaction of falling dominoes. When domino \(i\) falls, we search one by one for “dominoes that have not yet fallen” to its right, checking whether their height is less than the current domino’s height.

However, this method ends up scanning already-fallen dominoes repeatedly. For example, if all dominoes have already fallen and we scan from left to right to check a domino near the right end, this takes \(O(N^2)\) time in the worst case, which exceeds the time limit (TLE) under the constraint \(N \le 5 \times 10^5\).

Optimization Idea: Skipping Already-Fallen Dominoes

The key to this problem is “how to efficiently find the leftmost domino that has not yet fallen.”

Dominoes are always processed from left to right, and chain reactions also propagate from left to right. Therefore, by maintaining a variable head that tracks “the index of the smallest-numbered domino that has not yet fallen,” we can always access the next domino in \(O(1)\).

Specifically, we maintain the following information: - nxt[i]: The index of the next domino to check when domino \(i\) falls (initially \(i + 1\)) - head: The index of the leftmost domino that is still standing (initially \(1\))

When domino \(v\) falls, the next standing domino to its right is nxt[v]. Therefore, at the moment domino \(v\) falls, we update head to nxt[v]. Since each domino falls at most once in its lifetime, the total number of times head advances to the right is at most \(N\), allowing us to simulate very efficiently.

---

Algorithm

1. Initialization:

   • Set the pointer to the right neighbor for each domino: nxt[i] = i + 1.
   • Initialize the array ans (which stores the cause of each domino’s fall) to \(-1\) (undetermined).
   • Set head = 1, pointing to the smallest-numbered domino that has not yet fallen.

2. Simulation: Loop from \(i = 1\) to \(N\) in order.

   • If ans[i] != -1, domino \(i\) has already been knocked over by a chain reaction, so skip it.
   • Otherwise, push domino \(i\) by hand.
     • Set ans[i] = 0.
     • Update head to nxt[i].
     • Set the current chain origin to curr = i.
     • Chain reaction loop:

          - Let the next candidate domino be $v = head$.
          - If $v > N$ (out of range), the chain ends.
          - If $A_v < A_{curr}$ (candidate domino $v$ is strictly shorter than the current domino $curr$), then domino $v$ is knocked over by domino $curr$.
       

       • Record ans[v] = curr.
       • Advance head to nxt[v].
       • Update the chain origin to \(curr = v\), and continue the chain loop.

            - If $A_v \geq A_{curr}$, the chain stops here.
         

---

Complexity

• Time Complexity: \(O(N)\) For each domino \(v\), the number of times head points to \(v\) and ans[v] is updated (i.e., the domino is knocked over) is at most once. Also, the number of times the chain stops and exits the loop is at most \(N\), the same as the number of iterations of the outer loop. Therefore, the total number of while loop executions is at most \(2N\), and the processing completes in \(O(N)\) time.
• Space Complexity: \(O(N)\) We use \(O(N)\) memory to store the domino heights \(A\), the next-domino pointers nxt, and the answer array ans.

---

Implementation Notes

• Use of sentinels: By allocating the nxt array with size \(N + 2\), we can cleanly prevent boundary errors when the index exceeds \(N\) (i.e., when all dominoes have fallen).

• Fast I/O: Since the input size is large with \(N \le 5 \times 10^5\), it is important in C++ to include cin.tie(NULL); ios_base::sync_with_stdio(false); to speed up input and output.

  Source Code

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<int> A(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
    }

    // 各ドミノの右隣のドミノを指すポインタ
    vector<int> nxt(N + 2);
    for (int i = 1; i <= N + 1; ++i) {
        nxt[i] = i + 1;
    }

    vector<int> ans(N + 1, -1);
    int head = 1; // まだ倒れていない最小のドミノの番号

    for (int i = 1; i <= N; ++i) {
        if (ans[i] != -1) {
            // すでに倒れている場合はスキップ
            continue;
        }
        
        // 指で直接倒す
        ans[i] = 0;
        head = nxt[i];
        int curr = i;
        
        // 連鎖のシミュレーション
        while (true) {
            int v = head;
            if (v > N) {
                break;
            }
            if (A[v] < A[curr]) {
                ans[v] = curr;
                head = nxt[v];
                curr = v;
            } else {
                break;
            }
        }
    }

    for (int i = 1; i <= N; ++i) {
        cout << ans[i] << (i == N ? "" : " ");
    }
    cout << "\n";

    return 0;
}

---

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