← 返回题目列表

Codeforces · 1264/A

A. 美丽的地区比赛

中文机器翻译题面 查看原题

美丽地区大赛(BeRC)就这样结束了! $$$n$$$ 学生参加了比赛。最终排名已经已知:第 $$$i$$$ 位的参与者解决了 $$$p_i$$$ 问题。由于参与者主要按已解决问题的数量排序,因此 $$$p_1 \ge p_2 \ge \dots \ge p_n$$$。

帮助评审团分发金、银、铜牌。令它们的数字分别为$$$g$$$、$$$s$$$ 和$$$b$$$。以下是规则中的要求列表,所有这些要求都必须满足:

- 对于三种类型的奖牌中的每一种,必须至少授予一枚奖牌(即$$$g>0$$$、$$$s>0$$$和$$$b>0$$$);
- 金牌数量必须严格小于银牌数量和铜牌数量(即$$$g<s$$$和$$$g<b$$$,但$$$s$$$和$$$b$$$之间没有要求);
- 每位金牌获得者必须解决比银牌获得者更多的问题;
- 每个银牌获得者必须严格解决比铜牌获得者更多的问题;
- 每个铜牌获得者必须严格解决比任何未获得奖牌的参赛者更多的问题;
- 奖牌获得者总数 $$$g+s+b$$$ 不应超过所有参与者的一半(例如,如果 $$$n=21$$$,则您最多可以奖励 $$$10$$$ 参与者,如果 $$$n=26$$$,则您最多可以奖励 $$$13$$$ 参与者)。

评审团希望向最大数量的参与者颁发奖牌(即最大化 $$$g+s+b$$$),以便满足上面列出的所有项目。帮助评审团找到这样的颁奖方式。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10000$$$) — 输入中测试用例的数量。然后是 $$$t$$$ 测试用例。

测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 4\cdot10^5$$$) — BeRC 参与者的数量。测试用例的第二行包含整数 $$$p_1, p_2, \dots, p_n$$$ ($$$0 \le p_i \le 10^6$$$),其中 $$$p_i$$$ 等于最终排名中第 $$$i$$$ 参与者解决的问题数。值 $$$p_i$$$ 按非递增顺序排序,即 $$$p_1 \ge p_2 \ge \dots \ge p_n$$$。

输入中所有测试用例的 $$$n$$$ 总和不超过 $$$4\cdot10^5$$$。

输出

打印 $$$t$$$ 行,第 $$$j$$$ 行应包含第 $$$j$$$ 测试用例的答案。

答案由三个非负整数$$$g、s、b$$$组成。

- 如果无法用奖牌奖励参与者,则打印 $$$g=s=b=0$$$,以便同时满足声明中的所有要求。
- 否则,打印三个正数 $$$g, s, b$$$ — 分别可能获得的金牌数、银牌数和铜牌数。 $$$g+s+b$$$ 的总和应该是最大可能的。如果有多个答案,请打印其中任何一个。

示例

输入 #1

5
12
5 4 4 3 2 2 1 1 1 1 1 1
4
4 3 2 1
1
1000000
20
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
32
64 64 63 58 58 58 58 58 37 37 37 37 34 34 28 28 28 28 28 28 24 24 19 17 17 17 17 16 16 16 16 11

输出 #1

1 2 3
0 0 0
0 0 0
2 5 3
2 6 6

注意

在第一个测试用例中,可以奖励 $$$1$$$ 金牌、$$$2$$$ 银牌和 $$$3$$$ 铜牌。在这种情况下,完成 $$$5$$$ 任务的参与者将获得金牌,完成 $$$4$$$ 任务的参与者将获得银牌,完成 $$$2$$$ 或 $$$3$$$ 任务的参与者将获得铜牌。完全解决 $$$1$$$ 任务的参与者将不会获得奖励。很容易看出,在这种情况下,所有条件都满足,并且可以通过这种方式奖励参与者。授予超过 $$$6$$$ 奖牌是不可能的,因为奖牌数量不应超过参与者人数的一半。答案 $$$1$$$、$$$3$$$、$$$2$$$ 在这个测试用例中也是正确的。

在第二个和第三个测试用例中,不可能奖励奖牌,因为每种类型至少应该给予一枚奖牌,但奖牌数量不能超过参与者人数的一半。