AT_abc482_d.Wannabe Zombie

普及-

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

There are NN people, numbered 11 to NN, standing on a number line.
Person ii is standing at coordinate XiX_i. Here, XiX_i is even for i=1,2,…,Ni=1,2,\dots,N, and X1<X2<⋯<XNX_1 < X_2 < \cdots < X_N holds.

For each k=1,2,…,Nk=1,2,\dots,N, solve the following problem.

At time 00, person kk becomes a zombie. Everyone other than person kk remains human.
From time 00 onward, humans and zombies can move freely on the number line at a speed of at most 11 per unit time.
When a zombie and a human are at the same coordinate, that human becomes a zombie.
Find the minimum possible time at which everyone has become a zombie.

It can be proved that the answer is an integer under the constraints of this problem.

有 NN 个人,编号为 11 到 NN,站在一条数轴上。
第 ii 个人位于坐标 XiX_i 处。其中,对所有 i=1,2,…,Ni=1,2,\dots,N,XiX_i 均为偶数,且满足 X1<X2<⋯<XNX_1 < X_2 < \cdots < X_N。

对每个 k=1,2,…,Nk=1,2,\dots,N,求解以下问题:

在时刻 00,第 kk 个人变为僵尸,其余所有人仍为人类。
从时刻 00 开始,人类与僵尸均可在数轴上以不超过 11 单位长度/单位时间的速度自由移动。
当一个僵尸与一个人类处于同一坐标时,该人类立即变为僵尸。
求所有人全部变为僵尸的最短可能时间。

在本题约束条件下,可以证明答案必为整数。

输入格式

The input is given from Standard Input in the following format:

NN
X1X_1 X2X_2 …\dots XNX_N

输入从标准输入中按以下格式给出:

NN
X1X_1 X2X_2 …\dots XNX_N

输出格式

Print NN lines. The ii-th line (1≤i≤N)(1 \leq i \leq N) should contain the answer to the problem for k=ik=i.

输出 NN 行。第 ii 行(1≤i≤N1 \leq i \leq N)应包含该问题在 k=ik=i 时的答案。

输入输出样例

  • 输入#1

    5
    2 4 10 14 18

    输出#1

    8
    7
    6
    6
    8
  • 输入#2

    9
    140322306 171833796 356303608 595703832 701965684 798563428 857902324 933683272 971602066

    输出#2

    415639880
    399884135
    307649229
    280821689
    280821689
    329120561
    358790009
    396680483
    415639880

说明/提示

Sample 1 Explanation:
For k=1k=1, if person 11 moves in the positive direction of the number line at speed 11 and persons 2,3,4,52,3,4,5 move in the negative direction at speed 11, everyone will have become a zombie by time 88.

For k=2k=2, if each person moves as follows, everyone will have become a zombie by time 77.

  • Person 11: Moves in the positive direction at speed 11.
  • Person 22: Moves in the positive direction at speed 11 until time 33, and in the negative direction at speed 11 from time 33 onward.
  • Person 33: Moves in the negative direction at speed 11 until time 33, and in the positive direction at speed 11 from time 33 onward.
  • Person 44: Moves in the negative direction at speed 11.
  • Person 55: Moves in the negative direction at speed 11.

Constraints

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 0≤X1<X2<⋯<XN≤1090 \leq X_1 < X_2 < \cdots < X_N \leq 10^9
  • XiX_i is even.
  • All input values are integers.

样例 1 解释:
当 k=1k=1 时,若第 11 个人以速度 11 沿数轴正方向移动,而第 2,3,4,52,3,4,5 个人均以速度 11 沿数轴负方向移动,则所有人将在时刻 88 前全部变成僵尸。

当 k=2k=2 时,若每个人按如下方式移动,则所有人将在时刻 77 前全部变成僵尸:

  • 第 11 个人:以速度 11 沿正方向移动。
  • 第 22 个人:在时刻 33 前以速度 11 沿正方向移动,从时刻 33 起以速度 11 沿负方向移动。
  • 第 33 个人:在时刻 33 前以速度 11 沿负方向移动,从时刻 33 起以速度 11 沿正方向移动。
  • 第 44 个人:以速度 11 沿负方向移动。
  • 第 55 个人:以速度 11 沿负方向移动。

约束条件

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 0≤X1<X2<⋯<XN≤1090 \leq X_1 < X_2 < \cdots < X_N \leq 10^9
  • 所有 XiX_i 均为偶数。
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页