CFCF2145D.Inversion Value of a Permutation
普及+/提高
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
长度为 n 的排列是一个包含 n 个整数的数组,其中每个 1 到 n 的数字恰好出现一次。对于一个排列 p,如果存在一对下标 (i,j),满足 i<j 且 pi>pj,则称 (i,j) 是排列 p 的一个逆序对。
对于排列 p,我们定义它的“逆序区间值”是:所有包含至少一个逆序对的子区间的数量。形式化地说,这等价于满足条件的整数对 (l,r) 的个数(1≤l<r≤n),使得区间 [l,r] 存在一对下标 (i,j) 满足 l≤i<j≤r 且 pi>pj。
例如,对于排列 [3,1,4,2],其逆序区间值为 5。
现给定两个整数 n 和 k。请你构造一个长度为 n 的排列,使其逆序区间值恰好等于 k。
输入格式
第一行包含一个整数 t(1≤t≤500)——表示测试用例的数量。
接下来每个测试用例一行,包含两个整数 n 和 k(2≤n≤30;0≤k≤2n(n−1))。
输出格式
对于每个测试用例,输出如下结果:
- 如果不存在符合条件的排列,输出单个整数 0;
- 否则,输出 n 个两两不同、从 1 到 n 的整数,表示所构造的排列。若存在多种答案,输出任意一种均可。
输入输出样例
输入#1
5 4 5 5 10 5 0 6 8 3 1
输出#1
3 1 4 2 5 4 3 2 1 1 2 3 4 5 2 3 5 6 1 4 0