codeforces-scrape

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

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 ```