codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.