No.3588 Already Ready
Problem Statement
$N$ teams numbered from $1$ to $N$ hold a tournament. The initial score of each team is $0$.
The tournament proceeds according to the following rules.
- In the tournament, matches are played in order, $1$ match at a time, until the termination condition described below is satisfied. In each match, exactly $1$ team among all $N$ teams becomes the "winner".
- For every 1 match, the winner gets $2$ points, and each of the $N-1$ teams that are not the winner gets $1$ point.
- A team whose score is at least $K$ immediately before the start of a match is called "ready". If a ready team becomes the winner, the tournament ends with that match as the last one, and that team "wins the tournament".
You are given the final score of each team† $A_1,A_2,\dots,A_N$ at the end of the tournament, and the tournament-winning team (the winner of the last match) $M$.
Determine whether there exists a progression of the tournament consistent with this information.
If one exists, output the lexicographically smallest‡ among the winner sequences representing such a progression of the tournament.
† The final score refers to the score after the points of the match that decides the tournament winner have been added.
‡ For $2$ sequences $P,Q$, let $j$ be the first position where they differ; if $P_j<Q_j$, then $P$ is said to be lexicographically smaller than $Q$.
However, if one is a prefix of the other, the shorter one is said to be lexicographically smaller.
Constraints
- $2 \leq N \leq 2\times 10^5$
- $1 \leq K \leq 2\times 10^5$
- $1 \leq M \leq N$
- $0 \leq A_i \leq 2\times 10^5$
- All input values are integers
Input
The input is given from standard input in the following format.
$N\ K$ $M$ $A_1\ A_2\ \dots\ A_N$
Output
If no progression of the tournament satisfying the conditions exists, output -1 on $1$ line.
If one exists, output in the following format.
$T$ $b_1\ b_2\ \dots\ b_T$
Here, $T$ is the number of matches and $b_t$ is the team number of the winner of the $t$-th match; $T$ is an integer greater than or equal to $1$, and each $b_t$ is an integer satisfying $1 \leq b_t \leq N$.
If there are multiple winner sequences satisfying the conditions, output the lexicographically smallest one among them.
Sample
Sample 1
Input
3 2 1 4 4 4
Output
3 2 3 1
For the winner sequence $(2,3,1)$, the scores after each match are
$(1,2,1) \rightarrow (2,3,3) \rightarrow (4,4,4)$.
Immediately before the start of the last match, the score of team $1$ is $2$, so it is ready,
and the tournament ends with team $1$ winning last.
$(3,2,1)$ also satisfies the conditions, but the lexicographically smallest is $(2,3,1)$.
Sample 2
Input
3 2 1 4 3 5
Output
-1
No progression of the tournament satisfying the conditions exists.
Sample 3
Input
4 4 1 7 6 6 6
Output
5 1 2 3 4 1
For example, $(2,3,4,1,1)$ also satisfies the conditions, but it is not the lexicographically smallest.
The lexicographically smallest winner sequence is $(1,2,3,4,1)$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
siganai