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

代码语言：javascript复制

Codeforces Round #547 (Div. 3)

代码语言：javascript复制

#include <bits/stdc  .h>
#define ll long long
using namespace std;
int n,m;
map<int,int> mp;
ll pre[200005],s[200005],a[200005];
 
int main()
{
  scanf("%d",&n);
  for(int i=1;i<n;i  ){
    scanf("%lld",&pre[i]);
  }
  ll ans = 0;
  for(int i=1;i<n;i  ){
    s[i] = pre[i]   s[i-1];// S[i] = Pi - P1
    ans  = s[i]; // ans 是 Pn Pn-1 Pn-2 ... P2 - (n - 1)*P1
  }
  a[1] = (ll)n * (ll)(n   1) / 2 - ans; // 这样a[1] = n * P1
  a[1] /= n; //得到P1就得到答案了
  mp[a[1]]   ;
  for(int i=1;i<n;i  ){
    a[i   1] = a[i]   pre[i];
    mp[a[i 1]]   ;
  }
  for(int i=1;i<=n;i  ){
    if(mp[i] != 1){
      puts("-1");
      return 0;
    }
  }
  for(int i=1;i<=n;i  ){
    printf("%lld ",a[i]);
  }
  return 0;
}
 

permutation

0 人点赞