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.
Examples
input
Copy
3 -2 1
output
Copy
3 1 2
input
Copy
5 1 1 1 1
output
Copy
1 2 3 4 5
input
Copy
4 -1 2 2
output
Copy
-1
告诉你a_i 和 a_i+1的差值，然后问你能不能找到一个1到n的排列，满足这个差值数组，不能找到则输出-1
那就开始从0开始作为第一个，然后一直模拟，按到差值构造出一个数列，接着判断一下这个数列能不能满足1到n的排列，如果最大值大于n的话就用所有的减去那个差值，如果最小的小于等于0，那就加上那个差值，最后再去check一下看看满不满足1到n的排列，然后输出就OK了
#include <bits/stdc++.h>
#include <time.h>
#define fi first
#define se secondusing namespace std;typedef long long ll;
typedef double db;
int xx[4] = {1,-1,0,0};
int yy[4] = {0,0,1,-1};
const double eps = 1e-9;
typedef pair<int,bool> P;
const int maxn = 1e6;
const ll mod = 1e9 + 7;
inline int sign(db a) { return a < -eps ? -1 : a > eps;}
inline int cmp1(db a,db b){ return sign(a - b);}
ll mul(ll a,ll b,ll c) { ll res = 1; while(b) { if(b & 1) res *= a,res %= c; a *= a,a %= c,b >>= 1; } return res;}
ll phi(ll x) { ll res = x; for(ll i = 2; i * i <= x; i++) { if(x % i == 0) res = res / i * (i - 1); while(x % i == 0) x /= i; } if(x > 1) res = res / x * (x - 1); return res;}
void ex_gcd(ll a, ll b, ll &x, ll &y){if (b == 0) { x = 1;y = 0;return; } else { ex_gcd(b, a%b, x, y); ll t = x; x = y; y = t - (a / b)*y; } return ; }
int fa[maxn];
int Find(int x) { if(x != fa[x]) return fa[x] = Find(fa[x]); return fa[x];}
ll c,n,k;
ll b[maxn],x;
ll num[maxn];
vector<int>v[maxn];
bool vis[maxn];
map<ll,ll>m;
ll s[maxn],a[maxn],ans[maxn];
int main() {ios::sync_with_stdio(false);while(cin >> n){for(int i = 1; i < n;i++) cin >> a[i];ans[1] = 0;for(int i = 1;i < n;i++) ans[i + 1] = ans[i] + a[i];ll Max = 0,id = 0,Min = 1e18;for(int i = 1;i <= n;i++) Max = max(Max,ans[i]),Min = min(Min,ans[i]);if(Max > n) for(int i = 1;i <= n;i++){ ans[i] -= abs(Max - n);if(Min <= 0) for(int i = 1;i <= n;i++) ans[i] += abs(-1 * Min + 1);for(int i = 1;i <= n;i++){if(!m[ans[i]]) m[ans[i]] = 1;else return cout << -1 << endl,0;if(ans[i] <= 0 || ans[i] > n)return cout << -1 << endl,0;}for(int i = 1;i <= n;i++) cout << ans[i] << " ";cout << endl;}
// cerr << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}