# 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.

```// 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;
{
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()
{
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++)
{
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​​ 的所有素数。

• ### 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​​是偶数。“素数对猜想”...

• ### PAT (Basic Level) Practice （中文）1020 月饼 (25 分)

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

• ### 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​​是偶数。“素数对猜想”...

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

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

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

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

• ### Hyperledger Fabric中的零知识证明

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

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

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

• ### AQS源码分析之Elasticsearch BaseFuture

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

• ### 【Codeforces 738A】Interview with Oleg

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