luogu#P7957. [COCI2014-2015#6] KRATKI

[COCI2014-2015#6] KRATKI

题目背景

我们都非常熟悉「最长单调子序列」问题:

给定一个长度为 nn 的数列,你需要求出它的 LMS(即最长单调子序列)的长度。
请注意,这里「LMS」是指「递增子序列和递增递减子序列中更长的一个」。
即需要对 LIS 和 LDS 的长度取最大值。

现在你需要解决一个 LMS 的逆问题。

题目描述

给定数列的长度 nn

你需要构造出一个 nn 的排列,使得它的 LMS 长度为 kk

输入格式

仅一行两个整数 n,kn,k

输出格式

如果无解,输出 -1\texttt{-1}

否则输出一行 nn 个整数,即你构造的数列。

如果存在多组解,输出任意一种。

4 3
1 4 2 3
5 1
-1
5 5
1 2 3 4 5

提示

样例 1 说明

{1,4,2,3}\{1,4,2,3\}LMS{1,2,3}\{1,2,3\},长度为 33,符合要求。

数据规模与约定

本题采用 Special Judge。

对于 100%100\% 的数据,有 1kn1061\le k\le n\le 10^6

说明

按原题配置,满分 120 分。

译自 COCI 2014-2015 Contest #6 Task D KRATKI

由于原数据没有一些特殊的数据,本题添加了数据 #11。如果你没通过它,会得到 120 Unaccept。