[USACO 2018 Dec P]Sort It Out
题号:NC24196
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 32 M,其他语言64 M
64bit IO Format: %lld

题目描述

FJ有N1≤N≤10^5)头奶牛(分别用1…N编号)排成一行。FJ喜欢他的奶牛以升序排列,不幸的是现在她们的顺序被打乱了。在过去FJ曾经使用一些诸如“冒泡排序”的开创性的算法来使他的奶牛排好序,但今天他想偷个懒。取而代之,他会每次对着一头奶牛叫道“按顺序排好”。当一头奶牛被叫到的时候,她会确保自己在队伍中的顺序是正确的(从她的角度看来)。只要有一头紧接在她右边的奶牛的编号比她小,她们就交换位置。然后,只要有一头紧接在她左边的奶牛的编号比她大,她们就交换位置。这样这头奶牛就完成了“按顺序排好”,在这头奶牛看来左边的奶牛编号比她小,右边的奶牛编号比她大。

FJ想要选出这些奶牛的一个子集,然后遍历这个子集,依次对着每一头奶牛发号施令(按编号递增的顺序),重复这样直到所有NN头奶牛排好顺序。例如,如果她选出了编号为{2,4,5}的奶牛的子集,那么他会喊叫奶牛2,然后是奶牛4,然后是奶牛5。如果N头奶牛此时仍未排好顺序他会再次对着这几头奶牛喊叫,如果有必要的话继续重复。

由于FJ不确定哪些奶牛比较专心,他想要使得这个子集最小。此外,他认为K是个幸运数字。请帮他求出满足重复喊叫可以使得所有奶牛排好顺序的最小子集之中字典序第K小的子集。

我们称{1,…,N}的一个子集S在字典序下小于子集T,当S的所有元素组成的序列(按升序排列)在字典序下小于T的所有元素组成的序列(按升序排列)。例如,{1,3,6} 在字典序下小于{1,4,5}。

部分分:对于占总分3/16的测试数据,N≤6,并且K=1。对于另外的占总分5/16的测试数据,K=1。对于另外的占总分8/16的测试数据,没有其他限制。

输入描述:

输入的第一行包含一个整数N。第二行包含一个整数K(1≤K≤10^18)。第三行包含N个空格分隔的整数,表示从左到右奶牛的编号。

保证存在至少K个符合要求的子集。

输出描述:

第一行输出最小子集的大小。接下来输出字典序第K小的最小子集中奶牛的编号,每行一个数,升序排列。
示例1

输入

复制
4 1
4 2 1 3

输出

复制
2
1
4

说明

开始的时候序列为4213。在FJ喊叫编号为1的奶牛之后,序列变为1423。在FJ喊叫编号为4的奶牛之后,序列变为1234。在这个时候,序列已经完成了排序。