2259C.md (2419B)
1 Source: https://codeforces.com/problemset/problem/2259/C 2 3 C. 101 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 The score of an array $b$ of length $m$ is defined as the maximum length of a subarray of $b$ such that the first and last elements of the subarray are equal to $1$ and all other elements in the subarray are equal to $0$. Formally, the score of $b$ is equal to the maximum integer $k$ for which there exists an index $i$ such that: 22 23 * $1 \leq i \leq m - k + 1$ 24 * $b_i = b_{i+k-1} = 1$ 25 * $b_{i+1} = b_{i+2} = \ldots = b_{i+k-2} = 0$ 26 27 If there is no subarray meeting the requirements, the score of $b$ is $0$. 28 29 You are given an array $a_1, a_2, \ldots, a_n$, such that each element is equal to one of $-1$, $0$, or $1$. Replace each $-1$ with either a $0$ or $1$ such that the score of $a$ is maximal over all possible ways to replace the $-1$s in $a$. 30 31 Input 32 33 The first line of each input contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 34 35 The first line of each test case contains $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of $a$. 36 37 The second line of each test case contains $a_1, a_2, \ldots, a_n$ ($a_i \in \{-1, 0, 1\}$) — the array $a$. 38 39 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 40 41 Output 42 43 For each test case, output $n$ space separated integers representing $a$ after the $-1$s were replaced with $0$s or $1$s. If there are multiple possible solutions, output any. 44 45 Example 46 47 Input 48 49 ``` 50 10 51 52 6 53 54 1 0 -1 0 0 1 55 56 7 57 58 0 -1 0 0 1 0 1 59 60 5 61 62 -1 0 0 -1 0 63 64 4 65 66 0 0 0 0 67 68 1 69 70 -1 71 72 6 73 74 1 0 1 0 0 -1 75 76 7 77 78 0 1 0 0 0 1 0 79 80 6 81 82 -1 -1 -1 -1 -1 -1 83 84 7 85 86 -1 0 1 -1 0 0 1 87 88 3 89 90 -1 0 0 91 ``` 92 93 Output 94 95 ``` 96 1 0 0 0 0 1 97 0 1 0 0 1 0 1 98 1 0 0 1 0 99 0 0 0 0 100 1 101 1 0 1 0 0 1 102 0 1 0 0 0 1 0 103 1 0 0 0 0 1 104 0 0 1 0 0 0 1 105 1 0 0 106 ``` 107 108 Note 109 110 In the first test case, we can change the only $-1$ to a $0$, making $a = [1, 0, 0, 0, 0, 1]$. Since the first and last elements of $a$ are equal to $1$, and all other elements are $0$, the score of $a$ is $6$. 111 112 In the third test case, changing both $-1$s to $1$s makes $a = [1, 0, 0, 1, 0]$, and the largest subarray that satisfies the conditions in the statement is from the $1$-st index to the $4$-th index. 113 114 In the fifth test case, we set the only $-1$ to $1$, making $a = [1]$, meaning the largest subarray that satisfies the conditions in the statement is the full array.