問題一覧 > 通常問題

No.1872 Dictionary Order

レベル : / AI推定難易度 : 1625 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 71
作問者 : shiomusubi496 / テスター : ぷら
お気に入りにしたユーザー ProblemId : 7336 / 自分の提出
問題文最終更新日: 2022-03-11 16:05:43
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 335 (順位表) の他の問題:

Problem Statement

You are given integers $N, M$, a sequence $A = (A_1, A_2, \ldots, A_N)$ of length $N$, and a permutation $P = (P_1, P_2, \ldots, P_N)$ of $(1, 2, \ldots, N)$. An integer sequence $B = (B_1, B_2, \ldots, B_K)$ satisfying the following conditions is called a good sequence.

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

For a good sequence $B$, its heading sequence is defined as $(P_{B_1}, P_{B_2}, \ldots, P_{B_K})$.

Find the good sequence whose heading sequence is lexicographically smallest. If no good sequence exists, report that.

Input

$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$ is a permutation of $(1, 2, \ldots, N)$
  • All input values are integers

Output

If a good sequence exists, output the good sequence whose heading sequence is lexicographically smallest in the following format.

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

It can be proved that, under the constraints of this problem, if a good sequence exists, the one whose heading sequence is lexicographically smallest is uniquely determined ($1$ way).

If no good sequence exists, output $-1$.

Sample

Sample 1
Input
4 10
2 6 4 8
3 2 4 1
Output
2
2 3

There are $2$ good sequences: $(1, 4), (2, 3)$. Their heading sequences are $(3, 1), (2, 4)$ respectively, and the lexicographically smallest of these is $(2, 4)$, so the answer is $(2, 3)$, whose heading sequence it is.

Sample 2
Input
4 6
4 3 1 4
1 2 3 4
Output
-1

No good sequence exists, so output $-1$.

Note that the elements of $A$ are not necessarily distinct.

Sample 3
Input
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
Output
5
8 12 14 15 19

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