Educational Codeforces Round 109 (Rated for Div. 2) C. Robot Collisions（几何计算，贪心）

那一天的战绩：

题目大意：
输入t（1<t<1000）t为测试数据个数；
每个测试有一个n，m；n为机器人的个数，m为墙的坐标；
接下来n个数字是机器人的起始坐标；
下一行n个字母是每个机器人的方向；
（机器人只会向右走或向左走，每秒走一个单位，走到坐标0或m就调头）
题目的要求是输出每个机器人相撞时爆炸的时间，没有爆炸的输出-1；（机器人只会在整点相撞，这个性质会成为后来解题的关键）
爆炸后的机器人自然就没有了，就不会和其他机器人相撞，值得一提的这样是不可能有三个机器人相撞！
只会有两个机器人相撞，如果有三个机器人相撞的话，就和题目自相矛盾了。

机器人的行走轨迹可以通过时间直接算出来，如果时间是第x秒，机器人的初始坐标是d，方向是R的话
每秒坐标加1，那么机器人所在的坐标是d+x，反之，机器人的初始坐标是d，方向是L的话
每秒坐标减1，那么机器人所在的坐标是d-x，那么我们就可以得到计算机器人坐标的公式：

x 为 自 变 量 是 时 间 f ( x ) = { x + d , 方向为R − x + d , 方向为L x为自变量是时间\\ f(x) =

$$\begin{cases} x+d, & \text{方向为R} \\ -x+d, & \text{方向为L} \end{cases}$$ x为自变量是时间f(x)={x+d,−x+d,​方向为R方向为L​
但这只是第一步，还有个条件：机器人走到坐标0或m就调头
这就说明当f(x）为0，或者m时，函数的斜率会转换，使得0<=f(x)<=m,而当机器人在走过了2m的路程后又回到了起始坐标，这就说明机器人的运行轨迹具有周期性，周期为2m；

有了这些我们就可以把所有机器人的轨迹给画在坐标系上了，在进行观察，
相交就意味着两个机器人坐标相等，相等就是相撞，机器人只会在整点相撞，我们就只需要在上面图找整点，再找规律。
那么怎样才会相交？平行肯定不会相交，只有两条斜率不同的直线才可以相交，那么两条直线斜率必定是-1和1，这样就可以相交了，接下来就是如何判断这个相交的点是整数点。
{ y = x + d 1 , L1 y = − x + d 2 , L2

$$\begin{cases} y=x+d1, & \text{L1} \\ y=-x+d2, & \text{L2} \end{cases}$$ {y=x+d1,y=−x+d2,​L1L2​
这是L1和L2相交的方程，由计算可知$x=\frac{d1+d2}{2}$,很明显x要是整数的话，d1+d2就必须是偶数，不然无法整除，那么d1,d2只有两种情况，都是d1,d2奇数和都是d1,d2都是偶数，也就说初始值是奇数的机器人只会和初始值是奇数的机器人相撞，同理偶数也是。（这里自己画图去证明）

所以我们要分类，把初始值是奇数的分成一类，偶数的分成一类，分开求；
接下来就是要求每个机器人的最短相撞时间，这里就要用到一个贪心算法（证明过于复杂，后面有时间的话我会考虑更新的 ） ；（证明要花很久的时间，如果有人要看的话我会更新的）
我们把机器人分类后，把他们按照初始值排序（升序），再按顺序放进栈里面，如果栈顶的方向是
R，入栈元素方向是L，那么栈顶元素和入栈元素的时间就是两者的初始值相减除以2，然后这两个元素出栈，剩下的元素方向排列必然是L……LR……R，或L……L，然后从栈底和栈顶开始扫描每两个一组，确定时间（由专门的公式自己推），如果剩下一堆LR则单独判断如果剩的由单独的L或R，那就是不会爆炸的机器人输出-1就可以了。

#include <bits/stdc++.h>
#define Mid ((l + r) / 2)
#define lson (rt << 1)
#define rson (rt << 1 | 1)
using namespace std;
int read() {
	char c; int num, f = 1;
	while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0';
	while(c = getchar(), isdigit(c)) num = num * 10 + c - '0';
	return f * num;
}
const int N = 3e5 + 1009;
struct node {
	int pos, dir, id;
} a[N], tmp[N], sta[N];
int n, m, tot, cnt, tt[N];
int cmp(const node & a, const node &b) {return a.pos < b.pos;}
void work1() {
	sort(tmp + 1, tmp + 1 + tot, cmp);
	cnt = 0;
	for(int i = 1; i <= tot; i++) {
		if(cnt != 0 && sta[cnt].dir == 1 && tmp[i].dir == 0) {
			tt[sta[cnt].id] = tt[tmp[i].id] = (tmp[i].pos - sta[cnt].pos) / 2;
			cnt--;
		} else sta[++cnt] = tmp[i];
	}
	int mid = 0, l = 1, r = cnt;
	for(int i = 1; i <= cnt; i++) 
		if(sta[i].dir == 0)
			mid = i;
	for(int i = 2; i <= mid; i += 2) {
		tt[sta[i].id] = tt[sta[i - 1].id] = sta[i - 1].pos + (sta[i].pos - sta[i - 1].pos) / 2;
		l = i + 1;
	}
	for(int i = cnt - 1; i > mid; i -= 2) {
		tt[sta[i].id] = tt[sta[i + 1].id] = m - sta[i + 1].pos + (sta[i + 1].pos - sta[i].pos) / 2;
		r = i - 1;
	}
	if(l < r) {
		tt[sta[l].id] = tt[sta[r].id] = (sta[l].pos + (m - sta[r].pos) + m) / 2;
	}
}
void work() {
	cin >> n >> m; tot = 0;
	for(int i = 1; i <= n; i++) tt[i] = -1;
	for(int i = 1; i <= n; i++) cin >> a[i].pos;
	for(int i = 1; i <= n; i++) {
		char c;
		cin >> c;
		a[i].dir = c == 'R';
		a[i].id = i;
	}
	for(int i = 1; i <= n; i++) if(a[i].pos & 1){
		tmp[++tot] = a[i];
	}
	work1();
	tot = 0;
	for(int i = 1; i <= n; i++) if(a[i].pos % 2 == 0) {
		tmp[++tot] = a[i];
	}
	work1();
	for(int i = 1; i <= n; i++)
		cout << tt[i] << " ";
	cout << endl;
}
signed main()
{
	int Case = read();
	while(Case--) work();
	return 0;
}
/*

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

*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79