No.3780 Erase and Mex
タグ : / 解いたユーザー数 30
作問者 :
Problem Statement
There are $N$ non-negative integers written on a blackboard. Let the $i$-th integer be $A_i$. You may perform the following operation any number of times, possibly $0$ times.
- Choose any number of integers, at least $1$, written on the blackboard. Let $S$ be the multiset consisting of the chosen integers. Write one $\operatorname{mex}(S)$ on the blackboard, and then erase all of the chosen integers from the blackboard.
Here, $\operatorname{mex}(S)$ denotes the smallest non-negative integer not contained in $S$.
Also, you may make an end declaration exactly once, at any time of your choice. When you make the end declaration, if exactly $1$ integer is written on the blackboard at that point, you obtain $x$ points, where $x$ is that integer; otherwise, you obtain $-10^{100}$ points. Find the maximum score you can obtain.
Answer for $T$ test cases.
Constraints
- $1\le T\le 2\times 10^5$
- $1\le N\le 2 \times 10^5$
- $0\le A_i\le 10^9 (1\le i\le N)$
- The sum of $N$ over the $T$ test cases is at most $2\times 10^5$
- All input values are integers
Input
The input is given in the following format, where $case_i$ denotes the $i$-th test case.
$T$ $case_1$ $case_2$ $\vdots$ $case_T$
Each test case is given in the following format.
$N$ $A_1\ A_2\ \cdots\ A_N$
Output
Print $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.
Sample
Sample 1
Input
2 6 3 1 1 1 1 1 20 21 10 19 3 11 24 12 6 24 17 4 3 20 11 9 3 23 0 22 9
Output
4 7
For the $1$st test case, you can obtain $4$ points by performing the operations as follows.
- Let $S=\{1,1\}$. Since $\operatorname{mex}(S)=0$, the integers written on the blackboard become $\{0,1,1,1,3\}$.
- Let $S=\{1\}$. Since $\operatorname{mex}(S)=0$, the integers written on the blackboard become $\{0,0,1,1,3\}$.
- Let $S=\{0,1\}$. Since $\operatorname{mex}(S)=2$, the integers written on the blackboard become $\{0,1,2,3\}$.
- Let $S=\{0,1,2,3\}$. Since $\operatorname{mex}(S)=4$, the integers written on the blackboard become $\{4\}$.
- Make the end declaration.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。