一度 \(A _ i=i\) であるようなマス \(i\) に到達したらそこから移動することはありません。 そのようなマスに到達するまでは駒を毎回 \(1\) マス以上進めることになりますが、マス \(i\) からはじめて駒を毎回進めることはたかだか \(N-i\) 回しかできません。 \(N\leq10 ^ {100}\) なので、「\(10 ^ {100}\) 回操作を行う」ということは、「駒が進めなくなるまで操作を行う」と言い換えてよいです。

よって、次のようなアルゴリズムは正しい答えを出力します。

• \(i=1,2,\ldots,N\) の順に、以下の手順を行う。
  1. \(\operatorname{ans}\leftarrow i\) と初期化する。
  2. \(\operatorname{ans}\neq A _ {\operatorname{ans}}\) である限り、\(\operatorname{ans}\leftarrow A _ {\operatorname{ans}}\) と更新する。
  3. \(\operatorname{ans}\) を出力する。

このアルゴリズムの 2. の繰り返しは、それぞれの \(i\) で最悪 \(N-i\) 回行われます。 よって、このアルゴリズムの最悪時間計算量は \(\Theta(N ^ 2)\) となっており、このアルゴリズムを実装して提出しても実行時間制限を超過してしまいます。

ここで、答えの列 \((\operatorname{ans} _ 1,\operatorname{ans} _ 2,\ldots,\operatorname{ans} _ N)\) を後ろから求めることにすると、後ろの計算結果を利用できるようになります。

• \(i=N,N-1,\ldots,2,1\) の順に、以下の手順を行う。
  1. \(\operatorname{ans} _ i\leftarrow i\) と初期化する。
  2. \(\operatorname{ans} _ i\neq A _ {\operatorname{ans} _ i}\) なら、\(\operatorname{ans} _ i\leftarrow\operatorname{ans} _ {A _ i}\) とする。
• \(i=1,2,\ldots,N\) の順に、\(\operatorname{ans} _ i\) を出力する。

これで最悪時間計算量は \(\Theta(N)\) となり、十分高速に答えを求めることができます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <ranges>

int main() {
    using namespace std;
    int N;
    cin >> N;

    vector<int> A(N);
    for (auto&& a : A) {
        cin >> a;
        --a; // 0-indexed にしておく
    }

    vector<int> ans(N);
    for (int i : views::iota(0, N) | views::reverse) { // 降順に、最後に到着するマスを求める
        if (i == A[i]) { // はじめから動かないなら
            ans[i] = i; // そのマスが答え
        } else { // 動くなら
            ans[i] = ans[A[i]]; // 動いた先のマスから始めたときの結果が答え
        }
    }

    for (int a : ans) {
        // 1-indexed に直して出力
        cout << a + 1 << " ";
    }
    cout << endl;

    return 0;
}