# Cow Program

## 题目描述

Farmer John has just given the cows a program to play with! The program contains two integer variables, $x$ and $y$, and performs the following operations on a sequence $a_1, a_2, \ldots, a_n$ of positive integers:

1. Initially, $x=1$ and $y=0$. If, after any step, $x \le 0$ or $x \gt n$, the program immediately terminates.
2. The program increases both $x$ and $y$ by a value equal to $a_x$ simultaneously.
3. The program now increases $y$ by $a_x$ while decreasing $x$ by $a_x$.
4. The program executes steps 2 and 3 (first step 2, then step 3) repeatedly until it terminates (it may never terminate). So, the sequence of executed steps may start with: step 2, step 3, step 2, step 3, step 2 and so on.

The cows are not very good at arithmetic though, and they want to see how the program works. Please help them!
You are given the sequence $a_2, a_3, \ldots, a_n$. Suppose for each $i \; (1 \le i \le n-1)$ we run the program on the sequence $i, a_2, a_3, \ldots, a_n$. For each such run output the final value of $y$ if the program terminates or $-1$ if it does not terminate.

## 题意概述

while (!(x <= 0 || x > n)) {
y += a[x], x += a[x];
if (!(x <= 0 || x > n)) y += a[x], x -= a[x];
}


## 代码

#include <iostream>
using namespace std;
long long n, a[300001], ans[300001][2], to[300001][2], vis[300001][2];
long long dfs(long long t, long long m) {
if (ans[t][m]) return ans[t][m];
if (vis[t][m]) return ans[t][m] = -1; vis[t][m] = true;
if (to[t][m] < 1 || to[t][m] > n) return ans[t][m] = a[t];
long long ret = dfs(to[t][m], !m);
if (ret == -1) ans[t][m] = -1; else ans[t][m] = a[t] + ret;
return ans[t][m];
}
int main()
{
cin >> n, vis[1][1] = true;
for (int i = 2; i <= n; ++i) cin >> a[i];
for (int i = 2; i <= n; ++i) to[i][0] = i - a[i], to[i][1] = i + a[i];
for (int i = 2; i <= n; ++i) if (!ans[i][0]) dfs(i, 0);
for (int i = 1; i < n; ++i)
if (ans[i + 1][0] == -1) cout << -1 << endl;
else cout << i + ans[i + 1][0] << endl;
return 0;
}


418 I'm a teapot