← 返回 meta 的题目列表Match Signals Received by Two Antennas Within a Maximum Delay
类型：online_judge
Given two one-dimensional integer arrays a and b, where an index represents reception time and an element represents a signal ID received by an antenna, and a non-negative integer k representing the maximum allowed delay:
Two records form a valid reception if a[i] == b[j] and |i - j| <= k. Each record may be used in at most one pair.
Output the signal IDs of all valid pairs. Order results by the earlier timestamp of each pair; break ties by the index in a. Print an empty line if no valid pair exists.
Input format
n m k
a0 a1 ... a(n-1)
b0 b1 ... b(m-1)
1 <= n, m <= 2 * 10^5
0 <= k <= 2 * 10^5
a[i] and b[j] are integer signal IDs.
Example 1
Input
4 4 1
1 2 3 4
2 1 4 3
Output
1 2 3 4
Example 2
Input
4 3 0
5 5 7 5
5 7 5
Output
5 7
In Example 2, only records at the same index may match. a[1] = 5 has no available matching record at the same index.
Example
Input
4 4 1
1 2 3 4
2 1 4 3
Output
1 2 3 4