/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
(1, 2, \dots, N) の順列 A = (A_1, A_2, \dots, A_N) が与えられます。
1 \leq L \leq R \leq N を満たす整数の組 (L, R) に対して、A の L 番目から R 番目までの要素を反転してできる順列を f(L, R) とします。
ここで、「A の L 番目から R 番目までの要素を反転する」とは、A_L, A_{L+1}, \dots, A_{R-1}, A_R を A_R, A_{R-1}, \dots, A_{L+1}, A_{L} に同時に置き換えることを言います。
(L, R) を 1 \leq L \leq R \leq N を満たすように選ぶ方法は \frac{N(N + 1)}{2} 通りあります。
このような (L, R) の組全てに対して順列 f(L, R) をすべて列挙して辞書順にソートしたときに、先頭から K 番目にある順列を求めてください。
数列の辞書順とは？
数列 S = (S_1,S_2,\ldots,S_{|S|}) が数列 T = (T_1,T_2,\ldots,T_{|T|}) より辞書順で小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。 ここで、|S|, |T| はそれぞれ S, T の長さを表します。
- |S| \lt |T| かつ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})。
- ある整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace が存在して、下記の 2 つがともに成り立つ。
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
- S_i が T_i より（数として）小さい。
制約
- 1 \leq N \leq 7000
- 1 \leq K \leq \frac{N(N + 1)}{2}
- A は (1, 2, \dots, N) の順列
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \dots A_N
出力
順列 f(L, R) を列挙して辞書順にソートしたときに、先頭から K 番目にある順列を B =(B_1, B_2, \dots, B_N) とする。
このとき以下の形式で B を出力せよ。
B_1 B_2 \dots B_N
入力例 1
3 5 1 3 2
出力例 1
2 3 1
1 \leq L \leq R \leq N を満たす (L, R) の組全てに対して順列 f(L, R) をすべて列挙すると次のようになります。
- f(1, 1) = (1, 3, 2)
- f(1, 2) = (3, 1, 2)
- f(1, 3) = (2, 3, 1)
- f(2, 2) = (1, 3, 2)
- f(2, 3) = (1, 2, 3)
- f(3, 3) = (1, 3, 2)
これらを辞書順にソートしたときに 5 番目に来る順列は f(1, 3) = (2, 3, 1) です。よってこれを出力します。
入力例 2
5 15 1 2 3 4 5
出力例 2
5 4 3 2 1
答えは f(1, 5) です。
入力例 3
10 37 9 2 1 3 8 7 10 4 5 6
出力例 3
9 2 1 6 5 4 10 7 8 3
Score : 400 points
Problem Statement
You are given a permutation A = (A_1, A_2, \dots, A_N) of (1, 2, \dots, N).
For a pair of integers (L, R) such that 1 \leq L \leq R \leq N, let f(L, R) be the permutation obtained by reversing the L-th through R-th elements of A, that is, replacing A_L, A_{L+1}, \dots, A_{R-1}, A_R with A_R, A_{R-1}, \dots, A_{L+1}, A_{L} simultaneously.
There are \frac{N(N + 1)}{2} ways to choose (L, R) such that 1 \leq L \leq R \leq N.
If the permutations f(L, R) for all such pairs (L, R) are listed and sorted in lexicographical order, what is the K-th permutation from the front?
What is lexicographical order on sequences?
A sequence S = (S_1,S_2,\ldots,S_{|S|}) is said to be lexicographically smaller than a sequence T = (T_1,T_2,\ldots,T_{|T|}) if and only if 1. or 2. below holds. Here, |S| and |T| denote the lengths of S and T, respectively.
- |S| \lt |T| and (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
- There is an integer 1 \leq i \leq \min\lbrace |S|, |T| \rbrace that satisfies both of the following.
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1}).
- S_i is smaller than T_i (as a number).
Constraints
- 1 \leq N \leq 7000
- 1 \leq K \leq \frac{N(N + 1)}{2}
- A is a permutation of (1, 2, \dots, N).
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_N
Output
Let B =(B_1, B_2, \dots, B_N) be the K-th permutation from the front in the list of the permutations f(L, R) sorted in lexicographical order.
Print B in the following format:
B_1 B_2 \dots B_N
Sample Input 1
3 5 1 3 2
Sample Output 1
2 3 1
Here are the permutations f(L, R) for all pairs (L, R) such that 1 \leq L \leq R \leq N.
- f(1, 1) = (1, 3, 2)
- f(1, 2) = (3, 1, 2)
- f(1, 3) = (2, 3, 1)
- f(2, 2) = (1, 3, 2)
- f(2, 3) = (1, 2, 3)
- f(3, 3) = (1, 3, 2)
When these are sorted in lexicographical order, the fifth permutation is f(1, 3) = (2, 3, 1), which should be printed.
Sample Input 2
5 15 1 2 3 4 5
Sample Output 2
5 4 3 2 1
The answer is f(1, 5).
Sample Input 3
10 37 9 2 1 3 8 7 10 4 5 6
Sample Output 3
9 2 1 6 5 4 10 7 8 3