結果
問題 | No.1597 Matrix Sort |
ユーザー |
![]() |
提出日時 | 2021-07-09 22:15:28 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,119 ms / 1,500 ms |
コード長 | 1,670 bytes |
コンパイル時間 | 2,661 ms |
コンパイル使用メモリ | 77,484 KB |
実行使用メモリ | 68,348 KB |
最終ジャッジ日時 | 2024-07-01 16:50:26 |
合計ジャッジ時間 | 23,597 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;public class Main {public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] sa = br.readLine().split(" ");int n = Integer.parseInt(sa[0]);long k = Long.parseLong(sa[1]);int p = Integer.parseInt(sa[2]);sa = br.readLine().split(" ");int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = Integer.parseInt(sa[i]) % p;}sa = br.readLine().split(" ");int[] b = new int[n];for (int i = 0; i < n; i++) {b[i] = Integer.parseInt(sa[i]) % p;}br.close();Arrays.sort(a);Arrays.sort(b);long k2 = (long) n * n - k + 1;int ok = 0;int ng = p;while (Math.abs(ok - ng) > 1) {int mid = (ok + ng) / 2;long cnt = 0;for (int i = 0; i < n; i++) {if (a[i] <= mid) {int min = mid - a[i];int max = p - a[i];int l = binarySearch(b, min);int r = binarySearch(b, max);cnt += r - l;} else {int min = 0;int max = p - a[i];int l = binarySearch(b, min);int r = binarySearch(b, max);cnt += r - l;min = mid + p - a[i];max = p;l = binarySearch(b, min);r = binarySearch(b, max);cnt += r - l;}}if (cnt >= k2) {ok = mid;} else {ng = mid;}}System.out.println(ok);}static int binarySearch(int[] array, int val) {int ok = array.length;int ng = -1;while (Math.abs(ok - ng) > 1) {int mid = (ok + ng) / 2;if (array[mid] >= val) {ok = mid;} else {ng = mid;}}return ok;}}