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.
- 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 space-separated integers A1, A2, ..., AN.
For each test case, print a single line containing N characters. For each K (1 ≤ K ≤ N), the K-th of these characters should be '1' if it is possible to partition the array in the desired way or '0' if it is impossible.
- 1 ≤ T ≤ 1,000,000
- 1 ≤ N ≤ 1,000,000
- 1 ≤ sum of N over all test cases ≤ 1,000,000
- 1 ≤ Ai ≤ 109 for each valid i
Subtask #1 (30 points): sum of N over all test cases ≤ 10,000
Subtask #2 (70 points): original constraints
Input: 3 5 1 4 2 3 5 4 1 1 1 1 4 1 1 2 2 Output: 10100 1101 1010
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).
|Tags||easy-medium, ltime58, maths, mgch, sieve, sum|
|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|
Fetching successful submissions
If you are still having problems, see a sample solution here.