CF1141C Polycarp Restores Permutation

    • 36通过
    • 78提交
  • 题目来源 CodeForces 1141C
  • 评测方式 RemoteJudge
  • 标签
  • 难度 普及+/提高
  • 时空限制 2000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    有一个长度为 $n (2 \le n \le 2 \cdot 10^{5})$ 的序列 $p$ ,现在给出一个长度为 $n-1$ 的序列 $q$ ,其中 $q_{i}=p_{i+1}-p_{i}$ ,询问序列 $p$ 是否有可能是 $1 \sim n$ 的一个排列,如果可行,输出这个排列,否则输出 $-1$

    题目描述

    An array of integers $ p_1, p_2, \dots, p_n $ is called a permutation if it contains each number from $ 1 $ to $ n $ exactly once. For example, the following arrays are permutations: $ [3, 1, 2] $ , $ [1] $ , $ [1, 2, 3, 4, 5] $ and $ [4, 3, 1, 2] $ . The following arrays are not permutations: $ [2] $ , $ [1, 1] $ , $ [2, 3, 4] $ .

    Polycarp invented a really cool permutation $ p_1, p_2, \dots, p_n $ of length $ n $ . It is very disappointing, but he forgot this permutation. He only remembers the array $ q_1, q_2, \dots, q_{n-1} $ of length $ n-1 $ , where $ q_i=p_{i+1}-p_i $ .

    Given $ n $ and $ q=q_1, q_2, \dots, q_{n-1} $ , help Polycarp restore the invented permutation.

    输入输出格式

    输入格式:

    The first line contains the integer $ n $ ( $ 2 \le n \le 2\cdot10^5 $ ) — the length of the permutation to restore. The second line contains $ n-1 $ integers $ q_1, q_2, \dots, q_{n-1} $ ( $ -n < q_i < n $ ).

    输出格式:

    Print the integer -1 if there is no such permutation of length $ n $ which corresponds to the given array $ q $ . Otherwise, if it exists, print $ p_1, p_2, \dots, p_n $ . Print any such permutation if there are many of them.

    输入输出样例

    输入样例#1: 复制
    3
    -2 1
    
    输出样例#1: 复制
    3 1 2 
    输入样例#2: 复制
    5
    1 1 1 1
    
    输出样例#2: 复制
    1 2 3 4 5 
    输入样例#3: 复制
    4
    -1 2 2
    
    输出样例#3: 复制
    -1
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。