D - Dual Rotation Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 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