← 返回题目列表

AtCoder · scpc2026_div2_c

C. 重新排列

中文机器翻译题面 查看原题

表示言語

/ /

分数: 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