← 返回题目列表

Codeforces · 1297/C

C. 梦之队

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

Polycarp 是 IT 公司的项目经理。现在,他需要为他的团队选择开发人员来启动一个新项目。该公司有 $$$n$$$ 开发人员“坐在替补席上”(即不参与其他项目)。 Polycarp 评估了每个人的技能: $$$a_i$$$ ($$$-10^4 \le a_i \le 10^4$$$) — 第 $$$i$$$ 个开发人员的整数特征。该值可以是正值、零甚至负值(有些开发人员会造成干扰)。

Polycarp 为其团队选择一部分开发人员后,团队的实力将由所有选定开发人员的 $$$a_i$$$ 值的总和决定。

Polycarp担心,如果他以最大化$$$a_i$$$特征总和的方式选择团队,其他经理可能会觉得这是不可接受的。因此,他计划创建这样一个团队,使其 $$$a_i$$$ 值的总和严格小于最大可能值。

帮助波利卡普选择符合以下条件的团队:

- 所选团队的所有成员的特征 $$$a_i$$$ 的总和严格小于通过其他方式选择团队可以获得的最大值
- 同时,所选团队的所有成员的 $$$a_i$$$ 的特征总和尽可能最大。

如果按照上述要求,您可以通过多种方式选择团队,那么只需找到其中任何一种即可。

保证所需子集中的特征总和严格为正(即 Polycarp 始终可以选择非空团队)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例都以一行开头,其中包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — “替补”的开发人员数量。

测试用例的第二行包含整数序列 $$$a_1, a_2, \dots, a_n$$$ ($$$-10^4 \le a_i \le 10^4$$$) — $$$n$$$ 开发人员的特征。保证特征使得答案中特征的总和严格为正。

保证输入中所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

按照给定 $$$t$$$ 测试用例在输入中出现的顺序打印答案。在每个答案的第一行,打印一个正整数 $$$s$$$ — 所需子集中的特征之和。第二行应仅包含字符 0 和 1 并与答案匹配:

- 如果第 $$$i$$$ 开发者属于团队,则第 $$$i$$$ 位置的字符应等于 1;
- 如果第 $$$i$$$ 开发人员不属于团队,则第 $$$i$$$ 位置的字符应等于 0。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

5
5
1 -1 1 -1 1
2
11 1
3
5 -3 4
3
5 3 -4
5
-1 0 3 -3 0

输出 #1

2
11101
11
10
6
111
5
100
2
10100

注意

在第一个测试用例中,最大子集 $$$a_1, a_3, a_5$$$ 的总和等于 $$$3$$$,因此 Polycarp 应该选择最大总和小于 $$$3$$$ 的团队。

在第二个测试用例中,最大子集 $$$a_1, a_2$$$ 的总和等于 $$$12$$$,因此 Polycarp 应选择最大总和小于 $$$12$$$ 的团队。

在第三个测试用例中,最大子集 $$$a_1, a_3$$$ 的总和等于 $$$9$$$。

在第四个测试用例中,最大子集 $$$a_1, a_2$$$ 的总和等于 $$$8$$$。

在第五个测试用例中,有几个子集的最大总和等于 $$$3$$$,因此 Polycarp 应该选择总和较低的团队。