問題一覧 > 通常問題

No.2803 Bocching Star

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 164
作問者 : hirayuu_yc / テスター : highlighter Magentor keisuke6 silv723 Yoyoyo8128 zeta7532 fact493
1 ProblemId : 11052 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-07-12 20:52:07

ストーリー

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

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

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

halc「黙れ脱法チーム

問題文

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

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

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

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

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

入力

N SN\ S
P1 P2PNP_1\ P_2\dots P_N
  • 1N2×1051\leq N\leq 2\times 10^5
  • 0S1090\leq S\leq 10^9
  • 0Pi1090\leq P_i\leq 10^9
  • 孤立した星は 11 つ以上存在する
  • 入力はすべて整数

出力

22 行出力してください。

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

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

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

サンプル

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

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

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

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

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

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

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

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