問題一覧 > 通常問題

No.1597 Matrix Sort

レベル : / AI推定難易度 : 1550 / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 193
作問者 : e869120 / テスター : penguinman ygussany
お気に入りにしたユーザー ProblemId : 6418 / 自分の提出
問題文最終更新日: 2021-07-09 22:13:32
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
競プロ典型 90 問　期末試験 (順位表) の他の問題:

Problem Statement

There is an $N \times N$ matrix $E$ defined as follows.

  • Let $E_{i, j}$ denote the $(i, j)$ entry of $E$. Then $E_{i, j} = (A_i + B_j) \bmod P$ $[0 \leq E_{i, j} < P]$.
Given sequences $A = (A_1, A_2, \dots, A_N), B = (B_1, B_2, \dots, B_N)$, find the value that comes $K$-th when the elements of the matrix $E$ are sorted in ascending order.

Input

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

Output

Output the answer.

Constraints

  • $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$
  • All inputs are integers.

Sample

Sample 1
Input
3 3 10
8 6 9
1 2 0
Output
1

The matrix $E$ is as shown below. Sorting its elements in ascending order gives $(0, 0, 1, 6, 7, 8, 8, 9, 9)$, so the $K=3$-rd smallest value is $1$.
Therefore, outputting $1$ is correct. $$ E = \begin{bmatrix} 9 & 0 & 8 \\ 7 & 8 & 6 \\ 0 & 1 & 9 \end{bmatrix} $$

Sample 2
Input
4 12 10
1 1 1 1
1 1 1 1
Output
2

All elements of the matrix $E$ are $2$, so the $K=12$-th smallest value is $2$.

Sample 3
Input
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
Output
5772917

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