問題一覧 > 通常問題

No.2382 Amidakuji M

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 122
作問者 : 👑 箱箱 / テスター : 👑 KazunKazun
0 ProblemId : 8717 / 出題時の順位表 / 自分の提出
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。