No.2774 Wake up Record 2
タグ : / 解いたユーザー数 126
作問者 : yuusaan / テスター : 👑 seekworser 👑 amentorimaru
ストーリー
ゆ~さんは睡眠記録ロボットを購入したおかげで睡眠の質が向上し、仕事の効率が上がりました。
仕事の効率が上がったことで給与も上がったので睡眠記録ロボットを下取りに出して「元気度記録ロボット」を購入しました。
ついでに「睡眠時間記録ロボット」もついてきたのでゆ~さんの気分はそれはもうウッキウキです。
「これで睡眠の質がさらに上がるぞ~!とりあえず夜起きちゃう時間を今まで通り割り出すとして...あれ?」
あなたの仕事は先ほどと同様ゆ~さんの目が覚めてしまう時刻を全て見つけることです。
問題文
ゆ~さんは自分の健康増進のために「元気度」を記録してくれるロボット $1$ と合計睡眠時間を記録してくれるロボット $2$ を購入し、それぞれができる記録を時間 $1$ から時間 $N$ までさせ、その記録を出力させました。
長さ $N$ の正整数列 $A$ と 正整数 $K$ が与えられます。
これらはロボット $1$ が時間 $i$ の時のゆ~さんの元気度が $A_i$ であったことを記録し、 ロボット $2$ がゆ~さんの合計睡眠時間が $K$ であったと記録していたことを表しています。
ゆ~さんは元気度がある一定の値以下である時間では寝ていて、そうでない時間では起きていたことがわかっています。
$2$ 以上 $N$ 以下の整数 $k$ のうち時間 $k$ では起きていて時間 $k-1$ では寝ているものをすべて昇順に出力してください。
入力
$N\ \ K$ $A_1\ \ A_2\ \ A_3 \ \dots\ A_N$
制約
- $2 \leq K\leq N\leq 10^5$
- $1 \leq A_i \leq 10^9$
- 入力はすべて整数
- $j$ 以下の元気度では寝ているものとしたとき、 $A_1 \leq j$
- 矛盾した入力は与えられない
出力
$2$ 行出力してください。
$1$ 行目では出力すべき $k$ の個数を、
$2$ 行目では出力すべき $k$ をすべて昇順に出力してください。
サンプル
サンプル1
入力
8 3 1 3 5 6 4 8 9 10
出力
2 3 6
このケースでは、元気度 $4$ 以下の場合は寝ていて、そうでないときは起きているとしたときに限り、睡眠時間が $3$ となり、与えられた情報と矛盾しません。
この情報を利用して、起きているときをo
、寝ているときをx
で表すと、xxooxooo
となり、条件を満たす $k$ は $3$ , $6$ です。
サンプル2
入力
10 10 1 2 3 2 3 2 3 2 1 1
出力
0
ゆ~さんは目が覚めることなく寝ることができています。
サンプル3
入力
10 5 199178881 932079191 906976560 427573994 961937646 979063146 995030172 852645442 662699738 313858222
出力
2 2 5
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。