No.3588 Already Ready
タグ : / 解いたユーザー数 10
作問者 :
siganai
問題文
$1$ から $N$ までの番号が付いた $N$ チームが大会を行います。各チームの初期スコアは $0$ です。
大会は、以下のルールに従って進行します。
- 大会では、後述の終了条件が満たされるまで $1$ 試合ずつ順に試合が行われ、各試合では全 $N$ チームのうちちょうど $1$ チームが「勝者」となります。
- 1 試合ごとに、勝者は $2$ 点を得て、勝者でない $N-1$ チームはそれぞれ $1$ 点を得ます。
- ある試合の開始直前にスコアが $K$ 以上であるチームを 「ready」 と呼び、ready なチームが勝者になった場合、その試合を最後に大会は終了し、そのチームが「優勝」します。
大会終了時点での各チームの最終スコア† $A_1,A_2,\dots,A_N$ と、優勝チーム(最後の試合の勝者) $M$ が与えられます。
この情報と矛盾しない大会進行が存在するか判定してください。
また、存在する場合は、そのような大会進行を表す勝者列のうち、辞書順最小‡のものを出力してください。
† 最終スコアとは、優勝が確定した試合で得点が加算されたあとのスコアを指します。
‡ $2$ つの列 $P,Q$ について、最初に異なる位置を $j$ としたとき $P_j<Q_j$ ならば、$P$ は $Q$ より辞書順で小さいとします。
ただし、一方がもう一方の接頭辞である場合は、短い方を辞書順で小さいとします。
制約
- $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$
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
$N\ K$ $M$ $A_1\ A_2\ \dots\ A_N$
出力
条件を満たす大会進行が存在しない場合は、-1 を $1$ 行で出力してください。
存在する場合は、次の形式で出力してください。
$T$ $b_1\ b_2\ \dots\ b_T$
ここで、$T$ は試合数、$b_t$ は $t$ 試合目の勝者のチーム番号で、$T$ は $1$ 以上の整数であり、各 $b_t$ は $1 \leq b_t \leq N$ を満たす整数です。
条件を満たす勝者列が複数存在する場合、その中で辞書順最小のものを出力してください。
サンプル
サンプル1
入力
3 2 1 4 4 4
出力
3 2 3 1
勝者列 $(2,3,1)$ に対する各試合後のスコアは、
$(1,2,1) \rightarrow (2,3,3) \rightarrow (4,4,4)$
となります。
最後の試合の開始直前、チーム $1$ のスコアは $2$ であり ready なので、
最後にチーム $1$ が勝って大会は終了します。
他にも $(3,2,1)$ が条件を満たしますが、辞書順最小は $(2,3,1)$ です。
サンプル2
入力
3 2 1 4 3 5
出力
-1
条件を満たす大会進行は存在しません。
サンプル3
入力
4 4 1 7 6 6 6
出力
5 1 2 3 4 1
例えば $(2,3,4,1,1)$ も条件を満たしますが、辞書順最小ではありません。
辞書順最小の勝者列は $(1,2,3,4,1)$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。