1512C.md (2051B)
1 Source: https://codeforces.com/problemset/problem/1512/C 2 3 C. A-B Palindrome 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 a string $s$ consisting of the characters '0', '1', and '?'. You need to replace all the characters with '?' in the string $s$ by '0' or '1' so that the string becomes a palindrome and has exactly $a$ characters '0' and exactly $b$ characters '1'. Note that each of the characters '?' is replaced independently from the others. 22 23 A string $t$ of length $n$ is called a palindrome if the equality $t[i] = t[n-i+1]$ is true for all $i$ ($1 \le i \le n$). 24 25 For example, if $s=$"01?????0", $a=4$ and $b=4$, then you can replace the characters '?' in the following ways: 26 27 * "01011010"; 28 * "01100110". 29 30 For the given string $s$ and the numbers $a$ and $b$, replace all the characters with '?' in the string $s$ by '0' or '1' so that the string becomes a palindrome and has exactly $a$ characters '0' and exactly $b$ characters '1'. 31 32 Input 33 34 The first line contains a single integer $t$ ($1 \le t \le 10^4$). Then $t$ test cases follow. 35 36 The first line of each test case contains two integers $a$ and $b$ ($0 \le a, b \le 2 \cdot 10^5$, $a + b \ge 1$). 37 38 The second line of each test case contains the string $s$ of length $a+b$, consisting of the characters '0', '1', and '?'. 39 40 It is guaranteed that the sum of the string lengths of $s$ over all test cases does not exceed $2 \cdot 10^5$. 41 42 Output 43 44 For each test case, output: 45 46 * "-1", if you can't replace all the characters '?' in the string $s$ by '0' or '1' so that the string becomes a palindrome and that it contains exactly $a$ characters '0' and exactly $b$ characters '1'; 47 * the string that is obtained as a result of the replacement, otherwise. 48 49 If there are several suitable ways to replace characters, you can output any. 50 51 Example 52 53 Input 54 55 ``` 56 9 57 4 4 58 01?????0 59 3 3 60 ?????? 61 1 0 62 ? 63 2 2 64 0101 65 2 2 66 01?0 67 0 1 68 0 69 0 3 70 1?1 71 2 2 72 ?00? 73 4 3 74 ??010?0 75 ``` 76 77 Output 78 79 ``` 80 01011010 81 -1 82 0 83 -1 84 0110 85 -1 86 111 87 1001 88 0101010 89 ```