AT_abc340_e [ABC340E] Mancala 2
题目描述
有 n 个箱子,编号从 0 到 n−1。最初,第 i 个箱子中有 ai 个球。
高桥按照 i=1,2,…,m 的顺序,依次执行 m 次操作。第 i 次操作的流程如下:
1.将计数器 c 设为 0;
2.取出编号为 bi 的箱子中的全部球,拿在手中;
3.只要手中还至少有 1 个球,就重复以下过程:
∘将 c 的值增加 1;
∘从手中取出 1 个球,放入编号为 (bi+c)modn 的箱子。
其中 umodn 表示 u 除以 n 得到的余数。
请在所有操作结束后,输出每个箱子中球的数量。
输入格式
第一行输入两个整数 n,m(1≦n,m≦2×105) 分别代表箱子数量和操作次数。
第二行输入 n 个整数 $a_0, a_1, \dots, a_{n-1} \left(0 \leqq a_i \leqq 10^9\right)$ 代表每个箱子中初始的球数。
第三行输入 m 个整数 b1,b2,…,bm(0≦bi<n) 代表每次操作取球的箱子编号。
输出格式
在一行上输出 n 个整数 x0,x1,…,xn−1,相邻两个整数之间用一个空格隔开,其中 xi 代表所有操作结束后第 i 个箱子中的球数。
测试样例
5 3
1 2 3 4 5
2 4 0
0 4 2 7 2
样例 1 解释
初始时五个箱子中的球数依次为 {1,2,3,4,5}(按编号 0∼4 排列)。
∙第 1 次操作取编号为 2 的箱子,其中有 3 个球,依次放入编号 3,4,0 的箱子,球数变为 {2,2,0,5,6};
∙第 2 次操作取编号为 4 的箱子,其中有 6 个球,先给每个箱子各 1 个(共 5 个),剩下的 1 个放入编号 0 的箱子,球数变为 {4,3,1,6,1};
∙第 3 次操作取编号为 0 的箱子,其中有 4 个球,依次放入编号 1,2,3,4 的箱子,球数变为 {0,4,2,7,2}。
因此输出 0,4,2,7,2。
3 10
1000000000 1000000000 1000000000
0 1 0 1 0 1 0 1 0 1
104320141 45436840 2850243019
1 4
1
0 0 0 0
1
样例 3 解释
只有一个编号为 0 的箱子。每次取出其中的 1 个球后,因为 (0+1)mod1=0,这个球又被放回编号为 0 的箱子,因此每次操作后箱子中始终有 1 个球,最终输出 1。