CFCF2145D.Inversion Value of a Permutation

普及+/提高

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

长度为 nn 的排列是一个包含 nn 个整数的数组,其中每个 11nn 的数字恰好出现一次。对于一个排列 pp,如果存在一对下标 (i,j)(i, j),满足 i<ji < jpi>pjp_i > p_j,则称 (i,j)(i, j) 是排列 pp 的一个逆序对。

对于排列 pp,我们定义它的“逆序区间值”是:所有包含至少一个逆序对的子区间的数量。形式化地说,这等价于满足条件的整数对 (l,r)(l, r) 的个数(1l<rn1 \leq l < r \leq n),使得区间 [l,r][l, r] 存在一对下标 (i,j)(i, j) 满足 li<jrl \leq i < j \leq rpi>pjp_i > p_j

例如,对于排列 [3,1,4,2][3, 1, 4, 2],其逆序区间值为 55

现给定两个整数 nnkk。请你构造一个长度为 nn 的排列,使其逆序区间值恰好等于 kk

输入格式

第一行包含一个整数 tt1t5001 \leq t \leq 500)——表示测试用例的数量。

接下来每个测试用例一行,包含两个整数 nnkk2n302 \leq n \leq 300kn(n1)20 \leq k \leq \dfrac{n(n-1)}{2})。

输出格式

对于每个测试用例,输出如下结果:

  • 如果不存在符合条件的排列,输出单个整数 00
  • 否则,输出 nn 个两两不同、从 11nn 的整数,表示所构造的排列。若存在多种答案,输出任意一种均可。

输入输出样例

  • 输入#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
首页