No.3434 [Cherry 8th Tune N] Make It Bigger, Hold on Card!
Problem Visual
▶ Open to reveal the problem visual
Notice
If the judge result is QLE, there may be an error in the problem or in the judge. Please report it.Problem Statement
Cherry-chan has $N$ red cards in her hand. The $i$-th red card has the integer $A_i$ written on it.
Separately from her hand, $N$ blue cards are stacked in a deck, and the $j$-th blue card from the top has the integer $B_j$ written on it.
Cherry-chan performs the following actions in order.
- From the $N$ red cards she holds, she chooses any number of cards, $0$ or more. Then, she eats all of the chosen cards.
- She draws blue cards in order from the top, the same number as the red cards she ate, and adds them to her hand.
After these actions, Cherry-chan holds a total of $N$ cards, red and blue. The sum of the integers written on these $N$ cards is called the score.
Give $1$ way of eating red cards that maximizes the score.
Solve $T$ test cases.
Constraints
- $1 \leq T \leq 2 \times 10^5$.
- Constraints for each test case
- $1 \leq N \leq 2 \times 10^5$.
- $-10^9 \leq A_i \leq 10^9 \quad (1 \leq i \leq N)$.
- $-10^9 \leq B_j \leq 10^9 \quad (1 \leq j \leq N)$.
- Constraints for the entire test file
- The sum of $N$ over the $T$ test cases is at most $2 \times 10^5$.
- All input values are integers.
Input
$T$
Each test case is given in the following format.
$N$ $A_1$ $\dots$ $A_N$ $B_1$ $\dots$ $B_N$
Output
The output consists of $T$ lines. On line $t~(1 \leq t \leq T)$, output a string $S$ of length $N$ consisting of 0 and 1, defined as follows.
- If the $i$-th red card is not eaten, the $i$-th character of $S$ is
0; if the $i$-th red card is eaten, the $i$-th character of $S$ is1.
If there are multiple ways of eating that maximize the score, you may give any $1$ of them.
Sample
Sample 1
Input
3 3 10 30 20 15 25 5 4 1 2 3 4 100 200 300 400 6 0 0 0 0 0 0 100 -1000 0 0 0 0
Output
101 1111 001000
[Test case $1$] Cherry-chan initially has $3$ red cards, with the integers $10, 30, 20$ written on them. Also, $3$ blue cards are stacked as a deck, and the integers written on the blue cards are $15, 25, 5$ in order from the top.
Suppose Cherry-chan eats the $1, 3$-th red cards and draws $2$ blue cards, the same number as the red cards she ate. After this action, the integers written on the $3$ cards she holds are $15, 30, 25$ in some order.
This action gives a score of $15 + 30 + 25 = 70$. Also, the score cannot be made greater than $70$, so $S=$
101is a correct answer.Note that Cherry-chan can freely choose which red cards to eat, but blue cards can only be drawn from the top of the deck.
- [Test case $2$] To maximize the score, she must eat all $4$ cards she holds and draw $4$ cards from the deck.
- [Test case $3$] Any way of eating exactly $1$ of the $6$ cards maximizes the score. Therefore, not only
001000but also000010and100000are correct answers for $S$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Kazun
kazuppa