/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
正整数 N,L と長さ N の正整数列 A = (A_{1}, A_{2}, \dots , A_{N}) が与えられます。
i = 1, 2, \dots , N について、以下の問いに答えてください。
\displaystyle \sum_{j = 1} ^ {L - 1} \sum_{k = j + 1} ^ {L} |B_{j} - B_{k}| = A_{i} を満たす、長さ L の非負整数列 B = (B_{1}, B_{2}, \dots B_{L}) が存在するか判定し、存在するならそのような B に対する \max(B) の最小値を求めてください。
制約
- 1\leq N \leq 2 \times 10 ^ {5}
- 2\leq L \leq 2 \times 10 ^ {5}
- 1\leq A_{i} \leq 2 \times 10 ^ {5}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
N L
A_{1} A_{2} \cdots A_{N}
出力
N 行出力してください。 k 行目には i=k としたときに、条件を満たす B が存在しないなら -1 を、存在するなら \max(B) の最小値を出力してください。
入力例 1
2 4 10 5
出力例 1
3 -1
A_{1} = 10 について、 B=(1,0,2,3) としたとき、\displaystyle \sum_{j = 1} ^ {L - 1} \sum_{k = j + 1} ^ {L} |B_{j} - B_{k}| = 10 となり、このとき \max(B) = 3 となります。 \max(B) < 3 かつ、条件を満たす非負整数列 B は存在しないので、1 行目には 3 を出力してください。
A_{2} = 5 について、
条件を満たす非負整数列 B は存在しないので、 2 行目には -1 を出力してください。
入力例 2
6 8 167 924 167167 167924 116677 154308
出力例 2
11 58 10448 10496 7293 9645
Score : 600 points
Problem Statement
You are given positive integers N and L, and a sequence of positive integers A = (A_{1}, A_{2}, \dots , A_{N}) of length N.
For each i = 1, 2, \dots , N, answer the following question:
Determine if there exists a sequence of L non-negative integers B = (B_{1}, B_{2}, \dots, B_{L}) such that \displaystyle \sum_{j = 1} ^ {L - 1} \sum_{k = j + 1} ^ {L} |B_{j} - B_{k}| = A_{i}. If it exists, find the minimum value of \max(B) for such a sequence B.
Constraints
- 1 \leq N \leq 2 \times 10^{5}
- 2 \leq L \leq 2 \times 10^{5}
- 1 \leq A_{i} \leq 2 \times 10^{5}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N L
A_{1} A_{2} \cdots A_{N}
Output
Print N lines. The k-th line should contain -1 if no sequence B satisfies the condition for i=k; otherwise, it should contain the minimum value of \max(B) for such a sequence B.
Sample Input 1
2 4 10 5
Sample Output 1
3 -1
For A_{1} = 10, if we take B = (1, 0, 2, 3), then \displaystyle \sum_{j = 1} ^ {L - 1} \sum_{k = j + 1} ^ {L} |B_{j} - B_{k}| = 10, where \max(B) = 3. No non-negative integer sequence B satisfies the condition with \max(B) < 3, so print 3 in the first line.
For A_{2} = 5,
there is no non-negative integer sequence B that satisfies the condition, so print -1 in the second line.
Sample Input 2
6 8 167 924 167167 167924 116677 154308
Sample Output 2
11 58 10448 10496 7293 9645