A13123 | $Nearest Opposite Parity$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

You are given an array $a$ consisting of $n$ integers. In one move, you can jump from the position $i$ to the position $i - a_i$ (if $1 \le i - a_i$ ) or to the position $i + a_i$ (if $i + a_i \le n$ ). For each position $i$ from $1$ to $n$ you want to know the minimum the number of moves required to reach any position $j$ such that $a_j$ has the opposite parity from $a_i$ (i.e. if $a_i$ is odd then $a_j$ has to be even and vice versa).

The first line of the input contains one integer $n$ ( $1 \le n \le 2 \cdot 10^5$ ) — the number of elements in $a$ . The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le n$ ), where $a_i$ is the $i$ -th element of $a$ .

Print $n$ integers $d_1, d_2, \dots, d_n$ , where $d_i$ is the minimum the number of moves required to reach any position $j$ such that $a_j$ has the opposite parity from $a_i$ (i.e. if $a_i$ is odd then $a_j$ has to be even and vice versa) or -1 if it is impossible to reach such a position.

输入 #1

10
4 5 7 6 7 5 4 4 6 4

输出 #1

1 1 1 2 -1 1 1 3 1 1

C++ 编辑器

输入

输出