[Solution] Long Binary String Codeforces Solution

[Solution] Long Binary String Codeforces Solution | Codeforces Problem Solution 2022

G. Long Binary String

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

There is a binary string t$t$ of length 10100${10}^{100}$, and initally all of its bits are 0$\mathtt{\text{0}}$. You are given a binary string s$s$, and perform the following operation some times:

• Select some substring of t$t$, and replace it with its XOR with s$s$.†${}^{†}$

After several operations, the string t$t$ has exactly two bits 1$\mathtt{\text{1}}$; that is, there are exactly two distinct indices p$p$ and q$q$ such that the p$p$-th and q$q$-th bits of t$t$ are 1$\mathtt{\text{1}}$, and the rest of the bits are 0$\mathtt{\text{0}}$.

Find the lexicographically largest‡${}^{‡}$ string t$t$ satisfying these constraints, or report that no such string exists.

†${}^{†}$ Formally, choose an index i$i$ such that 0≤i≤10100−|s|$0\le i\le {10}^{100}-|s|$. For all 1≤j≤|s|$1\le j\le |s|$, if sj=1$s_j=\mathtt{\text{1}}$, then toggle ti+j$t_{i+j}$. That is, if ti+j=0$t_{i+j}=\mathtt{\text{0}}$, set ti+j=1$t_{i+j}=\mathtt{\text{1}}$. Otherwise if ti+j=1$t_{i+j}=\mathtt{\text{1}}$, set ti+j=0$t_{i+j}=\mathtt{\text{0}}$.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

‡${}^{‡}$ A binary string a$a$ is lexicographically larger than a binary string b$b$ of the same length if in the first position where a$a$ and b$b$ differ, the string a$a$ has a bit 1$\mathtt{\text{1}}$ and the corresponding bit in b$b$ is 0$\mathtt{\text{0}}$.

Input

The only line of each test contains a single binary string s$s$ (1≤|s|≤35$1\le |s|\le 35$).

XOR Mixup Codeforces Solution

Long Binary String Codeforces Solution

Rising Sand Codeforces Solution

3SUM Closure Codeforces Solution

Fixed Point Guessing Codeforces Solution

PermutationForces II Codeforces Solution

Equal Reversal Codeforces Solution

Output

If no string t$t$ exists as described in the statement, output -1. Otherwise, output the integers p$p$ and q$q$ (1≤p<q≤10100$1\le p<q\le {10}^{100}$) such that the p$p$-th and q$q$-th bits of the lexicographically maximal t$t$ are 1$\mathtt{\text{1}}$.