Educational Codeforces Round 137 (Rated for Div. 2)

D. Problem with Random Tests

https://codeforces.com/contest/1743/problem/D

4 seconds / 512 megabytes

standard input / standard output

### Problem

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 $\mathtt{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 $\mathtt{0}$ and/or $\mathtt{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 $\mathtt{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.

input 1

5
11010

output 1

11111

input 2

7
1110010

output 2

1111110

input 3

4
0000

output 3

0

### Note

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

In the second example, you can choose the substrings $\mathtt{1110010}$ and $\mathtt{11100}$.

### 题解

（下方字符串下标均从第 $1$ 位开始计，写程序时注意调整）

$$E(X)=\sum_{i=1}^{n}{\frac{n}{2^n}}=2$$

### 代码

#include <bits/stdc++.h>

using namespace std;

string str_or(string &a, string &b)
{
if (a.size() >= b.size())
{
string ans = a;
for (int i = 0; i < b.size(); i++)
if (b[i] == '1')
ans[a.size() - b.size() + i] = '1';
return ans;
}
return str_or(b, a);
}

string remove_zero(string &s)
{
string ans = s;
while (ans[0] == '0' && ans.size() - 1)
ans.erase(ans.begin());
return ans;
}

int main()
{
int n;
cin >> n;
string s;
cin >> s;
int one = s.find('1'), zero = s.find('0', one);
string ans = s;
if (zero != s.npos)
{
for (int i = one; i < zero; i++)
{
string sub_s = s.substr(i, n - zero);
ans = max(ans, str_or(s, sub_s));
}
}
cout << remove_zero(ans) << endl;
return 0;
}