← 返回题目列表

Codeforces · 1525/C

C. 机器人碰撞

中文机器翻译题面 查看原题

有 $$$n$$$ 个机器人沿着 OX 轴行驶。还有两堵墙:一堵墙位于坐标 $$$0$$$ 处,一堵墙位于坐标 $$$m$$$ 处。

第 $$$i$$$ 个机器人从整数坐标 $$$x_i~(0 < x_i < m)$$$ 开始,以每秒 $$$1$$$ 单位的速度向左(朝向 $$$0$$$)或向右移动。没有两个机器人从同一坐标开始。

每当机器人到达墙壁时,它会立即转身并以相同的速度继续向相反的方向行驶。

每当多个机器人在同一个整数坐标处相遇时,它们就会碰撞并爆炸成灰尘。一旦机器人爆炸,它就不会与任何其他机器人发生碰撞。请注意,如果多个机器人在非整数坐标处相遇,则不会发生任何情况。

对于每个机器人,找出它是否爆炸,如果发生则打印爆炸时间,否则打印 $$$-1$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

然后是 $$$t$$$ 测试用例的描述。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$2 \le m \le 10^8$$$) - 机器人的数量和右墙的坐标。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$x_1, x_2, \dots, x_n$$$ ($$$0 < x_i < m$$$) - 机器人的起始坐标。

每个测试用例的第三行包含 $$$n$$$ 空格分隔的字符“L”或“R”——机器人的起始方向(“L”代表左,“R”代表右)。

测试用例中的所有坐标 $$$x_i$$$ 都是不同的。

所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印 $$$n$$$ 整数 - 对于第 $$$i$$$ 个机器人,输出它爆炸的时间(如果爆炸),否则输出 $$$-1$$$。

示例

输入 #1

5
7 12
1 2 3 4 9 10 11
R R L L R R R
2 10
1 6
R R
2 10
1 3
L L
1 10
5
R
7 8
6 1 7 2 3 5 4
R L R L L L L

输出 #1

1 1 1 1 2 -1 2 
-1 -1 
2 2 
-1 
-1 2 7 3 2 7 3

注意

这是第一个测试用例的秒 $$$0, 1, 2$$$ 和 $$$3$$$ 的图片:

请注意,机器人 $$$2$$$ 和 $$$3$$$ 不会发生碰撞,因为它们在同一点 $$$2.5$$$ 相遇,该点不是整数。

第二个 $$$3$$$ 机器人 $$$6$$$ 就无限行驶,因为没有机器人可以碰撞。