luogu#P11332. [NOISG2020 Finals] Labels

[NOISG2020 Finals] Labels

题目背景

今天是快递员 Charles 的第一天工作。

题目描述

今天是快递员 Charles 的第一天工作。他需要派送 NN 个包裹,每个包裹都有一个标签编号,编号范围为 11NN(不一定唯一)。每天结束时,他需要记录一个长度为 NN 的序列 AA,其中 AiA_i 是第 ii 个派送包裹的标签编号。

为了节省存储空间,Charles 决定使用差分编码记录一个长度为 N1N-1 的序列 DD,其中 Di=Ai+1AiD_i = A_{i+1} - A_i

完成派送后,Charles 发现他不知道如何从 DD 恢复出 AA。你的任务是帮助他恢复 AA,或者判断是否无法唯一确定 AA

输入格式

  • 第一行一个整数 NN,表示包裹数量。
  • 第二行一个长度为 N1N-1 的整数序列 DD,其中 DiD_i 表示第 i+1i+1 个包裹和第 ii 个包裹标签编号的差。

输出格式

  • 如果可以唯一恢复 AA,输出 NN 个用空格分隔的整数,表示序列 AA
  • 如果无法唯一恢复 AA,输出 -1
5
1 3 -2 1
1 2 5 3 4
5
2 2 -3 1
1 3 5 2 3
2
0
-1

提示

【样例解释】

对于样例 #1,差分序列 D=[1,3,2,1]D = [1, 3, -2, 1],恢复出的序列为 A=[1,2,5,3,4]A = [1, 2, 5, 3, 4],验证如下:

  • A2A1=21=1=D1A_2 - A_1 = 2 - 1 = 1 = D_1
  • A3A2=52=3=D2A_3 - A_2 = 5 - 2 = 3 = D_2
  • A4A3=35=2=D3A_4 - A_3 = 3 - 5 = -2 = D_3
  • A5A4=43=1=D4A_5 - A_4 = 4 - 3 = 1 = D_4

对于样例 #2,可以唯一恢复 A=[1,3,5,2,3]A = [1, 3, 5, 2, 3]

对于样例 #3,差分序列 D=[0]D = [0],序列可能为 A=[1,1]A = [1, 1]A=[2,2]A = [2, 2],因此无法唯一恢复,输出 1-1

【数据范围】

  • 2N3×1052 \leq N \leq 3 \times 10^5
  • 1AiN1 \leq A_i \leq N
  • N<Di<N-N < D_i < N
子任务编号 分值 限制条件
11 77 N=2N = 2
22 1515 2N62 \leq N \leq 6
33 2525 2N1032 \leq N \leq 10^3
44 1818 1Di1-1 \leq D_i \leq 1
55 3535 无额外限制