/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
長さ 2N の数列 a が与えられます。
すぬけ君が (1,2, \ldots, N) の空でない（連続するとは限らない）部分列 x=(x_1,x_2,\ldots,x_k) を用いて、数列を作ろうとしています。 作られる数列は、a の x_1 番目、x_2 番目、\ldots、x_k 番目、x_{1}+N 番目、\ldots、x_{k}+N 番目の要素を抜き出してこの順で連結した数列です。
すぬけ君が作ることができる数列のうち、辞書順最小のものを求めてください。
数列の辞書順とは？
相異なる数列 S と数列 T の大小を判定するアルゴリズムを以下に説明します。
以下では S の i 番目の要素を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。
- S と T のうち長さが短い方の数列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
- S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、 S_j が T_j より（数として）小さい場合は S \lt T 、大きい場合は S \gt T と決定して、アルゴリズムを終了します。
- S_i \neq T_i である i が存在しない場合、 S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。
制約
- 与えられる入力は全て整数
- 1 \leq N \leq 10^5
- 1 \leq a_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N
a_{1} \cdots a_{2N}
出力
すぬけ君が作ることができる数列のうち、辞書順最小のものを出力せよ。
入力例 1
3 2 1 3 1 2 2
出力例 1
1 2
- x = (2) とします。
- このとき、作られる数列は (1,2) となり辞書順最小です。
入力例 2
10 38 38 80 62 62 67 38 78 74 52 53 77 59 83 74 63 80 61 68 55
出力例 2
38 38 38 52 53 77 80 55
入力例 3
12 52 73 49 63 55 74 35 68 22 22 74 50 71 60 52 62 65 54 70 59 65 54 60 52
出力例 3
22 22 50 65 54 52
Score : 600 points
Problem Statement
Given is an integer sequence a of length 2N.
Snuke is going to make a sequence using a non-empty (not necessarily contiguous) subsequence x=(x_1,x_2,\ldots,x_k) of (1,2, \ldots, N). The sequence will be made by extracting and concatenating the x_1-th, x_2-th, \ldots, x_k-th, (x_{1}+N)-th, \ldots, (x_{k}+N)-th elements of a in this order.
Find the lexicographically smallest sequence that Snuke can make.
Lexicographical order on sequences
Here is the algorithm to determine the lexicographical order between different sequences S and T.
Below, let S_i denote the i-th element of S. Also, if S is lexicographically smaller than T, we will denote that fact as S \lt T; if S is lexicographically larger than T, we will denote that fact as S \gt T.
- Let L be the smaller of the lengths of S and T. For each i=1,2,\dots,L, we check whether S_i and T_i are the same.
- If there is an i such that S_i \neq T_i, let j be the smallest such i. Then, we compare S_j and T_j. If S_j is smaller than T_j in numerical order, we determine that S \lt T and quit; if S_j is greater than T_j, we determine that S \gt T and quit.
- If there is no i such that S_i \neq T_i, we compare the lengths of S and T. If S is shorter than T, we determine that S \lt T and quit; if S is longer than T, we determine that S \gt T and quit.
Constraints
- All values in input are integers.
- 1 \leq N \leq 10^5
- 1 \leq a_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N
a_{1} \cdots a_{2N}
Output
Print the lexicographically smallest sequence that Snuke can make.
Sample Input 1
3 2 1 3 1 2 2
Sample Output 1
1 2
- We choose x = (2).
- Then, the resulting sequence will be (1,2), the lexicographically smallest possible result.
Sample Input 2
10 38 38 80 62 62 67 38 78 74 52 53 77 59 83 74 63 80 61 68 55
Sample Output 2
38 38 38 52 53 77 80 55
Sample Input 3
12 52 73 49 63 55 74 35 68 22 22 74 50 71 60 52 62 65 54 70 59 65 54 60 52
Sample Output 3
22 22 50 65 54 52