No.2382 Amidakuji M
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 125
作問者 :
箱星
/ テスター :
Kazun
タグ : / 解いたユーザー数 125
作問者 :
箱星
/ テスター :
Kazun
問題文最終更新日: 2023-05-19 20:17:22
問題文
はじめ数列は $(1,2,\ldots,N)$ です。
$M$ の倍数 $K$ であって次の条件を満たすものが存在するか判定し、存在する場合は最小値を求めてください。
- 数列の隣り合う $2$ つの要素を入れ替える操作をちょうど $K$ 回行うことで、数列を $(P_1,P_2,\ldots,P_N)$ にできる。
制約
- $1\le N\le 2\times 10^5$
- $1\le M\le 10^{18}$
- $P$ は $(1,2,\ldots,N)$ の順列
- 入力はすべて整数
入力
$N$ $M$ $P_1$ $P_2$ $\cdots$ $P_N$
出力
$K$ の最小値を出力してください。存在しない場合は $-1$ を出力してください。
サンプル
サンプル1
入力
4 3 4 1 3 2
出力
6
$(1,2,3,4)\to (2,1,3,4)\to (2,1,4,3)\to (2,4,1,3)\to (4,2,1,3)\to (4,1,2,3)\to (4,1,3,2)$ のように $6$ 回の操作でできます。$0,3$ 回ではできません。
サンプル2
入力
2 100 2 1
出力
-1
サンプル3
入力
3 987654321 1 2 3
出力
0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。