#2330. 逆序对

逆序对

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你有一个长度为n\red{n}的序列a,a={1,2,3,...,k1,k,k1,k2,...,k(nk)}(k<=n<2k)\red{a,a=\{1,2,3,...,k-1,k,k-1,k-2,...,k-(n-k)\}(k<=n<2k)}

我们称a\red{a}中的一个逆序对为下标i,j\red{i,j}的两个元素有a[i]>a[j](i<j)\red{a[i]>a[j](i<j)}

你能构造出一些长度为k\red{k}的排列p\red{p,}然后用以下规则构造长度为n\red{n}序列b\red{b:}b[i]=p[a[i]]\red{b[i]=p[a[i]] }

你的目标是找到一个排列p\red{p,}b\red{b}中逆序对的个数不超过a\red{a}中逆序对个数的情况下使得b\red{b}的字典序最 大。

小提示:长度为k\red{k}的排列列中1k\red{1\sim k}各出现且仅出现一次。

另一个小提示:序列s\red{s}的字典序小于t\red{t}意味着s\red{s}t\red{t}的前缀或者第一个si\red{s_i≠}ti\red{t_i}si<ti\red{s_i<t_i }

输入格式

输入包括一行两个整数n,k——a\red{n,k——a}的长度及其峰值。

输出格式

对于每一个测试数据,输k\red{k}个整数一一排列p\red{p}使得b\red{b}是不增加逆序对个数的字典序最大序列。

可以证明p\red{p}是存在且唯一的。

样例

输入样例

2 2

输出样例

1 2

提示

对于50%\red{50\%}的数据,1<=k<=102\red{1<=k<=10^2}

对于100%\red{100\%}的数据,k<=n<=2k,1<=k<=105\red{k<=n<=2k,1<=k<=10^5}

国庆集训11

未参加
状态
已结束
规则
IOI
题目
7
开始于
2022-10-6 9:00
结束于
2022-10-6 12:00
持续时间
3 小时
主持人
参赛人数
12