Problem with Random Tests

4000ms

524288K

Description:

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 $$$s_1$$$ be the first substring, $$$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, $$$f(s_i) = 26$$$);
the value is the bitwise OR of $$$f(s_1)$$$ and $$$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 $$$\frac{1}{2}$$$.

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

Hacks are forbidden in this problem.

Output:

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

Sample Input:

5
11010

Sample Output:

Sample Input:

7
1110010

Sample Output:

Sample Input:

4
0000

Sample Output:

Note:

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

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

Informação

Provedor Codeforces

Código CF1743D