CF1927E.Klever Permutation
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given two integers n and k ( k≤n ), where k is even.
A permutation of length n is an array consisting of n distinct integers from 1 to n in any order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (as 2 appears twice in the array) and [0,1,2] is also not a permutation (as n=3 , but 3 is not present in the array).
Your task is to construct a k -level permutation of length n .
A permutation is called k -level if, among all the sums of continuous segments of length k (of which there are exactly n−k+1 ), any two sums differ by no more than 1 .
More formally, to determine if the permutation p is k -level, first construct an array s of length n−k+1 , where si=∑j=ii+k−1pj , i.e., the i -th element is equal to the sum of pi,pi+1,…,pi+k−1 .
A permutation is called k -level if max(s)−min(s)≤1 .
Find any k -level permutation of length n .
输入格式
The first line of the input contains a single integer t ( 1≤t≤104 ) — the number of test cases. This is followed by the description of the test cases.
The first and only line of each test case contains two integers n and k ( 2≤k≤n≤2⋅105 , k is even), where n is the length of the desired permutation.
It is guaranteed that the sum of n for all test cases does not exceed 2⋅105 .
输出格式
For each test case, output any k -level permutation of length n .
It is guaranteed that such a permutation always exists given the constraints.
输入输出样例
输入#1
5 2 2 3 2 10 4 13 4 7 4
输出#1
2 1 1 3 2 1 8 4 10 2 7 5 9 3 6 4 10 1 13 5 9 2 12 6 8 3 11 7 1 6 3 7 2 5 4
说明/提示
In the second test case of the example:
- p1+p2=3+1=4 ;
- p2+p3=1+2=3 .
The maximum among the sums is 4 , and the minimum is 3 .