問題一覧 > 通常問題

No.1872 Dictionary Order

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 59
作問者 : shiomusubi496shiomusubi496 / テスター : ぷらぷら
4 ProblemId : 7336 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-03-11 16:05:43

問題文

整数 $N, M$ と長さ $N$ の数列 $A = (A_1, A_2, \ldots, A_N)$ 、及び $(1, 2, \ldots, N)$ の順列 $P = (P_1, P_2, \ldots, P_N)$ が与えられます。ここで、以下の条件を満たす整数列 $B = (B_1, B_2, \ldots, B_K)$ を良い数列と呼ぶことにします。

  • $1 \leq B_1 < B_2 < \cdots < B_K \leq N$
  • $\displaystyle \sum_{i=1}^K A_{B_i} = M$

また、良い数列 $B$ に対して見出し数列を $(P_{B_1}, P_{B_2}, \ldots, P_{B_K})$ と定義します。

このとき、見出し数列が辞書順で最小となる良い数列を求めて下さい。ただし、良い数列が存在しない場合はそれを報告してください。

入力

$N$ $M$
$A_1$ $A_2$ $\cdots$ $A_N$
$P_1$ $P_2$ $\cdots$ $P_N$
  • $1 \leq N, M \leq 2000$
  • $1 \leq A_i \leq M$ $(1 \leq i \leq N)$
  • $P$ は $(1, 2, \ldots, N)$ の順列
  • 入力は全て整数

出力

良い数列が存在する場合、見出し数列が辞書順最小となる良い数列を以下の形式で出力してください。

$K$
$B_1$ $B_2$ $\cdots$ $B_K$

なお、この問題の制約下で、良い数列が存在するとき、そのうち見出し数列が辞書順最小であるものは必ず $1$ 通りに定まることが証明できます。

良い数列が存在しない場合、 $-1$ と出力してください。

サンプル

サンプル1
入力
4 10
2 6 4 8
3 2 4 1
出力
2
2 3

良い数列は $(1, 4), (2, 3)$ の $2$ つです。それぞれの見出し数列は $(3, 1), (2, 4)$ となるため、このうち辞書順で最小な $(2, 4)$ が見出し数列である $(2, 3)$ が答えとなります。

サンプル2
入力
4 6
4 3 1 4
1 2 3 4
出力
-1

良い数列は存在しないため、 $-1$ を出力します。

$A$ の各要素は相異なるとは限らないことに注意してください。

サンプル3
入力
20 100
25 18 33 15 15 41 82 14 9 83 11 4 95 72 1 89 58 13 9 66
6 8 11 3 4 16 12 1 17 10 18 9 2 19 5 13 7 20 15 14
出力
5
8 12 14 15 19

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。