A13209. Dream Team
编程题
普及/提高-
知识点
题目描述
The first line contains one integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases. Then $t$ test cases follow.
Each test case begins with a line containing one integer $n$ ( $2 \le n \le 10^5$ ) — the number of developers "on the bench".
The second line of a test case contains a sequence of integers $a_1, a_2, \dots, a_n$ ( $-10^4 \le a_i \le 10^4$ ) — the characteristics of the $n$ developers. It is guaranteed that the characteristics are such that the sum of the characteristics in the answer is strictly positive.
It is guaranteed that the sum of $n$ over all test cases in the input doesn't exceed $10^5$ .
Each test case begins with a line containing one integer $n$ ( $2 \le n \le 10^5$ ) — the number of developers "on the bench".
The second line of a test case contains a sequence of integers $a_1, a_2, \dots, a_n$ ( $-10^4 \le a_i \le 10^4$ ) — the characteristics of the $n$ developers. It is guaranteed that the characteristics are such that the sum of the characteristics in the answer is strictly positive.
It is guaranteed that the sum of $n$ over all test cases in the input doesn't exceed $10^5$ .
输入格式
Print the answers for the given $t$ test cases in the order that they appear in the input. In the first line of each answer, print a positive integer $s$ — the sum of the characteristics in the desired subset. The second line should contain only the characters 0 and 1 and match the answer:
- the character in the $i$ -th position should be equal to 1 if the $i$ -th developer belongs to the team;
- the character in the $i$ -th position should be equal to 0 if the $i$ -th developer does not belong to the team.
If there are several answers, print any of them.
- the character in the $i$ -th position should be equal to 1 if the $i$ -th developer belongs to the team;
- the character in the $i$ -th position should be equal to 0 if the $i$ -th developer does not belong to the team.
If there are several answers, print any of them.
输出格式
In the first test case, the maximum subset $a_1, a_3, a_5$ has a sum equal to $3$ , so Polycarp should choose a team with the maximum total sum which is less than $3$ .
In the second test case, the maximum subset $a_1, a_2$ has a sum equal to $12$ , so Polycarp should choose a team with the maximum total sum which is less than $12$ .
In the third test case, the maximum subset $a_1, a_3$ has a sum equal to $9$ .
In the fourth test case, the maximum subset $a_1, a_2$ has a sum equal to $8$ .
In the fifth test case, there are several subsets with a maximum sum equal to $3$ , so Polycarp should choose a team with a lower total sum.
In the second test case, the maximum subset $a_1, a_2$ has a sum equal to $12$ , so Polycarp should choose a team with the maximum total sum which is less than $12$ .
In the third test case, the maximum subset $a_1, a_3$ has a sum equal to $9$ .
In the fourth test case, the maximum subset $a_1, a_2$ has a sum equal to $8$ .
In the fifth test case, there are several subsets with a maximum sum equal to $3$ , so Polycarp should choose a team with a lower total sum.
输入输出样例
输入 #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
说明/提示
In the first test case, the maximum subset $a_1, a_3, a_5$ has a sum equal to $3$ , so Polycarp should choose a team with the maximum total sum which is less than $3$ .
In the second test case, the maximum subset $a_1, a_2$ has a sum equal to $12$ , so Polycarp should choose a team with the maximum total sum which is less than $12$ .
In the third test case, the maximum subset $a_1, a_3$ has a sum equal to $9$ .
In the fourth test case, the maximum subset $a_1, a_2$ has a sum equal to $8$ .
In the fifth test case, there are several subsets with a maximum sum equal to $3$ , so Polycarp should choose a team with a lower total sum.
In the second test case, the maximum subset $a_1, a_2$ has a sum equal to $12$ , so Polycarp should choose a team with the maximum total sum which is less than $12$ .
In the third test case, the maximum subset $a_1, a_3$ has a sum equal to $9$ .
In the fourth test case, the maximum subset $a_1, a_2$ has a sum equal to $8$ .
In the fifth test case, there are several subsets with a maximum sum equal to $3$ , so Polycarp should choose a team with a lower total sum.