問題一覧 > 通常問題

No.3588 Already Ready

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 10
作問者 : marc2825 / テスター : siganai
ProblemId : 13243 / yukicoder contest 504 (順位表) / 自分の提出
問題文最終更新日: 2026-07-10 23:22:07
yukicoder contest 504の他の問題:

問題文

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