题目描述

The $\textit{Abelian Sandpile Model}$ is a famous dynamical system displaying self-organized criticality. It has been studied for decades since it was introduced by Per Bak, Chao Tang and Kurt Wiesenfeld in a 1987 paper. The sandpile prediction is of wide interest in physics, computer science, and mathematics, both for its beautiful algebraic structure and for its relevance to applications like load balancing and derandomization of models like internal diffusion-limited aggregation. The sandpile model is related to many other models and physical phenomena, like the rotor-routing model, avalanche models.

In the sandpile model, we are given an undirected graph $G$ whose vertices are indexed from $1$ to $n$. We're also given $n$ integers $a_1, a_2, \cdots, a_n$ where $a_i$ indicates that there are $a_i$ chips placed on vertex $i$ initially. Each turn we will pick an arbitrary vertex $v$ such that the number of chips on $v$ is not smaller than the number of edges connecting $v$, denoted as $d_v$. For each neighbor of $v$, it will receive one chip from $v$. Therefore, $v$ will lost $d_v$ chips. This process is called firing or toppling. Firing will keep happening until no vertex $v$ has at least $d_v$ chips.

It can be proven that the order of firing doesn't affect the result. Meanwhile, it is also possible that the firing will never terminate. This instance is described as recurrent. Now you are given a clique and the initial number of chips. Determine whether this instance is a recurrent one. If not, please output the final number of chips for each node respectively.

A clique (also called a complete graph) is a graph where every two vertices are connected with an edge.

输入格式

There is only one test case in each test file.

The first line of the input contains an integer $n$ ($2 \leq n \leq 5 \times 10^5$) indicating the size of the clique.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($0 \leq a_i \leq 10^9$) where $a_i$ indicates the initial number of chips placed on vertex $i$.

输出格式

Output one line. If the given sandpile instance will terminate, output $n$ integers separated by a space where the $i$-th integer indicates the final number of chips on the $i$-th vertex. Otherwise output Recurrent (without quotes) instead.

Please, DO NOT output extra spaces at the end of each line or your solution may be considered incorrect!

题目大意

【题目描述】

阿贝尔沙堆模型（Abelian Sandpile Model）是一个著名的显示自组织临界性的动力学系统。自从它由 Per Bak、Chao Tang 和 Kurt Wiesenfeld 在 1987 年的一篇论文中引入以来，它已经被研究了数十年。沙堆模型的预测引起了物理学、计算机科学和数学的广泛关注，这不仅是因为它美丽的代数结构，还因为它与负载平衡和内部扩散有关的模型的应用，如去随机化。沙堆模型与许多其他模型和物理现象相关，如转子路由模型、雪崩模型。

在沙堆模型中，给定一个顶点编号从 $1$ 到 $n$ 的无向图 $G$。我们还给出了 $n$ 个整数 $a_1, a_2, \cdots, a_n$，其中 $a_i$ 表示初始时放置在顶点 $i$ 上的筹码数量。每个回合，我们将选择一个任意的顶点 $v$，使得 $v$ 上的筹码数量不小于与 $v$ 相连的边数，记为 $d_v$。对于 $v$ 的每个邻居，它将从 $v$ 接收一枚筹码。因此，$v$ 将失去 $d_v$ 枚筹码。这个过程被称为 firing 或 toppling。直到没有顶点 $v$ 至少有 $d_v$ 枚筹码时，firing 才会停止。

可以证明，firing 的顺序不会影响结果。同时，也可能 firing 永远不会终止。这种情况被描述为“recurrent”。现在给定一个团和初始筹码数量，请确定这个实例是否是一个 recurrent 实例。如果不是，请分别输出每个节点的最终筹码数量。

团（也称为完全图）是一个图，其中任意两个顶点都有边相连。

【输入格式】

每个测试文件中只有一个测试用例。

输入的第一行包含一个整数 $n$（$2 \leq n \leq 5 \times 10^5$），表示团的大小。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$0 \leq a_i \leq 10^9$），其中 $a_i$ 表示放置在顶点 $i$ 上的初始筹码数量。

【输出格式】

输出一行。如果给定的沙堆实例将终止，则输出由空格分隔的 $n$ 个整数，其中第 $i$ 个整数表示第 $i$ 个顶点上的最终筹码数量。否则输出 Recurrent（不包括引号）。

请不要在每行末尾输出额外的空格，否则您的解决方案可能被认为是错误的！

【样例解释】

对于第一个样例测试用例：

• 我们只能在开始时选择顶点 $1$。筹码数量变为 $\{1, 1, 4, 1, 4\}$。
• 现在我们可以选择顶点 $3$ 或 $5$，因为它们都至少有 $4$ 枚筹码。我们选择顶点 $3$，筹码数量变为 $\{2, 2, 0, 2, 5\}$。选择顶点 $5$ 会得到相同的结果。
• 现在我们选择顶点 $5$。筹码数量变为 $\{3, 3, 1, 3, 1\}$。没有顶点至少有 $4$ 枚筹码，因此 firing 终止。

对于第二个样例测试用例，我们可以重复选择顶点 $1$ 和 $2$。firing 永远不会终止。

翻译来自于：ChatGPT

5
5 0 3 0 3

3 3 1 3 1

2
1 0

Recurrent

提示

For the first sample test case:

• We can only select vertex $1$ at the beginning. The number of chips becomes $\{1, 1, 4, 1, 4\}$.
• We can now select vertex $3$ or $5$ because both of them have at least $4$ chips. We select vertex $3$ and the number of chips becomes $\{2, 2, 0, 2, 5\}$. Selecting vertex $5$ will lead to the same result.
• We now select vertex $5$. The number of chips becomes $\{3, 3, 1, 3, 1\}$. There is no vertex with at least $4$ chips so the firing terminates.

For the second sample test case, we can select vertex $1$ and $2$ repeatedly. The firing never terminates.