結果
問題 | No.2612 Close the Distance |
ユーザー | Mitarushi |
提出日時 | 2024-01-06 13:20:12 |
言語 | Nim (2.0.2) |
結果 |
AC
|
実行時間 | 1,112 ms / 3,000 ms |
コード長 | 1,555 bytes |
コンパイル時間 | 3,909 ms |
コンパイル使用メモリ | 66,764 KB |
実行使用メモリ | 47,580 KB |
最終ジャッジ日時 | 2024-01-20 00:17:43 |
合計ジャッジ時間 | 22,156 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,548 KB |
testcase_01 | AC | 1 ms
6,548 KB |
testcase_02 | AC | 1 ms
6,548 KB |
testcase_03 | AC | 2 ms
6,548 KB |
testcase_04 | AC | 2 ms
6,548 KB |
testcase_05 | AC | 2 ms
6,548 KB |
testcase_06 | AC | 742 ms
47,568 KB |
testcase_07 | AC | 613 ms
47,572 KB |
testcase_08 | AC | 685 ms
47,516 KB |
testcase_09 | AC | 730 ms
47,564 KB |
testcase_10 | AC | 740 ms
47,580 KB |
testcase_11 | AC | 747 ms
47,568 KB |
testcase_12 | AC | 742 ms
46,148 KB |
testcase_13 | AC | 753 ms
47,516 KB |
testcase_14 | AC | 604 ms
47,580 KB |
testcase_15 | AC | 701 ms
44,148 KB |
testcase_16 | AC | 1,112 ms
47,364 KB |
testcase_17 | AC | 983 ms
45,844 KB |
testcase_18 | AC | 980 ms
47,344 KB |
testcase_19 | AC | 1,006 ms
47,456 KB |
testcase_20 | AC | 915 ms
47,432 KB |
testcase_21 | AC | 1,092 ms
47,340 KB |
testcase_22 | AC | 904 ms
47,352 KB |
testcase_23 | AC | 955 ms
47,344 KB |
testcase_24 | AC | 855 ms
47,344 KB |
testcase_25 | AC | 1,020 ms
47,344 KB |
testcase_26 | AC | 1 ms
6,548 KB |
ソースコード
import strutils, sequtils iterator readInt(): int {.closure.} = while true: let line = stdin.readLine.split.map(parseInt) for x in line: yield x var input = readInt let n = input() var x = newSeq[int64]() y = newSeq[int64]() for _ in 0..<n: let (a, b) = (input(), input()) x.add(a + b) y.add(b - a) let xy = zip(x, y) iterator exclude_box(xy: openArray[(int64, int64)], box_x, box_y, a: int64): (int64, int64) = for (x, y) in xy: if not (box_x <= x and x <= box_x + a and box_y <= y and y <= box_y + a): yield (x, y) proc is_not_more_than(xy: openArray[(int64, int64)], a, k: int64): bool = if xy.len <= k: return true if k == 0: return false let x_min = xy.mapIt(it[0]).min x_max = xy.mapIt(it[0]).max y_min = xy.mapIt(it[1]).min y_max = xy.mapIt(it[1]).max if is_not_more_than(exclude_box(xy, x_min, y_min, a).toSeq, a, k - 1): return true if k >= 2 and is_not_more_than(exclude_box(xy, x_min, y_max - a, a).toSeq, a, k - 1): return true if k >= 3 and is_not_more_than(exclude_box(xy, x_max - a, y_min, a).toSeq, a, k - 1): return true if k >= 3 and is_not_more_than(exclude_box(xy, x_max - a, y_max - a, a).toSeq, a, k - 1): return true false let max_a = max(x.max - x.min, y.max - y.min) var ng = -1i64 ok = max_a while ok - ng > 1: let m = (ok + ng) div 2 if is_not_more_than(xy, m, 3): ok = m else: ng = m echo ok