307662: CF1392F. Omkar and Landslide

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Omkar and Landslide

题意翻译

### 题目描述 现在有一些山发生了山体滑坡,这些山从左到右依次排布,第 $i$ 座山的高度为 $h_i$,且 $\forall i\in[1,n),h_i<h_{i+1}$。 每一时刻,假如 $h_i+2\leq h_{i+1}$,那么两座山的高度会发生变化,即 $h_i+1,h_{i+1}-1$。 问山体滑坡进行完后,即没有任何泥土能流动时,所有山的高度是多少。

题目描述

Omkar is standing at the foot of Celeste mountain. The summit is $ n $ meters away from him, and he can see all of the mountains up to the summit, so for all $ 1 \leq j \leq n $ he knows that the height of the mountain at the point $ j $ meters away from himself is $ h_j $ meters. It turns out that for all $ j $ satisfying $ 1 \leq j \leq n - 1 $ , $ h_j < h_{j + 1} $ (meaning that heights are strictly increasing). Suddenly, a landslide occurs! While the landslide is occurring, the following occurs: every minute, if $ h_j + 2 \leq h_{j + 1} $ , then one square meter of dirt will slide from position $ j + 1 $ to position $ j $ , so that $ h_{j + 1} $ is decreased by $ 1 $ and $ h_j $ is increased by $ 1 $ . These changes occur simultaneously, so for example, if $ h_j + 2 \leq h_{j + 1} $ and $ h_{j + 1} + 2 \leq h_{j + 2} $ for some $ j $ , then $ h_j $ will be increased by $ 1 $ , $ h_{j + 2} $ will be decreased by $ 1 $ , and $ h_{j + 1} $ will be both increased and decreased by $ 1 $ , meaning that in effect $ h_{j + 1} $ is unchanged during that minute. The landslide ends when there is no $ j $ such that $ h_j + 2 \leq h_{j + 1} $ . Help Omkar figure out what the values of $ h_1, \dots, h_n $ will be after the landslide ends. It can be proven that under the given constraints, the landslide will always end in finitely many minutes. Note that because of the large amount of input, it is recommended that your code uses fast IO.

输入输出格式

输入格式


The first line contains a single integer $ n $ ( $ 1 \leq n \leq 10^6 $ ). The second line contains $ n $ integers $ h_1, h_2, \dots, h_n $ satisfying $ 0 \leq h_1 < h_2 < \dots < h_n \leq 10^{12} $ — the heights.

输出格式


Output $ n $ integers, where the $ j $ -th integer is the value of $ h_j $ after the landslide has stopped.

输入输出样例

输入样例 #1

4
2 6 7 8

输出样例 #1

5 5 6 7

说明

Initially, the mountain has heights $ 2, 6, 7, 8 $ . In the first minute, we have $ 2 + 2 \leq 6 $ , so $ 2 $ increases to $ 3 $ and $ 6 $ decreases to $ 5 $ , leaving $ 3, 5, 7, 8 $ . In the second minute, we have $ 3 + 2 \leq 5 $ and $ 5 + 2 \leq 7 $ , so $ 3 $ increases to $ 4 $ , $ 5 $ is unchanged, and $ 7 $ decreases to $ 6 $ , leaving $ 4, 5, 6, 8 $ . In the third minute, we have $ 6 + 2 \leq 8 $ , so $ 6 $ increases to $ 7 $ and $ 8 $ decreases to $ 7 $ , leaving $ 4, 5, 7, 7 $ . In the fourth minute, we have $ 5 + 2 \leq 7 $ , so $ 5 $ increases to $ 6 $ and $ 7 $ decreases to $ 6 $ , leaving $ 4, 6, 6, 7 $ . In the fifth minute, we have $ 4 + 2 \leq 6 $ , so $ 4 $ increases to $ 5 $ and $ 6 $ decreases to $ 5 $ , leaving $ 5, 5, 6, 7 $ . In the sixth minute, nothing else can change so the landslide stops and our answer is $ 5, 5, 6, 7 $ .

Input

题意翻译

### 题目描述 现在有一些山发生了山体滑坡,这些山从左到右依次排布,第 $i$ 座山的高度为 $h_i$,且 $\forall i\in[1,n),h_i<h_{i+1}$。 每一时刻,假如 $h_i+2\leq h_{i+1}$,那么两座山的高度会发生变化,即 $h_i+1,h_{i+1}-1$。 问山体滑坡进行完后,即没有任何泥土能流动时,所有山的高度是多少。

加入题单

上一题 下一题 算法标签: