問題一覧 > 通常問題

No.2803 Bocching Star

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 152
作問者 : hirayuu_ychirayuu_yc / テスター : highlighterhighlighter MagentorMagentor keisuke6keisuke6 silv723silv723 Yoyoyo8128Yoyoyo8128 zeta7532zeta7532 fact493fact493
1 ProblemId : 11052 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-07-12 20:52:07

ストーリー

必ずしもこの項を読む必要はない。

halc「パ研合宿、楽しかったなー」

QgQ「でもお前、全然チーム組めてないじゃん」

halc「黙れ脱法チーム」

問題文

夜空に $N$ 個の星があります。星には $1,2,\dots,N$ と番号がついています。

夜空は数直線とみなすことができ、星 $i$ は座標 $P_i$ にあります。同じ座標に複数の星がある場合もあります。

各星は、距離 $S$ 以内に別の星がないとき、またその時に限り孤立した星といいます。

より厳密には、星 $i$ が孤立した星であることは、$i\ne j$ なる任意の $j$ について $S<|P_i-P_j|$ であることと同値です。

孤立した星を番号の昇順に列挙してください。

入力

$N\ S$
$P_1\ P_2\dots P_N$
  • $1\leq N\leq 2\times 10^5$
  • $0\leq S\leq 10^9$
  • $0\leq P_i\leq 10^9$
  • 孤立した星は $1$ つ以上存在する
  • 入力はすべて整数

出力

$2$ 行出力してください。

$1$ 行目には、孤立した星の個数を出力してください。

$2$ 行目には、孤立した星の番号を昇順に並べたものを半角スペースで区切って出力してください。

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

サンプル

サンプル1
入力
4 2
3 1 6 10
出力
2
3 4

星 $1$ と星 $2$ は距離 $2$ です。そのため、星 $1$ と星 $2$ は孤立した星ではありません。

星 $1,2,3$ と星 $4$ の距離はそれぞれ $7,9,4$ なので、星 $4$ は孤立した星です。同様に、星 $3$ も孤立した星であることが確認できます。

たとえば、$2$ 行目に 4 3 と出力することは許されません。番号が昇順に並んでいないためです。

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

夜空には星 $1$ 以外に星はないようです。

サンプル3
入力
9 0
9 9 8 2 4 4 3 5 3
出力
3
3 4 8

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