codeforces-scrape

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

2146C.md (4777B)


      1 Source: https://codeforces.com/problemset/problem/2146/C
      2 
      3 C. Wrong Binary Search
      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 You are given an integer $n$ and a binary string$^{\text{∗}}$ $s$ of length $n$.
     22 
     23 For a permutation$^{\text{†}}$ $p$ of length $n$ and an integer $x$, we define $\text{find}(x)$ as in the following pseudocode:
     24 
     25 ```
     26 function find(int x):  
     27     l := 1  
     28     r := n  
     29     while l <= r:  
     30         let m be a random integer between l and r (inclusive)  
     31         if p[m] == x  
     32             return m  
     33         if p[m] > x:  
     34             r := m - 1  
     35         else:  
     36             l := m + 1  
     37     return undefined     // not found
     38 ```
     39 
     40 We call an integer $x$ ($1\le x\le n$) stable if and only if $\text{find}(x)$ is always not undefined and $p_{\text{find}(x)}=x$ always holds, no matter how the value of $m$ is selected in the process of the pseudocode.
     41 
     42 You have to construct a permutation $p$ of length $n$, such that:
     43 
     44 * For each $1\le i\le n$, the integer $i$ is stable if and only if $s_i=\mathtt{1}$.
     45 
     46 Or determine that no such permutation exists.
     47 
     48 $^{\text{∗}}$A binary string is a string where each character is either $\mathtt{0}$ or $\mathtt{1}$.
     49 
     50 $^{\text{†}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).
     51 
     52 Input
     53 
     54 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     55 
     56 The first line of each test case contains a single integer $n$ ($2\le n \le 2\cdot 10^5$) — the length of the permutation.
     57 
     58 The second line contains the binary string $s$ of length $n$ ($s_i=\mathtt{0}$ or $\mathtt{1}$).
     59 
     60 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.
     61 
     62 Output
     63 
     64 For each test case:
     65 
     66 * If no such permutation exists, print "NO" in the only line of output.
     67 * Otherwise, print "YES" in the first line of output. Then output $n$ distinct integers $p_1, p_2, \ldots, p_n$ ($1\le p_i\le n$) in the second line — the permutation you constructed.
     68 
     69 You can output the token in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
     70 
     71 If there are multiple answers, you may print any of them.
     72 
     73 Example
     74 
     75 Input
     76 
     77 ```
     78 6
     79 
     80 3
     81 
     82 111
     83 
     84 5
     85 
     86 00000
     87 
     88 5
     89 
     90 10100
     91 
     92 7
     93 
     94 0010000
     95 
     96 11
     97 
     98 00001001100
     99 
    100 12
    101 
    102 011100010000
    103 ```
    104 
    105 Output
    106 
    107 ```
    108 YES
    109 
    110 1 2 3
    111 
    112 YES
    113 
    114 2 4 3 5 1
    115 
    116 NO
    117 
    118 YES
    119 
    120 2 1 3 5 7 6 4
    121 
    122 YES
    123 
    124 2 1 4 3 5 7 6 8 9 11 10
    125 
    126 NO
    127 ```
    128 
    129 Note
    130 
    131 In the first test case, we have constructed $p=[1,2,3]$. Take $\text{find(2)}$ as an example:
    132 
    133 * In the beginning, $l=1$ and $r=3$;
    134 * We will select $m$ as a random integer between $l=1$ and $r=3$.
    135   + If we choose $m=1$:
    136     - $p_1=1 \lt 2$, so $l$ is set to $m + 1 = 2$. Now $l=2$ and $r=3$;
    137     - We will select $m$ as a random integer between $l=2$ and $r=3$.
    138     - If we choose $m=2$: $p_2=2$, so the return value is $2$.
    139     - If we choose $m=3$: $p_3=3 \gt 2$, so $r$ is set to $m-1=2$. Now $l=2$ and $r=2$, so we can only select $m=2$. $p_2=2$, so the return value is $2$.
    140   + If we choose $m=2$:
    141     - $p_2=2$, so the return value is $2$.
    142   + If we choose $m=3$, the process is similar to that when $m=1$ is chosen. The return value is always $2$.
    143 * Thus, no matter how $m$ is selected during the process, the return value of $\text{find}(2)$ is always $2$.
    144 
    145 So $p_{\text{find}(2)}= p_2 = 2$ always holds, and the integer $2$ is stable.
    146 
    147 Similarly, we can show that integers $1$ and $3$ are also stable. Thus, the permutation $p = [1, 2, 3]$ is a valid answer.
    148 
    149 In the second test case, we have constructed $p=[2,4,3,5,1]$. Take $\text{find(3)}$ as an example:
    150 
    151 * In the beginning, $l=1$ and $r=5$;
    152 * We will select $m$ as a random integer between $l=1$ and $r=5$. Let's choose $m=2$;
    153 * $p_2=4 \gt 3$, so $r$ is set to $m-1=1$. Now $l=1$ and $r=1$;
    154 * We will select $m$ as a random integer between $l=1$ and $r=1$. We can only choose $m=1$;
    155 * $p_1=2 \lt 3$, so $l$ is set to $m + 1 = 2$. Now $l=2$ and $r=1$;
    156 * Since $l \gt r$, the loop is exited and the return value is undefined.
    157 
    158 Thus, the return value of $\text{find}(3)$ is undefined, so the integer $3$ is not stable.
    159 
    160 Similarly, we can show that integers $1$, $2$, $4$, and $5$ are also not stable. Thus, $p = [2, 4, 3, 5, 1]$ is a valid answer.
    161 
    162 Some other permutations, such as $p=[5,4,3,2,1]$ and $p=[3,5,1,4,2]$, are also valid answers. You may print any of them.
    163 
    164 In the third test case, it can be proven that no such permutation exists.