← 返回题目列表

AtCoder · arc160_a

A. 反转并计数

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给你一个排列 A = (A_1, A_2, \dots, A_N) of (1, 2, \dots, N).
对于一对整数 (L, R) 这样 1 \leq L \leq R \leq N,让 f(L, R) 是通过反转获得的排列 L-th 通过 R第一个元素 A,即替换 A_L, A_{L+1}, \dots, A_{R-1}, A_R 与 A_R, A_{R-1}, \dots, A_{L+1}, A_{L} 同时进行。

有 \frac{N(N + 1)}{2} 选择方式 (L, R) 这样 1 \leq L \leq R \leq N.
如果排列 f(L, R) 对于所有此类对 (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。

  1. |S| \lt |T| 和 (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
  2. 有一个整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace 满足以下两个条件。
    • (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

输出

让 B =(B_1, B_2, \dots, B_N) 是 K排列列表中从前面开始的第一个排列 f(L, R) 按字典顺序排序。
打印 B 采用以下格式:

B_1 B_2 \dots B_N

示例输入 1

3 5
1 3 2

示例输出 1

2 3 1

这是排列 f(L, R) 对于所有对 (L, R) 这样 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)

当它们按字典顺序排序时,第五种排列是 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