No.2779 Don't make Pair
タグ : / 解いたユーザー数 125
作問者 :
amentorimaru
Story
Thanks to your efforts, Yu-san was spared from seeing the unforgivable string, but Yu-san's anger has not subsided yet. The next target is an array.
Yu-san is trying to tear the array into $2$ parts so that identical elements in the array end up separated.
"Couples must be torn apart...!"
However, in reality, this is not always easy to do.
Your job is to figure out, on Yu-san's behalf, how to tear the array so that identical elements do not exist in the same array.
Problem Statement
You are given an array $A$ of length $N$.
Consider choosing an integer $j$ between $1$ and $N-1$, inclusive, and dividing the array into two subsequences $\{ A_1 , A_2 , \dots , A_j \}$ and $\{ A_{j+1} , A_{j+2} , \dots , A_N \}$.
List all $j$ satisfying the following condition in ascending order.
- Neither of the divided subsequences contains $2$ or more of the same element.
Input
$N$ $A_1$ $A_2$ $\dots$ $A_N$
Constraints
- $2\leq N \leq 2\times 10^5$
- $1 \leq A_i \leq 10^9$ $(1\leq i \leq N)$
- All inputs are integers.
Output
Output $2$ lines.
On the $1$st line, output the number of $j$ satisfying the condition.
On the $2$nd line, output the values of $j$ satisfying the condition in ascending order, separated by spaces.
Sample
Sample 1
Input
7 3 5 4 3 2 1 9
Output
3 1 2 3
For example, if $j=2$, the array is divided into the $2$ subsequences { $3$ , $5$ } and { $4$ , $3$ , $2$ , $1$ , $9$ }.
Neither of these $2$ arrays contains $2$ or more of the same element, so $j=2$ satisfies the condition.
On the other hand, if $j=5$, the array is divided into the $2$ subsequences { $3$ , $5$ , $4$ , $3$ , $2$ } and { $1$ , $9$ }.
{ $3$ , $5$ , $4$ , $3$ , $2$ } contains $2$ copies of $3$, so $j=5$ does not satisfy the condition.
Sample 2
Input
4 1 1 2 2
Output
0
No value of $j$ satisfies the condition.
Sample 3
Input
5 1 2 3 4 5
Output
4 1 2 3 4
Note that the possible values of $j$ range from $1$ to $N-1$. (The division never produces an empty array.)
Sample 4
Input
3 1 1 1
Output
0
Sample 5
Input
12 4 8 9 10 3 6 4 2 1 7 11 9
Output
4 3 4 5 6
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。