本文共 1504 字，大约阅读时间需要 5 分钟。

题目来源：

Description

You are given an array a consisting of n integers. In one move, you can jump from the position i to the position i−ai (if 1≤i−ai) or to the position i+ai (if i+ai≤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 aj has the opposite parity from ai (i.e. if ai is odd then aj has to be even and vice versa).

Input

The first line of the input contains one integer n (1≤n≤2⋅105) — the number of elements in a.

The second line of the input contains n integers a1,a2,…,an (1≤ai≤n), where ai is the i-th element of a.

Output

Print n integers d1,d2,…,dn, where di is the minimum the number of moves required to reach any position j such that aj has the opposite parity from ai (i.e. if ai is odd then aj has to be even and vice versa) or -1 if it is impossible to reach such a position.

Sample Input

10

Sample Output

1 1 1 2 -1 1 1 3 1 1

AC代码：

#include 
   
    using namespace std;#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define endl '\n'const int MAXN = 2e5+5;int arr[MAXN],ans[MAXN];vector
    
      v[MAXN];int main(){
       SIS;    int n;    memset(ans,-1,sizeof(ans));    cin >> n;    for(int i=0;i
     
      > arr[i];    queue
      
        q;    for(int i=0;i
       
        =0)        {
               v[i-arr[i]].emplace_back(i);            if((arr[i]&1)^(arr[i-arr[i]]&1)) ans[i]=1;        }        if(i+arr[i]
       
      
     
    
   

转载地址：http://qsyof.baihongyu.com/