#P7957. [COCI2014-2015#6] KRATKI
[COCI2014-2015#6] KRATKI
题目背景
我们都非常熟悉「最长单调子序列」问题:
给定一个长度为 的数列,你需要求出它的 LMS(即最长单调子序列)的长度。
请注意,这里「LMS」是指「递增子序列和递增递减子序列中更长的一个」。
即需要对 LIS 和 LDS 的长度取最大值。
现在你需要解决一个 LMS 的逆问题。
题目描述
给定数列的长度 。
你需要构造出一个 的排列,使得它的 LMS 长度为 。
输入格式
仅一行两个整数 。
输出格式
如果无解,输出 。
否则输出一行 个整数,即你构造的数列。
如果存在多组解,输出任意一种。
4 3
1 4 2 3
5 1
-1
5 5
1 2 3 4 5
提示
样例 1 说明
的 LMS 为 ,长度为 ,符合要求。
数据规模与约定
本题采用 Special Judge。
对于 的数据,有 。
说明
按原题配置,满分 120 分。
译自 COCI 2014-2015 Contest #6 Task D KRATKI。
由于原数据没有一些特殊的数据,本题添加了数据 #11。如果你没通过它,会得到 120 Unaccept。