CF 1141C Polycarp Restores Permutation

Description

An array of integers p1,p2,…,pnp1,p2,…,pn is called a permutation if it contains each number from 11 to nn exactly once. For example, the following arrays are permutations: [3,1,2][3,1,2] , [1][1] , [1,2,3,4,5][1,2,3,4,5] and [4,3,1,2][4,3,1,2] . The following arrays are not permutations: [2][2] , [1,1][1,1] , [2,3,4][2,3,4] .

Polycarp invented a really cool permutation p1,p2,…,pnp1,p2,…,pn of length nn . It is very disappointing, but he forgot this permutation. He only remembers the array q1,q2,…,qn−1q1,q2,…,qn−1 of length n−1n−1 , where qi=pi+1−piqi=pi+1−pi .

Given nn and q=q1,q2,…,qn−1q=q1,q2,…,qn−1 , help Polycarp restore the invented permutation.

Input

The first line contains the integer nn (2≤n≤2⋅1052≤n≤2⋅105 ) — the length of the permutation to restore. The second line contains n−1n−1 integers q1,q2,…,qn−1q1,q2,…,qn−1 (−n<qi<n−n<qi<n ).

Output

Print the integer -1 if there is no such permutation of length nn which corresponds to the given array qq . Otherwise, if it exists, print p1,p2,…,pnp1,p2,…,pn . Print any such permutation if there are many of them.

Examples

Input

3 -2 1

Output

3 1 2

Input

5 1 1 1 1

Output

1 2 3 4 5

Input

4 -1 2 2

Output

-1

题目分析

给你一个数组的相邻两项之间的差值，要求还原这个数组，而且这个数组中的元素的取值范围在[1,n]，并且每一个数只出现一次，并且1-n的每一个数都要出现.

想到这里，觉得这个题也不难呀，二分枚举第一个数然后根据前后的差值不断的向后递推就好了，不过注意判重。

如果第一个数太大了，那么必然会出现数组中的某一个数越界，那么就继续二分左区间，否则就二分右区间。

而在某一个数作为第一个数的时候出现了某一个数重复出现的情况，则说明这个数组无法还原.

代码区

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include <vector>

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;

const int Max = 5e5 + 5;

int v[Max];

;

int main()

{

	int n;

	while (scanf("%d", &n) != EOF)

	{

		for (int i = 1; i < n; i++)

		{

			scanf("%d", v + i);

		}

		int l, r;

		if (v[1] > 0)l = 1, r = n - v[0];	//若前两个数的差为正数，那么第一个数的小于n-v[0]，因为第二个数不可以超过n

		else l = 1 - v[0], r = n;		//若前两个数的差为负数，那么第一个数一定要大于1+v[0]

		vector<int>q;	//存数据

		bool vis[Max];	//vis[i]记录数字i是否出现

		int flag = false, gg = false;	        //flag == true代表成功,gg = true代表失败

		while (l <= r)		                //二分

		{

			int mid = (l + r) / 2;

			memset(vis, false, sizeof(vis));

			vis[mid] = true;	        //表示mid出现

			q.push_back(mid);

			int next;			//记录序列下一个数

			for (int i = 1; i < n;i++)

			{

				next = q.back() + v[i];	//记录下一个数

				if (1 <= next && next <= n && !vis[next])//当前数不重复，且在范围[1,n]内

				{

					q.push_back(next);

					vis[next] = true;

					if (q.size() == n) flag = true;

				}

				else

				{

					if (1 <= next && next <= n && vis[next])gg = true;				                                //出现重复，代表这个序列不可能成了

					break;

				}

			}

			if (gg || flag) break;		        //到达目的或者无法实现

			q.clear();				//当前作为一个数的数失败，则继续二分

			if (next > n)r = mid - 1;	        //第一个数太小导致越界

			else l = mid + 1;			//第一个数太大导致越界

		}

		if (gg)

		{

			printf("-1\n");

		}

		else

		{

			if(flag)

			{

				for (int i = 0;i < n - 1; i++)

				{

					printf("%d ", q[i]);

				}

				printf("%d\n", q[n - 1]);

			}

			else

			{

				printf("-1\n");

			}

		}

	}

	return 0;

}

巴特西

CF 1141C Polycarp Restores Permutation

Description

Input

Output

Examples

题目分析

代码区

最新文章

热门文章