CF1698G Long Binary String

有一个长度为 $10^{100}$ 的二进制字符串 $t$，初始时所有位都是 $\texttt{0}$。给定一个二进制字符串 $s$，你可以进行如下操作若干次： - 选择 $t$ 的某个子串，并用 $s$ 与其进行按位异或替换。$^\dagger$ 经过若干次操作后，字符串 $t$ 恰好有两位是 $\texttt{1}$，即存在且仅存在两个不同的下标 $p$ 和 $q$，使得 $t$ 的第 $p$ 位和第 $q$ 位为 $\texttt{1}$，其余所有位均为 $\texttt{0}$。请找出满足条件的字典序最大的 $t$，并输出这两个下标 $p$ 和 $q$，如果不存在这样的 $t$，则输出 $-1$。 $^\dagger$ 形式化地说，选择一个下标 $i$，满足 $0 \leq i \leq 10^{100}-|s|$。对于所有 $1 \leq j \leq |s|$，如果 $s_j = \texttt{1}$，则翻转 $t_{i+j}$。即如果 $t_{i+j}=\texttt{0}$，则令 $t_{i+j}=\texttt{1}$；如果 $t_{i+j}=\texttt{1}$，则令 $t_{i+j}=\texttt{0}$。 $^\ddagger$ 对于长度相同的二进制字符串 $a$ 和 $b$，如果在第一个不同的位置 $a$ 的该位为 $\texttt{1}$ 而 $b$ 的该位为 $\texttt{0}$，则称 $a$ 的字典序大于 $b$。

输入仅一行，一个二进制字符串 $s$（$1 \leq |s| \leq 35$）。

如果不存在满足条件的字符串 $t$，输出 $-1$。否则，输出两个整数 $p$ 和 $q$（$1 \leq p < q \leq 10^{100}$），表示字典序最大的 $t$ 中为 $\texttt{1}$ 的两个下标。

在第一个样例中，你可以进行如下操作： $$ \texttt{00000}\ldots \to \color{red}{\texttt{1}}\texttt{0000}\ldots \to \texttt{1}\color{red}{\texttt{1}}\texttt{000}\ldots $$ 在第二个样例中，你可以进行如下操作： $$ \texttt{00000}\ldots \to \color{red}{\texttt{001}}\texttt{00}\ldots \to \texttt{0}\color{red}{\texttt{011}}\texttt{0}\ldots $$ 在第三个样例中，你可以进行如下操作： $$ \texttt{00000}\ldots \to \color{red}{\texttt{1111}}\texttt{0}\ldots \to \texttt{1}\color{red}{\texttt{0001}}\ldots $$ 可以证明，这些 $t$ 都是字典序最大的。 在第四个样例中，你无法使任意一位变为 $\texttt{1}$，因此无解。 由 ChatGPT 4.1 翻译