← 返回题目列表

Codeforces · 1272/E

E. 最近的相反奇偶校验

中文机器翻译题面 查看原题

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。一步操作中,您可以从位置 $$$i$$$ 跳转到位置 $$$i - a_i$$$(如果 $$$1 \le i - a_i$$$)或位置 $$$i + a_i$$$(如果 $$$i + a_i \le n$$$)。

对于从 $$$1$$$ 到 $$$n$$$ 的每个位置 $$$i$$$,您想知道到达任何位置 $$$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$$$ 是到达任何位置 $$$j$$$ 所需的最小移动次数,使得 $$$a_j$$$ 与 $$$a_i$$$ 具有相反的奇偶性(即,如果 $$$a_i$$$ 是奇数那么 $$$a_j$$$ 必须是偶数,反之亦然),如果不可能达到这样的位置,则为 -1。

示例

输入 #1

10
4 5 7 6 7 5 4 4 6 4

输出 #1

1 1 1 2 -1 1 1 3 1 1