No.3427 Erasing a Subsequence
Problem Statement
You are given a sequence $S = (S_1, S_2, ..., S_N)$ of length $N$ and a sequence $T = (T_1, T_2, ...,T_M)$ of length $M$.
Here, it is guaranteed that there is at least $1$ way to extract $T$ from $S$ as a (not necessarily contiguous) subsequence.
Among the sequences obtained by removing $T$ from $S$, output the one that is lexicographically smallest.
Note that $T_i \;(1 \leq i \leq M)$ are values generated uniformly at random from the range of at least $0$ and less than $1000$.
What is lexicographic order?
Given $2$ sequences $A = (A_1, A_2, ...,A_n)$ and $B = (B_1, B_2,...,B_n)$ of length $n$,
lexicographic order is the order in which $A < B$ is defined to mean that there exists an $i\;(1 \leq i \leq n)$ satisfying the following conditions.
- $A_i<B_i$
- $A_j = B_j$ for all $j$ at least $1$ and less than $i$
Input
- $1 \leq M \leq N \leq 1000$
- $0 \leq S_i < 1000$
- $T_i \;(1 \leq i \leq M)$ are generated uniformly at random from the range of at least $0$ and less than $1000$.
- All input values are integers.
How the input is generated
The test cases were generated as follows.
- Choose $N, M$ from the range satisfying the constraints.
- Generate $T_i \;(1 \leq i \leq M)$ uniformly at random from the range of at least $0$ and less than $1000$.
- Generate $S$ so that it contains the generated $T$. $S_i \;(1 \leq i \leq N)$ are not generated uniformly at random.
The input is given from Standard Input in the following format.
$N \; M$ $S_1\;S_2\;...\;S_N$ $T_1\;T_2\;...\;T_M$
Output
Output the resulting sequence on $1$ line, separated by spaces.
Sample
The samples were created arbitrarily and are not included in the test cases.
Sample 1
Input
4 2 2 1 3 1 2 1
Output
1 3
Sample 2
Input
6 2 1 4 2 4 3 4 4 4
Output
1 2 3 4
Sample 3
Input
3 3 1 2 3 1 2 3
Output
If the answer is an empty string, output an empty line.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
まみめ
kidodesu