AT_arc134_d.[ARC134D] Concatenate Subsequences

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个长度为 $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 < T$ ，大于则记作 $S > T$ 。

取 $S$ 和 $T$ 中较短的那个数列的长度为 $L$ 。依次比较 $i=1,2,\ldots,L$ 时 $S_i$ 和 $T_i$ 是否相等。
如果存在 $S_i \neq T_i$ ，取最小的这样的 $i$ 为 $j$ ，比较 $S_j$ 和 $T_j$ ，若 $S_j$ 比 $T_j$ 小，则 $S < T$ ，大则 $S > T$ ，算法结束。
如果所有 $S_i = T_i$ ，则比较数列长度，短的字典序小，长的字典序大，算法结束。

输入格式

输入从标准输入读入，格式如下：

$N$ $a_1$ $a_2$ $\cdots$ $a_{2N}$

输出格式

请输出すぬけ君可以构造出的所有数列中，字典序最小的那个。

输入输出样例

输入#1
```
3
2 1 3 1 2 2
```
输出#1
```
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

说明/提示

数据范围

所有输入均为整数。
$1 \leq N \leq 10^5$
$1 \leq a_i \leq 10^9$

样例解释 1

取 $x = (2)$ 时，构造出的数列为 $(1,2)$ ，这是字典序最小的。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页