C. Gorilla and Permutation
time limit per test
2 seconds
memory limit per test
256 megabytes
Gorilla and Noobish_Monk found three numbers nn, mm, and kk (m<km<k). They decided to construct a permutation†† of length nn.
For the permutation, Noobish_Monk came up with the following function: g(i)g(i) is the sum of all the numbers in the permutation on a prefix of length ii that are not greater than mm. Similarly, Gorilla came up with the function ff, where f(i)f(i) is the sum of all the numbers in the permutation on a prefix of length ii that are not less than kk. A prefix of length ii is a subarray consisting of the first ii elements of the original array.
For example, if n=5n=5, m=2m=2, k=5k=5, and the permutation is [5,3,4,1,2][5,3,4,1,2], then:
- f(1)=5f(1)=5, because 5≥55≥5; g(1)=0g(1)=0, because 5>25>2;
- f(2)=5f(2)=5, because 3<53<5; g(2)=0g(2)=0, because 3>23>2;
- f(3)=5f(3)=5, because 4<54<5; g(3)=0g(3)=0, because 4>24>2;
- f(4)=5f(4)=5, because 1<51<5; g(4)=1g(4)=1, because 1≤21≤2;
- f(5)=5f(5)=5, because 2<52<5; g(5)=1+2=3g(5)=1+2=3, because 2≤22≤2.
Help them find a permutation for which the value of (∑ni=1f(i)−∑ni=1g(i))(∑i=1nf(i)−∑i=1ng(i)) is maximized.
††A permutation of length nn is an array consisting of nn distinct integers from 11 to nn in any order. For example, [2,3,1,5,4][2,3,1,5,4] is a permutation, but [1,2,2][1,2,2] is not a permutation (as 22 appears twice in the array) and [1,3,4][1,3,4] is also not a permutation (as n=3n=3, but 44 appears in the array).
Input
The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases.
The only line of each case contains three integers nn, mm, kk (2≤n≤1052≤n≤105; 1≤m<k≤n1≤m<k≤n) — the size of the permutation to be constructed and two integers.
It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105.
Output
For each test case, output the permutation — a set of numbers that satisfies the conditions of the problem. If there are multiple solutions, output any of them.
Example
Input
Copy
3
5 2 5
3 1 3
10 3 8
Output
Copy
5 3 4 1 2 3 2 1 10 9 8 4 7 5 6 1 2 3
Note
In the first example, (∑ni=1f(i)−∑ni=1g(i))=5⋅5−(0⋅3+1+3)=25−4=21
解题说明：此题是一道模拟题，为了保证结果尽可能大，可以采用贪心算法，将大于等于k的元素按降序放在排列最前面，将小于等于m的元素按升序放在排列最后面
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll n, m, k, a[N];int main()
{int tt;cin >> tt;while (tt--){cin >> n >> m >> k;ll x = n, y = 1;for (int i = 1; i <= n - m; i++){a[i] = x--;}for (int i = n - m + 1; i <= n; i++){a[i] = y++;}for (int i = 1; i <= n; i++){cout << a[i] << ' ';}cout << endl;}return 0;
}