2048C.md (2329B)
1 Source: https://codeforces.com/problemset/problem/2048/C 2 3 C. Kevin and Binary Strings 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 Kevin discovered a binary string $s$ that starts with 1 in the river at Moonlit River Park and handed it over to you. Your task is to select two non-empty substrings$^{\text{∗}}$ of $s$ (which can be overlapped) to maximize the XOR value of these two substrings. 22 23 The XOR of two binary strings $a$ and $b$ is defined as the result of the $\oplus$ operation applied to the two numbers obtained by interpreting $a$ and $b$ as binary numbers, with the leftmost bit representing the highest value. Here, $\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). 24 25 The strings you choose may have leading zeros. 26 27 $^{\text{∗}}$A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end. 28 29 Input 30 31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). 32 33 The only line of each test case contains a binary string $s$ that starts with 1 ($1\le\lvert s\rvert\le 5000$). 34 35 It is guaranteed that the sum of $\lvert s\rvert$ over all test cases doesn't exceed $5000$. 36 37 Output 38 39 For each test case, output four integers $l_1, r_1, l_2, r_2$ ($1 \le l_1 \le r_1 \le |s|$, $1 \le l_2 \le r_2 \le |s|$) — in the case the two substrings you selected are $s_{l_1} s_{l_1 + 1} \ldots s_{r_1}$ and $s_{l_2} s_{l_2 + 1} \ldots s_{r_2}$. 40 41 If there are multiple solutions, print any of them. 42 43 Example 44 45 Input 46 47 ``` 48 5 49 50 111 51 52 1000 53 54 10111 55 56 11101 57 58 1100010001101 59 ``` 60 61 Output 62 63 ``` 64 2 2 1 3 65 1 3 1 4 66 1 5 1 4 67 3 4 1 5 68 1 13 1 11 69 ``` 70 71 Note 72 73 In the first test case, we can choose $ s_2=\texttt{1} $ and $ s_1 s_2 s_3=\texttt{111} $, and $ \texttt{1}\oplus\texttt{111}=\texttt{110} $. It can be proven that it is impossible to obtain a larger result. Additionally, $ l_1=3$, $r_1=3$, $l_2=1$, $r_2=3 $ is also a valid solution. 74 75 In the second test case, $ s_1 s_2 s_3=\texttt{100} $, $ s_1 s_2 s_3 s_4=\texttt{1000} $, the result is $ \texttt{100}\oplus\texttt{1000}=\texttt{1100} $, which is the maximum.