Sort It Out

题目描述

FJ 有 $N$ 头奶牛（彼此不同，编号为 $1 \ldots N$）按一行站着。FJ 喜欢他的奶牛按编号递增排序，但不幸的是它们目前是乱序的。过去 FJ 曾用过诸如“冒泡排序”之类的开创性算法来给奶牛排序，但今天他很懒。于是他会一次对一头特定的奶牛大喊，让她“把事情理顺”。

当被大喊时，一头奶牛会确保自己（从她的视角）不是乱序的。只要她右边紧挨着的奶牛编号更小，她们就交换位置。然后，只要她左边紧挨着的奶牛编号更大，她们就交换位置。最后，这头奶牛就完成了“把事情理顺”；此时她左边的奶牛编号会更小，而她右边的奶牛编号会更大。

FJ 想选择一个奶牛子集，然后反复按顺序对该子集中的奶牛逐个大喊（按编号递增的顺序），直到全部 $N$ 头奶牛都排好序为止。例如，如果他选择编号为 $\{2, 4, 5\}$ 的子集，那么他会先对奶牛 $2$ 大喊，再对奶牛 $4$ 大喊，再对奶牛 $5$ 大喊。如果 $N$ 头奶牛仍未排好序，他就会再次对同样这些奶牛大喊，重复进行，直到需要为止。

由于 FJ 不确定哪些奶牛会认真听话，他想最小化这个子集的大小。此外，FJ 认为数字 $K$ 非常幸运。请你帮助他找出：在所有满足“反复对其大喊最终能使所有奶牛排序”的、且大小最小的子集中，按字典序排在第 $K$ 小的那个子集。

如果集合 $S$ 与集合 $T$ 都是 $\{1,\dots,N\}$ 的子集，将 $S$ 的元素按递增顺序列出得到一个列表，将 $T$ 的元素按递增顺序列出得到一个列表；若 $S$ 的列表在字典序上小于 $T$ 的列表，则称子集 $S$ 的字典序小于子集 $T$。例如，$\{1, 3, 6\}$ 的字典序小于 $\{1, 4, 5\}$。

输入格式

第一行包含一个整数 $N$。 第二行包含一个整数 $K$（$1 \leq K \leq 10^{18}$）。 第三行包含 $N$ 个用空格分隔的整数，表示从左到右的奶牛编号。 保证至少存在 $K$ 个合法的子集。

输出格式

输出第一行应为最小子集的大小。 接下来的若干行应为大小最小的子集中按字典序第 $K$ 小的那个子集所包含的奶牛编号，每行一个编号，按递增顺序输出。

4 1
4 2 1 3

2
1
4

提示

Scoring : 在占 $3/16$ 分值的测试点中，$N \leq 6$ 且 $K = 1$。在额外占 $5/16$ 分值的测试点中，$K = 1$。在额外占 $8/16$ 分值的测试点中，没有进一步限制。 我们从数组 $\mathtt{\:4\:\; 2\:\; 1\:\; 3\:}$ 开始。在 FJ 对编号为 1 的奶牛大喊后，数组变为 $\mathtt{\:1\:\; 4\:\; 2\:\; 3\:}$。当 FJ 对编号为 4 的奶牛大喊时，数组会变为 $\mathtt{\:1\:\; 2\:\; 3\:\; 4\:}$。此时数组已排序。 题目致谢：Spencer Compton

标签: USACO|2018|Platinum

来源

USACO|2018|Platinum