Dream Team - VietMX's Blog

Polycarp is the project manager in the IT-company. Right now, he needs to choose developers for his team to start a new project. The company has $n$ developers “on the bench” (i.e not involved in other projects). Polycarp assessed the skills of each of them: $a_i$ ($-10^4 \le a_i \le 10^4$) — an integer characteristic of the $i$-th developer. This value can be either positive, zero or even negative (some developers cause distractions).

After Polycarp chooses a subset of developers for his team, the strength of the team will be determined by the sum of $a_i$ values for all selected developers.

Polycarp fears that if he chooses a team in such a way that maximizes the sum of the characteristics of $a_i$, other managers may find this unacceptable. For this reason, he plans to create such a team that the sum of the $a_i$ values for it is strictly less than the maximum possible value.

Help Polycarp choose any team that:

the sum of the characteristics $a_i$ for all members of the selected team is strictly less than the maximum value that can be achieved by choosing the team in some other way
and at the same time, the sum of the characteristics of $a_i$ for all members of the selected team is the greatest possible.

If, following the requirements above, you can select a team in several ways, then just find any of them.

It’s guaranteed that the sum of the characteristics in the desired subset is strictly positive (i.e. Polycarp can always choose a non-empty team).Input

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$.Output

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.Exampleinput

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

output

Note

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.

Solution:

private fun readLn() = readLine()!! // string line
private fun readInt() = readLn().toInt() // single int
private fun readLong() = readLn().toLong() // single long
private fun readDouble() = readLn().toDouble() // single double
private fun readStrings() = readLn().split(" ") // list of strings
private fun readInts() = readStrings().map { it.toInt() } // list of ints
private fun readLongs() = readStrings().map { it.toLong() } // list of longs
private fun readDoubles() = readStrings().map { it.toDouble() } // list of doubles

fun main(args: Array<String>) {
var t = readInt()
while (t-- > 0) {
var n = readInt()
var a = readInts()
var s = 0
for (x in a) {
s += maxOf(x, 0)
}
var t = CharArray(n)
for (i in 0 until n) {
t[i] = (if (a[i] > 0) '1' else '0')
}
var v = 787788
var who = -1
for (i in 0 until n) {
if (a[i] > 0) {
if (a[i] < v) {
                    v = a[i]
                    who = i
                }
            }
            if (a[i] < 0) {
                if (-a[i] < v) {
                    v = -a[i]
                    who = i
                }
            }
        }
        t[who] = (if (a[who] > 0) '0' else '1')
println(s - v)
println(t.joinToString(""))
}
}

Restoring Three Numbers