/ / 题库 /

机器人巡游

机器人巡游

测试数据来自 nnu_contest/1287

机器人巡游

时间限制:1s

空间限制:64MB

题目描述

现有一数轴。数轴上两个点\(x=0,x=m\)上各有一堵墙。

一些机器人初始在\([0,m]\)上以每秒\(1\)的速度来回巡游。若机器人碰到墙,它就会调转方向,速度的大小不变。

调转方向不计时间。

若两个 正在巡游的 机器人在 某整数时间 处于同一位置,则它们会相撞,并立刻在原地停下,不再进行巡游。由于它们已经停止巡游,所以不会和其他机器人再次相撞。特别地,若两个正在巡游的机器人在 非整数时间 处于同一位置,则 无事发生

现给出机器人的初始位置和初始方向,问各机器人停止巡游的时间。特别地,若机器人不会停下来,认为其停止巡游时间为\(-1\)。

输入格式

第一行两个正整数\( n,m\)。表示机器人的数量和数轴的右边界

第二行,每行\(n\)个整数\(loc_i\),表示初始位置

第三行,每行\(n\)个整数\(v_i\),表示初始方向。其中'R'表示机器人初始沿数轴正方向巡游,'L'表示初始沿数轴负方向巡游。

初始位置将按照从小到大的顺序给出,即\(loc_1<loc_2<...\)

输出格式

\(n\)个整数,用空格隔开。按照原先的顺序,输出各个机器人的停止巡游时间。

特别地,若某机器人不会停下来,则用\(-1\)表示。

样例输入1

2 10
1 3
L L

样例输出1

2 2

样例1解释

第0秒,两个机器人在1,3位置,方向向左

第1秒,位置是(0,2),此时左侧的机器人方向变为右。

第2秒,(1,1),两机器人相撞。

样例输入2

7 12
1 2 3 4 9 10 11
R R L L R R R

样例输出2

1 1 1 1 2 -1 2 

样例2解释

位于(1,3),(2,4)的两对机器人在第一秒运动后就会相撞, 注意(2,3)是不会相撞的,因为它们在0.5秒时相遇,不是整数时间。

接下来看9,10,11的三个机器人,可以分析出第2秒\(9,11\)的两个机器人相撞,而场上仅剩下一个机器人,它将永远在数轴上巡游。

数据范围及限制

共\(25\)组测试数据,每个测试点\( 10\)分。

对于\(40\%\)的数据,\(1\le n\le m\le 15\)

对于\(80\%\)的数据,\(1\le n\le 200, 1\le m\le 10^7\)

对于\(100\%\)的数据,\(1\le n\le 10^5, 1\le m\le 10^8\)。

初始位置将按照从小到大的顺序给出,即\(loc_1<loc_2<...\)

任意两个机器人的初始位置不同。初始位置一定在\((0,m)\)之间,初始方向一定是'R'或'L'

信息

ID
2331
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者