P10872 [COTS 2022] Shifts Maliand

Translated from [Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2022/) D1T2. $\texttt{2s,0.5G}$. [SPJ link](https://www.luogu.com.cn/paste/9qlivbk0).

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$.

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

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.

For $100\%$ of the testdata, it is guaranteed that $1\le N\le 5\times 10^5$ and $0\le K,L\le N$. | Subtask ID | Score | Constraints | |:-----:|:------:|:-------:| | $1$ | $5$ | $1\le N\le 13$ | | $2$ | $50$ | $1\le N\le 5\, 000$ | | $3$ | $45$ | No additional constraints | 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