专栏首页glm的全栈学习之路Codeforces Round #547 (Div. 3)C. Polycarp Restores Permutation

Codeforces Round #547 (Div. 3)C. Polycarp Restores Permutation

C. Polycarp Restores Permutation

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

题意:输入一个数n表示一个序列长度,接下来输入n-1个数表示该序列的差分数组构成

要求还原成一个1-n构成的序列,无解输出-1

思路:一个很明显的解法就是我先假定第一个数为最大数n,然后得到一个序列,判断其是否连续是则还原(按照对应差值还原),否则无解

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#include<unordered_set>
#define rg register ll
#define inf 2147483647
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define maxn 200005
const double eps = 1e-8;
using namespace std;
inline ll read()
{
	char ch = getchar(); ll s = 0, w = 1;
	while (ch < 48 || ch>57) { if (ch == '-')w = -1; ch = getchar(); }
	while (ch >= 48 && ch <= 57) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
	return s * w;
}
inline void write(ll x)
{
	if (x < 0)putchar('-'), x = -x;
	if (x > 9)write(x / 10);
	putchar(x % 10 + 48);
}
ll n,a[10*maxn+5],minn=inf,flag[20*maxn],maxx=-1,b[maxn],c[maxn];
inline bool check()
{
    ll i=1,cnt=0;
    while(b[i+1]-b[i]==1)
    {
      //  cout<<b[i]<<endl;
        i++,cnt++;
 
    }
    return cnt+1==n?1:0;
}
int main()
{
	n=read();
	a[1]=n,flag[n]=1,minn=min(a[1],minn),maxx=max(maxx,a[1]);
	b[1]=a[1];
    for(rg i=2;i<=n;i++)
    {
        ll x=read();
        a[i]=a[i-1]+x,b[i]=a[i];
        //p.push_back(a[i]);
        minn=min(minn,a[i]);
        maxx=max(maxx,a[i]);
    }
   sort(b+1,b+1+n);
   /*for(rg i=1;i<=n;i++)
   {
       cout<<b[i]<<endl;
   }*/
    if(check())
    {
        ll k=maxx-n;
        for(rg i=1;i<=n;i++)
        {
            a[i]-=k;
           // flag[a[i]]=1;
          //  i==n?cout<<a[i]<<endl:cout<<a[i]<<" ";
        }
            for(rg i=1;i<=n;i++)
        {
            i==n?cout<<a[i]<<endl:cout<<a[i]<<" ";
        }
    }
    else
    {
        cout<<-1<<endl;
        return 0;
    }
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • PAT (Basic Level) Practice (中文)1013 数素数 (20 分)

    令 P​i​​ 表示第 i 个素数。现任给两个正整数 M≤N≤10​4​​,请输出 P​M​​ 到 P​N​​ 的所有素数。

    glm233
  • PAT (Basic Level) Practice (中文)1007 素数对猜想 (20 分)

    让我们定义d​n​​为:d​n​​=p​n+1​​−p​n​​,其中p​i​​是第i个素数。显然有d​1​​=1,且对于n>1有d​n​​是偶数。“素数对猜想”...

    glm233
  • PAT (Basic Level) Practice (中文)1020 月饼 (25 分)

    月饼是中国人在中秋佳节时吃的一种传统食品,不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量,请你计算可以获得的最大收益是多...

    glm233
  • PAT (Basic Level) Practice (中文)1007 素数对猜想 (20 分)

    让我们定义d​n​​为:d​n​​=p​n+1​​−p​n​​,其中p​i​​是第i个素数。显然有d​1​​=1,且对于n>1有d​n​​是偶数。“素数对猜想”...

    glm233
  • PAT (Basic Level) Practice (中文)1013 数素数 (20 分)

    令 P​i​​ 表示第 i 个素数。现任给两个正整数 M≤N≤10​4​​,请输出 P​M​​ 到 P​N​​ 的所有素数。

    glm233
  • Codeforces Round #547 (Div. 3)E. Superhero Battle

    A superhero fights with a monster. The battle consists of rounds, each of which ...

    glm233
  • Hyperledger Fabric中的零知识证明

    Fabric 1.3中的新增的idemixer(Identity Mixer)以前不大懂zero-knowledge proof(零知识证明),原本觉得PKI基...

    Zeal
  • PAT (Basic Level) Practice (中文)1008 数组元素循环右移问题 (20 分)

    一个数组A中存有N(>0)个整数,在不允许使用另外数组的前提下,将每个整数循环向右移M(≥0)个位置,即将A中的数据由(A​0​​A​1​​⋯A​N−1​​)变...

    glm233
  • AQS源码分析之Elasticsearch BaseFuture

    Java多线程编程中,常用的多线程设计模式包括:Future模式、Master-Worker模式、Guarded Suspeionsion模式、不变模式和生产者...

    开发架构二三事
  • 【Codeforces 738A】Interview with Oleg

    http://codeforces.com/contest/738/problem/A

    饶文津

扫码关注云+社区

领取腾讯云代金券