机器人巡游
测试数据来自 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
- 通过率
- ?
- 上传者