No.2774 Wake up Record 2
タグ : / 解いたユーザー数 137
作問者 :
amentorimaru
Story
Thanks to buying a sleep-recording robot, Yu-san's sleep quality improved and so did his work efficiency.
Since his improved work efficiency also raised his salary, he traded in the sleep-recording robot and bought an "energy-level-recording robot".
A "sleep-duration-recording robot" came along with it as well, so Yu-san is in an absolutely wonderful mood.
"This will improve my sleep quality even more! For now, I'll work out the times I wake up at night just like before... huh?"
Your job, same as before, is to find all the times at which Yu-san ends up waking up.
Problem Statement
To improve his health, Yu-san bought robot $1$, which records his "energy level", and robot $2$, which records his total sleep duration. He had each of them make its records from time $1$ to time $N$ and output those records.
You are given a sequence $A$ of $N$ positive integers and a positive integer $K$.
These indicate that robot $1$ recorded that Yu-san's energy level at time $i$ was $A_i$, and that robot $2$ recorded that Yu-san's total sleep duration was $K$.
It is known that Yu-san was asleep at the times when his energy level was at most a certain fixed value, and awake at all other times.
Output, in ascending order, all integers $k$ between $2$ and $N$, inclusive, such that he is awake at time $k$ and asleep at time $k-1$.
Input
$N\ \ K$ $A_1\ \ A_2\ \ A_3 \ \dots\ A_N$
Constraints
- $2 \leq K\leq N\leq 10^5$
- $1 \leq A_i \leq 10^9$
- All input values are integers.
- When he is regarded as asleep at energy levels of $j$ or less, $A_1 \leq j$.
- No contradictory input is given.
Output
Output $2$ lines.
On the $1$st line, output the number of values $k$ to be output,
and on the $2$nd line, output all the values $k$ to be output in ascending order.
Sample
Sample 1
Input
8 3 1 3 5 6 4 8 9 10
Output
2 3 6
In this case, only when he is asleep at energy levels of $4$ or less and awake otherwise is the sleep duration $3$, which does not contradict the given information.
Using this information and representing awake times by o and asleep times by x, we get xxooxooo, and the values $k$ satisfying the condition are $3$ , $6$.
Sample 2
Input
10 10 1 2 3 2 3 2 3 2 1 1
Output
0
Yu-san manages to sleep without waking up.
Sample 3
Input
10 5 199178881 932079191 906976560 427573994 961937646 979063146 995030172 852645442 662699738 313858222
Output
2 2 5
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。