Partitions

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
You are given an array A with size N. For each K between 1 and N (inclusive), find out if it is possible to partition (split) the array A into K contiguous subarrays such that the sum of elements within each of these subarrays is the same. Each element of the original array should belong to exactly one subarray.
Input
 The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
 The first line of each test case contains a single integer N.
 The second line contains N spaceseparated integers A_{1}, A_{2}, ..., A_{N}.
Output
For each test case, print a single line containing N characters. For each K (1 ≤ K ≤ N), the Kth of these characters should be '1' if it is possible to partition the array in the desired way or '0' if it is impossible.
Constraints
 1 ≤ T ≤ 1,000,000
 1 ≤ N ≤ 1,000,000
 1 ≤ sum of N over all test cases ≤ 1,000,000
 1 ≤ A_{i} ≤ 10^{9} for each valid i
Subtasks
Subtask #1 (30 points): sum of N over all test cases ≤ 10,000
Subtask #2 (70 points): original constraints
Example
Input: 3 5 1 4 2 3 5 4 1 1 1 1 4 1 1 2 2 Output: 10100 1101 1010
Explanation
Example case 1: There are two possible partitions: into exactly 1 array (with sum 1+4+3+2+5) or into exactly 3 arrays (with sums 1+4 = 2+3 = 5).
Author:  mgch 
Tester:  lg5293 
Tags  easymedium, ltime58, maths, mgch, sieve, sum 
Date Added:  27032018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 