/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
表示言語
/ /Score : 100 points
Problem Statement
You are given an integer array A=[A_1,\dots,A_N] of length N and an integer array B=[B_1,\dots,B_M] of length M.
Find a rearrangement of A in which the number of occurrences of B as a contiguous subsequence is maximized. Here, a rearrangement of A means an array A' satisfying the following condition.
- A' is an integer array of length N, and there exists a permutation P of 1,\dots,N such that A'_i=A_{P_i}(1 \le i \le N).
What is a contiguous subsequence?
A contiguous subsequence of a sequence is a sequence obtained by taking elements from consecutive positions of the original sequence, in the same order. For example, in the sequence [1,2,3,4], [2,3] is a contiguous subsequence, but [1,3] is not. Multiple contiguous subsequences may overlap with each other in the same sequence. For example, in the sequence [1,2,1,2,1], [1,2,1] appears a total of 2 times.What is a permutation?
A permutation of length N is a sequence that contains each integer from 1 to N exactly once. For example, [2,1,4,3] is a permutation, but [4,2,1,1] and [1,2,3,5] are not.Constraints
- 1 \le M \le N \le 1\,000\,000
- 0 \le A_i, B_i \le 1\,000\,000
- All given numbers are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_N B_1 B_2 \dots B_M
Output
Output the elements of a rearrangement of A that maximizes the number of occurrences of B as a contiguous subsequence, separated by spaces. If there are multiple such rearrangements, output any one of them.
Sample Input 1
4 2 1 2 3 4 2 1
Sample Output 1
2 1 3 4
Sample Input 2
4 2 1 2 1 2 2 1
Sample Output 2
2 1 2 1
表示言語
/ /점수 : 100 점
문제
길이가 N인 정수 배열 A=[A_1,\dots,A_N], 길이가 M인 정수 배열 B=[B_1,\dots,B_M]가 주어진다.
A의 재배열 중 B가 연속 부분 수열로 등장하는 횟수가 최대가 되는 배열을 구하시오. 이때 A의 재배열이란 다음을 만족하는 배열 A'을 의미한다.
- A'은 길이가 N인 정수 배열이고, A'_i=A_{P_i}(1 \le i \le N)인 길이 N인 순열 P가 존재한다.
연속 부분 수열이란
어떤 수열의 연속 부분 수열은 원래 수열에서 연속한 위치의 원소들을 순서대로 가져온 수열이다. 예를 들어 수열 [1, 2, 3, 4]에서 [2, 3]은 연속 부분 수열이지만, [1, 3]은 연속 부분 수열이 아니다. 같은 수열 안에서 여러 연속 부분 수열이 서로 겹쳐서 등장할 수도 있다. 예를 들어 수열 [1, 2, 1, 2, 1]에서 [1, 2, 1]은 총 2회 등장한다.순열이란
길이가 N인 순열은 1부터 N까지의 정수가 정확히 한 번씩 등장하는 수열이다. 예를 들어 [2,1,4,3]은 순열이지만 [4,2,1,1]이나 [1,2,3,5]는 순열이 아니다.제한
- 1 \le M \le N \le 10^6
- 0 \le A_i, B_i \le 10^6
- 입력으로 주어지는 수는 모두 정수이다.
입력
입력은 다음 형식으로 표준 입력으로 주어진다.
N M A_1 A_2 \dots A_N B_1 B_2 \dots B_M
출력
B가 연속 부분 수열로 등장하는 횟수가 최대화되는 A의 재배열의 원소를 순서대로 공백으로 구분하여 출력한다.
조건을 만족하는 재배열이 여러 가지라면 그중 아무거나 출력한다.
입력 예 1
4 2 1 2 3 4 2 1
출력 예 1
2 1 3 4
입력 예 2
4 2 1 2 1 2 2 1
출력 예 2
2 1 2 1
表示言語
/ /配点 : 100 点
問題文
長さ N の整数配列 A=[A_1,\dots,A_N] と，長さ M の整数配列 B=[B_1,\dots,B_M] が与えられる．
A の並べ替えのうち，B が連続部分列として現れる回数が最大になる配列を求めよ．ここで，A の並べ替えとは，次の条件を満たす配列 A' を意味する．
- A' は長さ N の整数配列であり，A'_i=A_{P_i}(1 \le i \le N) となる 1,\dots,N の順列 P が存在する．
連続部分列とは
ある数列の 連続部分列 とは，元の数列から連続した位置の要素を順番に取り出してできる数列である．例えば，数列 [1,2,3,4] において [2,3] は連続部分列であるが，[1,3] は連続部分列ではない． 同じ数列の中で，複数の連続部分列が互いに重なって現れることもある．例えば，数列 [1,2,1,2,1] において [1,2,1] は合計 2 回現れる．順列とは
長さ N の 順列 とは，1 から N までの整数をちょうど一度ずつ含む数列である．例えば [2,1,4,3] は順列であるが，[4,2,1,1] や [1,2,3,5] は順列ではない．制約
- 1 \le M \le N \le 1\,000\,000
- 0 \le A_i, B_i \le 1\,000\,000
- 入力される数値はすべて整数
入力
入力は以下の形式で標準入力から与えられる．
N M A_1 A_2 \dots A_N B_1 B_2 \dots B_M
出力
B が連続部分列として現れる回数が最大になる A の並べ替えの要素を，順に空白区切りで出力せよ．
条件を満たす並べ替えが複数存在する場合，そのうちどれを出力してもよい．
入力例 1
4 2 1 2 3 4 2 1
出力例 1
2 1 3 4
入力例 2
4 2 1 2 1 2 2 1
出力例 2
2 1 2 1