[R7E]小球碰撞 - 代码源竞赛平台

时空限制

1S/512M

题目描述

在数轴上有 $n$ 个移动速度为每秒 $1$ 单位的小球，初始时第 $i$ 个小球的位置为 $a_i$ ，移动方向为 $d_i$ 。方向只有 $-1$ 和 $1$ 两种，其中 $-1$ 代表向左移动（位置减一）， $1$ 代表向右移动（位置加一）。当两个小球位置相同时，小球会发生碰撞，碰撞的一瞬间这两个小球就会交换移动方向。

数轴上还有 $m$ 个墙，第 $i$ 个墙的位置为 $b_i$ 。小球撞上墙（即小球位置为 $b_i$ ）的一瞬间移动方向变为相反。

求 $t$ 秒后每个小球的位置。

格式

输入格式

第一行包含三个整数 $n,m,t$ ，分别表示小球的数量、墙的数量和移动的时间。

第二行包含 $n$ 个整数 $a_i$ ，分别表示每个小球初始位置。数据保证 $a_i$ 互不相等。

第三行包含 $n$ 个整数 $d_i$ ，分别表示每个小球初始移动方向。

第四行包含 $m$ 个整数 $b_i$ ，分别表示每个墙的位置。数据保证 $b_i$ 互不相等，保证对于任意 $1\leq i \leq n$ 且 $1\leq j\leq m$ ，有 $a_i\neq b_j$ 。

输出格式

输出一行包含 $n$ 个整数，第 $i$ 个整数表示 $t$ 秒后第 $i$ 个小球的位置。

样例

样例输入 #1

样例输出 #1

3 0 8 4

样例解释 #1

小球的移动状态如下图：

样例输入 #2

6 3 1000
16 205 87 39 1 44
1 1 -1 1 1 -1
210 32 146

样例输出 #2

-937 181 127 65 -952 108

样例输入 #3

样例输出 #3

200 200

数据规模

对于 $10\%$ 的数据， $n\leq 1000$ ， $m=0$ ， $t\leq 1000$ 。

对于 $30\%$ 的数据， $m=0$ 。

对于 $50\%$ 的数据， $m\leq 1$ 。

对于 $100\%$ 的数据， $1\leq n \leq 10^5$ ， $0\leq m \leq 10^5$ ， $1 \leq t \leq 10^{18}$ ， $0 \leq a_i,b_i \leq 10^{18}$ ， $d_i\in\{-1，1\}$ 。数据保证 $a_i$ 互不相等，保证 $b_i$ 互不相等，保证对于任意 $1\leq i \leq n$ 且 $1\leq j\leq m$ ，有 $a_i\neq b_j$ 。