← 返回题目列表

AtCoder · awc0092_b

B. 机器人在走廊里来回走动

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

分数: 300 分

问题陈述

高桥正在一条长长的笔直走廊里进行机器人运动实验 L。该走廊对应区间 [0, L] 在一条数轴上,两端都有墙(坐标 0 和坐标 L).

有 N 走廊里的机器人,以及 i第机器人(1 \leq i \leq N) 放置在坐标处 X_i 时间 0。每个机器人都有一个速度 V_i 设置时间 0。一个机器人 V_i > 0 匀速移动 |V_i| 在增加坐标的方向(正方向)上,机器人 V_i < 0 匀速移动 |V_i| 在坐标递减的方向(负方向),并且机器人 V_i = 0 不动并留在原地。这里,速度的单位是坐标单位除以时间单位。

当机器人到达走廊尽头时(坐标 0 或坐标 L),其速度符号立即反转,并继续以相同速度向相反方向移动。这种反射可以重复任意多次,并且机器人始终保持在区间内 [0, L].

此反射规则有时也适用 0。具体来说,初始位置在墙上的机器人的行为如下:

  • 坐标中的机器人 0:如果 V_i < 0,其速度在时间处立即反转 0,并且它开始以速度正方向移动 |V_i|。如果 V_i \geq 0,不反转并以速度移动 V_i (如果 V_i = 0,它保持在原位)。
  • 坐标中的机器人 L:如果 V_i > 0,其速度在时间处立即反转 0,并且它开始以速度向负方向移动 |V_i|。如果 V_i \leq 0,不反转并以速度移动 V_i (如果 V_i = 0,它保持在原位)。

每个机器人独立移动。即使两个或多个机器人到达同一坐标,它们也会相互穿过,不会影响彼此的运动。

找到每个的坐标 N 机器人当时 T.

保证在给定的输入中,每个机器人在某个时刻的坐标 T 始终是整数。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq L \leq 10^9
  • 0 \leq T \leq 10^9
  • 0 \leq X_i \leq L (1 \leq i \leq N)
  • -10^9 \leq V_i \leq 10^9 (1 \leq i \leq N)
  • 所有输入均为整数
  • 各机器人此时的坐标 T 始终是整数

输入

N L T
X_1 V_1
X_2 V_2
\vdots
X_N V_N
  • 第一行包含三个空格分隔的整数: N 代表机器人数量, L 代表走廊的长度,以及 T 代表查询的时间。
  • 从第 2 行到 (N + 1)第行,此时的初始位置和速度 给出了每个机器人的 0 。
  • 的 (1 + i)- 第行 (1 \leq i \leq N) 包含初始位置 X_i 和速度 V_i 的 i第一个机器人,以空格分隔。

输出

输出 N 行。的 i- 第行 (1 \leq i \leq N)应包含的坐标 i当时第个机器人 T.


示例输入 1

3 10 3
2 1
8 3
5 -2

示例输出 1

5
3
1

示例输入 2

4 6 5
0 -3
6 4
3 0
1 2

示例输出 2

3
2
3
1

示例输入 3

5 100 7
10 15
50 -30
0 20
99 -1
100 -10

示例输出 3

85
40
60
92
30

示例输入 4

6 1000000000 1000000000
500000000 0
0 1
1 -1
0 2
500000000 3
999999999 1

示例输出 4

500000000
1000000000
999999999
0
500000000
1

示例输入 5

1 1 0
0 0

示例输出 5

0