問題一覧 > 通常問題

No.2779 Don't make Pair

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 117
作問者 : yuusaanyuusaan / テスター : 👑 seekworserseekworser amentorimaruamentorimaru
0 ProblemId : 10973 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-06-07 22:35:48

ストーリー

あなたの力でゆ~さんは許せない文字列を見ずに済みましたが、まだゆ~さんの怒りは収まりません。次は配列をターゲットにしました。

ゆ~さんは配列内の同じ要素が別々に分かれるように、その配列を $2$ つに引き裂こうとしています。

「カップルは引き裂くべし...!」

しかし、現実では必ずしもそれが簡単にできるとは限りません。

あなたの仕事は配列をどう引き裂いたら同じ要素たちが同じ配列に存在しないようにできるのかゆ~さんの代わりに考えてあげることです。

問題文

長さ $N$ の配列 $A$ が与えられます。

ここで、 $1$ 以上 $N-1$ 以下の整数 $j$ を選択して $\{ A_1 , A_2 , \dots , A_j \}$ と $\{ A_{j+1} , A_{j+2} , \dots , A_N \}$ の二つの部分列に分割することを考えます。

このとき、以下の条件を満たす $j$ を昇順にすべて挙げて下さい。

  • 分割された部分列について、どちらの部分列にも同じ要素が $2$ つ以上含まれない。

入力

$N$
$A_1$ $A_2$ $\dots$ $A_N$

制約

  • $2\leq N \leq 2\times 10^5$
  • $1 \leq A_i \leq 10^9$ $(1\leq i \leq N)$
  • 入力はすべて整数

出力

$2$ 行出力して下さい。

$1$ 行目には条件を満たす $j$ の個数を、
$2$ 行目には条件を満たす $j$ を昇順に空白区切りで出力して下さい。

最後に改行してください。

サンプル

サンプル1
入力
7
3 5 4 3 2 1 9
出力
3
1 2 3

例として、 $j=2$ とすると、{ $3$ , $5$ },{ $4$ , $3$ , $2$ , $1$ , $9$ } の $2$ つの部分列部分列に分割され、

この $2$ つの配列はともに 同じ要素を $2$ つ以上含みまないので $j=2$ は条件を満たします。

一方、 $j=5$ とすると、{ $3$ , $5$ , $4$ , $3$ , $2$ },{ $1$ , $9$ } の $2$ つの部分列部分列に分割され、

{ $3$ , $5$ , $4$ , $3$ , $2$ }には $3$ が $2$ つ含まれているので、$j=5$ は条件を満たしません。

サンプル2
入力
4
1 1 2 2
出力
0

$j$ をどの値にしても条件を満たしません。

サンプル3
入力
5
1 2 3 4 5
出力
4
1 2 3 4

$j$ の取りうる値は $1$ から $N-1$ までである点に注意してください。(分割によって空配列が発生することはありません。)

サンプル4
入力
3
1 1 1
出力
0

サンプル5
入力
12
4 8 9 10 3 6 4 2 1 7 11 9
出力
4
3 4 5 6

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。