A16639 | $Inversion Value of a Permutation$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

长度为 $n$ 的排列是一个包含 $n$ 个整数的数组，其中每个 $1$ 到 $n$ 的数字恰好出现一次。对于一个排列 $p$，如果存在一对下标 $(i, j)$，满足 $i < j$ 且 $p_i > p_j$，则称 $(i, j)$ 是排列 $p$ 的一个逆序对。 对于排列 $p$，我们定义它的“逆序区间值”是：所有包含至少一个逆序对的子区间的数量。形式化地说，这等价于满足条件的整数对 $(l, r)$ 的个数（$1 \leq l < r \leq n$），使得区间 $[l, r]$ 存在一对下标 $(i, j)$ 满足 $l \leq i < j \leq r$ 且 $p_i > p_j$。 例如，对于排列 $[3, 1, 4, 2]$，其逆序区间值为 $5$。 现给定两个整数 $n$ 和 $k$。请你构造一个长度为 $n$ 的排列，使其逆序区间值恰好等于 $k$。

第一行包含一个整数 $t$（$1 \leq t \leq 500$）——表示测试用例的数量。 接下来每个测试用例一行，包含两个整数 $n$ 和 $k$（$2 \leq n \leq 30$；$0 \leq k \leq \dfrac{n(n-1)}{2}$）。

对于每个测试用例，输出如下结果： - 如果不存在符合条件的排列，输出单个整数 $0$； - 否则，输出 $n$ 个两两不同、从 $1$ 到 $n$ 的整数，表示所构造的排列。若存在多种答案，输出任意一种均可。

输入 #1

输出 #1

3 1 4 2
5 4 3 2 1
1 2 3 4 5
2 3 5 6 1 4
0

C++ 编辑器

输入

输出