Background

Translated from Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection) D1T2. $\texttt{2s,0.5G}$.

SPJ link.

Problem Description

Given non-negative integers $N,K,L$, construct two $01$ sequences $S,T$ such that:

• The lengths of $S$ and $T$ are $N$.
• $S$ contains exactly $K$ ones, and $T$ contains exactly $L$ ones.
• $f(S,T)$ is the minimum among all possible $f(S,T)$.

Define $f(S,T)$ as follows: after applying any cyclic shifts to $S$ and $T$, take the maximum value of $\sum_{i=1}^{N} S_i\operatorname{and} T_i$, where $\mathrm{and}$ denotes the bitwise AND operation.

You need to construct $S$ and $T$.

Input Format

One line with three integers $N,K,L$.

Output Format

The first line contains an integer $F$, which is the minimum value of $f(S,T)$.

The next two lines describe the sequences $S$ and $T$, respectively. There is no need to output spaces between adjacent elements.

If there are multiple solutions, output any one of them.

6 4 3

2
011011
101010

5 2 0

0
01001
00000

10 7 6

5
1101100111
1110001101

Hint

For $100\%$ of the testdata, it is guaranteed that $1\le N\le 5\times 10^5$ and $0\le K,L\le N$.

Scoring:

• If you answer $F$ correctly, you can get $20\%$ of the score.
• On this basis, if your $S,T$ satisfy the conditions, you will get the remaining $80\%$ of the score.
• If you only plan to answer the first part, you still need to output any two $01$ sequences satisfying conditions 1 and 2, otherwise you are not guaranteed to get any score.

Translated by ChatGPT 5