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.