表示言語
/ /分数: 100 点
问题陈述
给你一个整数数组 A=[A_1,\dots,A_N] 长度 N 和一个整数数组 B=[B_1,\dots,B_M] 长度 M.
找到以下内容的重新排列 A 其中出现的次数 B 作为连续子序列被最大化。在这里,一个 重新排列 of A 表示数组 A' 满足以下条件。
- A' 是长度的整数数组 N,并且存在一个排列 P of 1,\dots,N 这样 A'_i=A_{P_i}(1 \le i \le N).
什么是连续子序列?
A 连续子序列 是通过从原始序列的连续位置以相同的顺序取出元素而获得的序列。例如,在序列中 [1,2,3,4], [2,3] 是一个连续的子序列,但是 [1,3] 不是。 多个连续的子序列可以在同一序列中彼此重叠。 [1,2,1,2,1], [1,2,1] 共出现 2 次。什么是排列?
A 排列 长度 N 是一个序列,其中包含来自 1 to 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
输出
输出重排的元素 A 最大化出现次数 B 作为连续的子序列,由空格分隔。如果存在多个这样的重排,则输出其中任何一个。 对于
示例输入 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)인 길이 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