← 返回题目列表

AtCoder · toyota2023spring_final_d

D. 双旋转

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

配点 : 700 点

問題文

(0,1,\cdots,N-1) 的排列 给出了 P=(P_0,P_1,\cdots,P_{N-1}) 。

整数 a,b (0 \leq a,b \leq N-1),排列 f(a,b) 如下。

  • f(a,b)=(q_0,q_1,\cdots,q_{N-1}) 除此之外,q_{(i+a \pmod N)}=(P_i+b \pmod N) (0 \leq i \leq N-1)。 当找到

全部 a,b 反对 f(a,b) 时, 您将得到N^2 排列。 考虑按字典顺序对这些排列进行排序。 排序后,从头开始 找到位于 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 存在并且以下内容 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 2 \times 10^5
  • 1 \leq K \leq N^2
  • (P_0,P_1,\cdots,P_{N-1}) 是 您也可以写 (0,1,\cdots,N-1) 是 的排列。
  • 所有输入值均为整数

入力

输入是按以下格式从标准输入给出的。

N K
P_0 P_1 \cdots P_{N-1}

出力

输出答案的排列,用空格分隔元素。


入力例 1

2 2
0 1

出力例 1

0 1

f(a,b) 如下 4 是可能的。

  • f(0,0)=(0,1)
  • f(0,1)=(1,0)
  • f(1,0)=(1,0)
  • f(1,1)=(0,1)

如果我们按字典顺序排列这些排列,我们得到(0,1),(0,1),(1,0),(1,0) 变为。 因此,在这个 2 位置 (0,1) 就是答案。


入力例 2

4 6
0 2 1 3

出力例 2

1 2 0 3

入力例 3

10 79
6 5 9 8 7 1 3 2 0 4

出力例 3

7 9 8 2 1 0 4 6 5 3