CF1272E · Nearest Opposite Parity

• 难度：1900
• 标签：dfs and similar、graphs、shortest paths
• 链接：https://codeforces.com/problemset/problem/1272/E
• 时间限制：2 seconds　内存限制：256 megabytes
• 出现位置：Day28-阶段模拟7-S T1-T3综合卷

中文题意

给定一个由 $n$ 个整数组成的数组 $a$。一次移动中，你可以从位置 $i$ 跳到位置 $i - a_i$（若 $1 \le i - a_i$）或位置 $i + a_i$（若 $i + a_i \le n$）。

对每个位置 $i$（$1$ 到 $n$），你想知道到达任意一个位置 $j$（使得 $a_j$ 与 $a_i$ 奇偶性相反，即 $a_i$ 为奇数时 $a_j$ 需为偶数，反之亦然）所需的最少移动次数。

输入格式（中文）

第一行一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示 $a$ 中的元素个数。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$），其中 $a_i$ 为 $a$ 的第 $i$ 个元素。

输出格式（中文）

输出 $n$ 个整数 $d_1, d_2, \dots, d_n$，其中 $d_i$ 为到达任意一个 $a_j$ 与 $a_i$ 奇偶性相反的位置 $j$ 所需的最少移动次数；若无法到达这样的位置，则输出 $-1$。

样例

样例 1

输入：

10
4 5 7 6 7 5 4 4 6 4

输出：

1 1 1 2 -1 1 1 3 1 1