No.1872 Dictionary Order
タグ : / 解いたユーザー数 71
作問者 :
shiomusubi496
/ テスター :
ぷら
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もしくは右上の雲マークをクリックしてアカウントを作成してください。