The Return of the Reverse Flash
All submissions for this problem are available.
Eobard Thawne, "The Reverse Flash" finally figured out what time period "The Flash" is from. He also figured out a way to get back to his time by using the tachyon particles. But Flash stopped him and locked him up in the meta-human cell. But when Flash captured the Reverse Flash, he ruptured the timeline because of which Cisco Ramon is affected. Harrison Wells said that the only way to save Cisco is to restore the timeline. So, Flash has to send Reverse Flash back to the future as quickly as possible.
Flash's speed coupled with Thawne's speed will be enough to catapault Thawne through the time continuum. The only thing Flash has to do is to provide Thawne with "enough momentum" to get him past the space-time barrier. Momentum here is proportional to the maximum sum subarray. The more the maximum sum, the more is the momentum. Enough momentum here means the maximum possible value of the maximum sum sub array. Harrison Wells found that the maximum sum subarray of any array may increase if we rearrange the elements of the array. So, to achieve enough momentum, they have to try all the possible re-arrangements of the array and find the maximum possible value of the maximum sum sub array.
Now Flash needs your help. He wants you to find the maximum possible value of the maximum sum subarray. He also wants the arrangement of the array which yields that maximum value. If more than one arrangement exists, print the number of such arrangements (modulo 1000000007) and also print the lexicographically smallest arrangement.
1) For clarification on what is maximum sum subarray, please refer this link
2) Even if the number of arrangements possible is 1, print that.
The first line consists of 't', the number of test cases.
Each test case has two lines, the first line being 'n', the array size and the second line consists of the array.
1 <= t <= 1000
1 <= n <= 10^5
1 <= | a[i] | <= 10^3 ( | a[i] | = Absolute value of a[i]).
For each test case, print the required output. (Refer example for clarity).
Input: 2 2 -10 11 3 3 2 1 Output: 11 2 -10 11 6 6 1 2 3
Example case 1:
The given array is [-10, 11]. There are 2 different arrangements of this array.
1) [-10, 11]
2) [11, -10]
The maximum sum subarray of both the above arrangements is 11. This value corresponds to the o/p line 1.
The number of arrangements which has the maximum subarray is 2. This value corresponds to the o/p line 2.
The lexicographically smallest arrangement among the two is [-10, 11] which is printed in the o/p line 3.
Example case 2:
The given array is [3, 2, 1]. There are 6 different arrangements of this array.
1) [3, 2, 1]
2) [3, 1, 2]
3) [2, 1, 3]
4) [2, 3, 1]
5) [1, 2, 3]
6) [1, 3, 2]
The maximum sum subarray of all the above arrangements is 6. This value corresponds to the o/p line 4.
The number of arrangements which has the maximum subarray is 6. This value corresponds to the o/p line 5.
The lexicographically smallest arrangement among the two is [1, 2, 3] which is printed in the o/p line 6.
|Time Limit:||1 - 1.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.