CF1473C.No More Inversions

普及/提高-

通过率:0%

AC君温馨提醒

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

题目描述

You have a sequence aa with nn elements 1,2,3,,k1,k,k1,k2,,k(nk)1, 2, 3, \dots, k - 1, k, k - 1, k - 2, \dots, k - (n - k) ( kn<2kk \le n < 2k ).

Let's call as inversion in aa a pair of indices i<ji < j such that a[i]>a[j]a[i] > a[j] .

Suppose, you have some permutation pp of size kk and you build a sequence bb of size nn in the following manner: b[i]=p[a[i]]b[i] = p[a[i]] .

Your goal is to find such permutation pp that the total number of inversions in bb doesn't exceed the total number of inversions in aa , and bb is lexicographically maximum.

Small reminder: the sequence of kk integers is called a permutation if it contains all integers from 11 to kk exactly once.

Another small reminder: a sequence ss is lexicographically smaller than another sequence tt , if either ss is a prefix of tt , or for the first ii such that sitis_i \ne t_i , si<tis_i < t_i holds (in the first position that these sequences are different, ss has smaller number than tt ).

输入格式

The first line contains a single integer tt ( 1t10001 \le t \le 1000 ) — the number of test cases.

The first and only line of each test case contains two integers nn and kk ( kn<2kk \le n < 2k ; 1k1051 \le k \le 10^5 ) — the length of the sequence aa and its maximum.

It's guaranteed that the total sum of kk over test cases doesn't exceed 10510^5 .

输出格式

For each test case, print kk integers — the permutation pp which maximizes bb lexicographically without increasing the total number of inversions.

It can be proven that pp exists and is unique.

输入输出样例

  • 输入#1

    4
    1 1
    2 2
    3 2
    4 3

    输出#1

    1 
    1 2 
    2 1 
    1 3 2

说明/提示

In the first test case, the sequence a=[1]a = [1] , there is only one permutation p=[1]p = [1] .

In the second test case, the sequence a=[1,2]a = [1, 2] . There is no inversion in aa , so there is only one permutation p=[1,2]p = [1, 2] which doesn't increase the number of inversions.

In the third test case, a=[1,2,1]a = [1, 2, 1] and has 11 inversion. If we use p=[2,1]p = [2, 1] , then b=[p[a[1]],p[a[2]],p[a[3]]]=[2,1,2]b = [p[a[1]], p[a[2]], p[a[3]]] = [2, 1, 2] and also has 11 inversion.

In the fourth test case, a=[1,2,3,2]a = [1, 2, 3, 2] , and since p=[1,3,2]p = [1, 3, 2] then b=[1,3,2,3]b = [1, 3, 2, 3] . Both aa and bb have 11 inversion and bb is the lexicographically maximum.

首页