分数: 600 点
问题陈述
给你正整数 N 和 L,以及正整数序列 A = (A_{1}, A_{2}, \dots , A_{N}) 长度 N.
对于每个 i = 1, 2, \dots , N,回答以下问题:
判断是否存在序列 L 非负整数 B = (B_{1}, B_{2}, \dots, B_{L}) 这样 \displaystyle \sum_{j = 1} ^ {L - 1} \sum_{k = j + 1} ^ {L} |B_{j} - B_{k}| = A_{i}。如果存在,求最小值 \max(B) 对于这样的序列 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- 第行应包含 -1 如果没有序列 B 满足条件 i=k;否则,它应该包含最小值 \max(B) 对于这样的序列 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。 没有非负整数序列 B 满足条件 \max(B) < 3,所以打印 3 在第一行。
对于 A_{2} = 5,
不存在非负整数序列 B 满足条件,所以打印 -1 在第二行。
示例输入 2
6 8 167 924 167167 167924 116677 154308
示例输出 2
11 58 10448 10496 7293 9645