P6303 [eJOI 2018] AB Strings

**This problem is translated from [eJOI2018](http://ejoi2018.org/) Problem C.** ***AB-Strings***.

You have two strings $s, t$, and they contain only the letters `a` and `b`. You may perform the following operation multiple times: choose a prefix of $s$ and a prefix of $t$, and swap them. (Note that the prefix can be **empty** or the entire string.) Your task is to find a sequence of operations such that after performing them, one string contains only the character `a`, and the other contains only the character `b`. You should use as few operations as possible, but a non-optimal solution may still get partial points. For details, see the “Constraints and Hint” section.

The input consists of two lines, containing the two strings $s, t$.

Output an integer $n$ ($0\leq n\leq 5\times 10^5$) on the first line, representing the total number of operations. In the next $n$ lines, each line contains two integers $a_i, b_i$, which are the prefix lengths of $s$ and $t$ to be swapped in this operation, respectively. If there are multiple valid solutions, you may output any of them.

#### Explanation for Sample $1$: In this sample, first swap the prefix of length $1$ of the first string with the prefix of length $0$ of the second string, i.e. insert `b` at the beginning of the second string. The two strings become `ab` and `bbb`. Next, swap the prefix of length $1$ of the first string with the prefix of length $3$ of the second string, i.e. swap `a` and `bbb`. The two strings become `bbbb` and `a`, achieving the goal. #### Explanation for Sample $2$: It is already in the required final state. ------ #### Scoring Policy Let $n$ be the number of operations you output, and $m$ be the number in the official answer. **This problem uses SPJ**. - If for all test cases $n=m$, you will get $100\%$ of the score. - If for all test cases $n\leq m+2$, you will get $70\%$ of the score. (Rounded to the nearest integer.) - If for all test cases $n\leq 2m+2$, you will get $50\%$ of the score. (Rounded to the nearest integer.) - If for all test cases $n\leq 5\times 10^5$, you will get $30\%$ of the score. (Rounded to the nearest integer.) - If for at least one test case $n > 5\times 10^5$, you will get $0\%$ of the score. ---- For $100\%$ of the testdata, it is guaranteed that $1\leq \lvert s\rvert,\lvert t\rvert \leq 2\times 10^5$, where $\lvert s\rvert,\lvert t\rvert$ denote the lengths of $s, t$, respectively. It is also guaranteed that at least one string contains at least one character `a`, and at least one string contains at least one character `b`. #### Constraints |Subtask ID|Score|Constraints| |:-:|:-:|:-:| |$1$|$5$| $1\leq \lvert s\rvert,\lvert t\rvert \leq 6$, and there is exactly one character `a` in total in the two strings.| |$2$|$10$| $1\leq \lvert s\rvert,\lvert t\rvert \leq 6$.| |$3$|$20$| $1\leq \lvert s\rvert,\lvert t\rvert \leq 50$.| |$4$|$20$| $1\leq \lvert s\rvert,\lvert t\rvert \leq 250$.| |$5$|$20$| $1\leq \lvert s\rvert,\lvert t\rvert \leq 2\times 10^3$.| |$6$|$25$|No additional constraints.| Translated by ChatGPT 5