3671. 唐纳德先生与领土扩张

单点时限: 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$),和一个字符 CD,分别表示目前有多少个城邦,以及最左边的城邦是属于你 (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$。

输出格式

对于每组测试数据,输出一行三个整数,分别为:所需的时间,唐纳德先生的城池数量,你的城池数量。

样例

Input
5
2 D
2 3
2 D
3 3
2 C
4 3
4 D
2 1 2 3
1 D
9
Output
2 0 5
3 6 0
0 3 4
5 8 0
0 9 0

提示

样例分别为:DDCCCDDDCCCCCCCDDDDDCDDCCCDDDDDDDDD

以第四个样例为例,其收敛经历了下述过程:DDCDDCCCDDDDCCCCDDDDDCCCDDDDDDCCDDDDDDDCDDDDDDDD

4 人解决,28 人已尝试。

5 份提交通过,共有 72 份提交。

9.2 EMB 奖励。

创建: 1 年,6 月前.

修改: 1 年,6 月前.

最后提交: 1 年,4 月前.

来源: EOJ Monthly 2019.1

题目标签