[Codeforces] Round547(div3) : C - Polycarp Restores Permutation
Round547(div3) : C - Polycarp Restores Permutation
풀이
수학
O(n^2)으로 x값을 한바퀴돌면서 순열이 성립하는지 한바퀴 체크하면 쉽겠지만,
n의 범위가 200000까지라서 시간초과가 난다.
키포인트는 q[i]를 누적해서 더했을때 최소값 + 1 이 초항(x)가 되야된다는것이다.(항상 1부터 시작하니까)
초항(x)값을 계산했으면, chk배열로 중복체크를 하면서 x+누적합q[i]이 1부터 n까지 사이에 존재하는지만 체크하면 된다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
long long q[200001];
int chk[200001];
int main() {
int n;
cin >> n;
long long m = 0;
q[0] = 0;
for (int i = 1; i < n; i++) {
int tmp;
cin >> tmp;
q[i] = q[i - 1] + tmp;
if (q[i] < m) {
m = q[i];
}
}
long long x = 1 - m;
vector<int> v;
int flag = 0;
for (int i = 0; i < n; i++) {
int num = x + q[i];
if (chk[num] == 0 && num>=0 && num<=n) {
chk[num] = 1;
v.push_back(num);
}
else {
flag = 1;
break;
}
}
if (flag) {
cout << -1;
}
else {
for (auto x : v) {
cout << x << ' ';
}
}
return 0;
}
Written on March 20, 2019