[Solution] Problem with Random Tests Codeforces Solution

D. Problem with Random Tests

time limit per test

4 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

You are given a string 𝑠$s$ consisting of 𝑛$n$ characters. Each character of 𝑠$s$ is either 0 or 1.

A substring of 𝑠$s$ is a contiguous subsequence of its characters.

You have to choose two substrings of 𝑠$s$ (possibly intersecting, possibly the same, possibly non-intersecting — just any two substrings). After choosing them, you calculate the value of the chosen pair of substrings as follows:

• let 𝑠1$s_1$ be the first substring, 𝑠2$s_2$ be the second chosen substring, and 𝑓(𝑠𝑖)$f(s_i)$ be the integer such that 𝑠𝑖$s_i$ is its binary representation (for example, if 𝑠𝑖$s_i$ is 11010, 𝑓(𝑠𝑖)=26$f(s_i)=26$);
• the value is the bitwise OR of 𝑓(𝑠1)$f(s_1)$ and 𝑓(𝑠2)$f(s_2)$.

Calculate the maximum possible value you can get, and print it in binary representation without leading zeroes.

Input

The first line contains one integer 𝑛$n$ — the number of characters in 𝑠$s$.

The second line contains 𝑠$s$ itself, consisting of exactly 𝑛$n$ characters 0 and/or 1.

All non-example tests in this problem are generated randomly: every character of 𝑠$s$ is chosen independently of other characters; for each character, the probability of it being 1 is exactly 12$\frac{1}{2}$.

This problem has exactly 40$40$ tests. Tests from 1$1$ to 3$3$ are the examples; tests from 4$4$ to 40$40$ are generated randomly. In tests from 4$4$ to 10$10$, 𝑛=5$n=5$; in tests from 11$11$ to 20$20$, 𝑛=1000$n=1000$; in tests from 21$21$ to 40$40$, 𝑛=106$n={10}^6$.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

Hacks are forbidden in this problem.

Output

Print the maximum possible value you can get in binary representation without leading zeroes.

Note

In the first example, you can choose the substrings 11010 and 101. 𝑓(𝑠1)=26$f(s_1)=26$, 𝑓(𝑠2)=5$f(s_2)=5$, their bitwise OR is 31$31$, and the binary representation of 31$31$ is 11111.

In the second example, you can choose the substrings 1110010 and 11100.