单点时限: 6.0 sec
内存限制: 1024 MB
在一个一维的世界里,有 $m$ 座城池。相邻的城池(也就是 $i$ 和 $i+1$ 座城市)如果属于同一个国家,他们就连成一个城邦。于是这 $m$ 座城池连成了 $n$ 个城邦。在发生战争时,城邦的大小是决定成败的最关键因素。
唐纳德先生与你各坐拥这个世界的一部分城池,你们经历了数千年的战争在形成了现在的局面。很不幸的是,从现在开始,你们的命运就不在自己手中了。有一个观察者,早就厌烦了这个世界里大大小小的持续了几千年的战争,他决定启用高维力量,一劳永逸地解决战乱。
于是他制定了以下规则:对于观察者来说,每一秒,唐纳德先生手下的城邦会同时在他们的右边界上发起进攻;你手下的城邦会在左边界上发起进攻。这就会产生战争。战争的成败取决于城邦的所占的城池多少,城邦大者赢;如果一样大,唐纳德先生会赢。(是的,这很不公平。)赢的一方可以在边界线上进一步,也就是说吃掉对方的一个城池。如果这是对方的城邦的最后一个城池,那么这个城邦就会消失,可能会有城邦与城邦会连成新的城邦。从而,在若干秒后,整个世界的格局就再也不会改变了。也就再也不会有战争。
听起来很完美?现在我想提前知道结果:要多少秒后格局才会定下来?到那时,唐纳德和你所拥有的城池数量各是多少?
第一行一个整数 $t$ ($1 \le t \le 10^5$),表示有 $t$ 组测试数据。
对于每组数据,第一行是一个正整数 $n$ ($1 \le n \le 10^6$),和一个字符 C
或 D
,分别表示目前有多少个城邦,以及最左边的城邦是属于你 (C) 还是唐纳德先生 (D)。
第二行有 $n$ 个正整数用空格隔开 $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^{12}$, $a_1+a_2+\cdots+a_n = m$),表示从左往右的城邦大小。如果最左边的城邦是 C
,那么 $a_1$ 对应 C,$a_2$ 对应 D,$a_3$ 对应 C,以此类推;如果最左边的城邦是 D
,那么 $a_1$ 对应 D,以此类推。
保证所有测试数据的 $n$ 之和不超过 $10^6$。
对于每组测试数据,输出一行三个整数,分别为:所需的时间,唐纳德先生的城池数量,你的城池数量。
5 2 D 2 3 2 D 3 3 2 C 4 3 4 D 2 1 2 3 1 D 9
2 0 5 3 6 0 0 3 4 5 8 0 0 9 0
样例分别为:DDCCC
,DDDCCC
,CCCCDDD
,DDCDDCCC
,DDDDDDDDD
。
以第四个样例为例,其收敛经历了下述过程:DDCDDCCC
— DDDDCCCC
— DDDDDCCC
— DDDDDDCC
— DDDDDDDC
— DDDDDDDD
。