問題一覧 > 通常問題

No.1597 Matrix Sort

レベル : / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 178
作問者 : e869120e869120 / テスター : penguinmanpenguinman ygussanyygussany
10 ProblemId : 6418 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-09 22:13:32

問題文

次のように定義される $N \times N$ 行列 $E$ があります。

  • $E$ の $(i, j)$ 成分を $E_{i, j}$ とするとき、$E_{i, j} = (A_i + B_j) \bmod P$ $[0 \leq E_{i, j} < P]$ である。
数列 $A = (A_1, A_2, \dots, A_N), B = (B_1, B_2, \dots, B_N)$ が与えられるので、行列 $E$ の要素を小さい順に並べ替えたときに、$K$ 番目に来る値を求めてください。

入力

$N$ $K$ $P$
$A_1$ $A_2$ $A_3$ $\dots$ $A_N$
$B_1$ $B_2$ $B_3$ $\dots$ $B_N$

出力

答えを出力してください。

制約

  • $1 \leq N \leq 100000$
  • $1 \leq K \leq N^2$
  • $2 \leq P \leq 10^7$
  • $0 \leq A_i < P$
  • $0 \leq B_i < P$
  • 入力はすべて整数

サンプル

サンプル1
入力
3 3 10
8 6 9
1 2 0
出力
1

行列 $E$ は次のようになります。要素を小さい順に並べ替えると、$(0, 0, 1, 6, 7, 8, 8, 9, 9)$ となるため、$K=3$ 番目に小さい値は $1$　です。
よって、$1$ を出力すれば正解となります。 $$ E = \begin{bmatrix} 9 & 0 & 8 \\ 7 & 8 & 6 \\ 0 & 1 & 9 \end{bmatrix} $$

サンプル2
入力
4 12 10
1 1 1 1
1 1 1 1
出力
2

行列 $E$ のすべての要素が $2$ であるため、$K=12$ 番目に小さい値は $2$ です。

サンプル3
入力
20 219 10000000
95721 5276873 324359 9685767 3366751 8559371 9585372 727158 1078765 8724976 6215265 7865821 2935346 8733718 2938209 505494 2495042 1209011 1977113 737232
5035685 7810192 1491963 2260046 7337814 9260042 3663277 6685733 4512005 1467792 390472 7697153 974165 7614120 8286425 8471713 9075871 3634602 9635043 6791062
出力
5772917

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。