1400C.md (1661B)
1 Source: https://codeforces.com/problemset/problem/1400/C 2 3 C. Binary String Reconstruction 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 Consider the following process. You have a binary string (a string where each character is either 0 or 1) $w$ of length $n$ and an integer $x$. You build a new binary string $s$ consisting of $n$ characters. The $i$-th character of $s$ is chosen as follows: 22 23 * if the character $w_{i-x}$ exists and is equal to 1, then $s_i$ is 1 (formally, if $i \gt x$ and $w_{i-x} = $ 1, then $s_i = $ 1); 24 * if the character $w_{i+x}$ exists and is equal to 1, then $s_i$ is 1 (formally, if $i + x \le n$ and $w_{i+x} = $ 1, then $s_i = $ 1); 25 * if both of the aforementioned conditions are false, then $s_i$ is 0. 26 27 You are given the integer $x$ and the resulting string $s$. Reconstruct the original string $w$. 28 29 Input 30 31 The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases. 32 33 Each test case consists of two lines. The first line contains the resulting string $s$ ($2 \le |s| \le 10^5$, each character of $s$ is either 0 or 1). The second line contains one integer $x$ ($1 \le x \le |s| - 1$). 34 35 The total length of all strings $s$ in the input does not exceed $10^5$. 36 37 Output 38 39 For each test case, print the answer on a separate line as follows: 40 41 * if no string $w$ can produce the string $s$ at the end of the process, print $-1$; 42 * otherwise, print the binary string $w$ consisting of $|s|$ characters. If there are multiple answers, print any of them. 43 44 Example 45 46 Input 47 48 ``` 49 3 50 101110 51 2 52 01 53 1 54 110 55 1 56 ``` 57 58 Output 59 60 ``` 61 111011 62 10 63 -1 64 ```