問題一覧 > 通常問題

No.3588 Already Ready

レベル : / AI推定難易度 : 2250 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 12
作問者 : marc2825 / テスター : siganai
お気に入りにしたユーザー ProblemId : 13243 / 自分の提出
問題文最終更新日: 2026-10-21 16:17:25
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 504 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。