結果

問題 No.2436 Min Diff Distance
ユーザー lam6er
提出日時 2025-03-20 21:18:02
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,285 bytes
コンパイル時間 180 ms
コンパイル使用メモリ 82,248 KB
実行使用メモリ 190,056 KB
最終ジャッジ日時 2025-03-20 21:19:06
合計ジャッジ時間 4,496 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read().split()
    n = int(input[0])
    xs = []
    ys = []
    idx = 1
    for _ in range(n):
        x = int(input[idx])
        y = int(input[idx + 1])
        xs.append(x)
        ys.append(y)
        idx += 2
    
    s = [xs[i] + ys[i] for i in range(n)]
    d = [xs[i] - ys[i] for i in range(n)]
    
    max_s = max(s)
    min_s = min(s)
    max_d = max(d)
    min_d = min(d)
    
    # Define the four sorted lists
    # sorted_x is indices sorted by x, then y
    sorted_x = sorted(range(n), key=lambda i: (xs[i], ys[i]))
    sorted_y = sorted(range(n), key=lambda i: (ys[i], xs[i]))
    sorted_s = sorted(range(n), key=lambda i: (s[i], xs[i]))
    sorted_d = sorted(range(n), key=lambda i: (d[i], xs[i]))
    
    # Build position arrays
    pos_x = [0] * n
    for idx_list, original_i in enumerate(sorted_x):
        pos_x[original_i] = idx_list
    pos_y = [0] * n
    for idx_list, original_i in enumerate(sorted_y):
        pos_y[original_i] = idx_list
    pos_s = [0] * n
    for idx_list, original_i in enumerate(sorted_s):
        pos_s[original_i] = idx_list
    pos_d = [0] * n
    for idx_list, original_i in enumerate(sorted_d):
        pos_d[original_i] = idx_list
    
    k = 5
    min_distances = [float('inf')] * n
    
    for i in range(n):
        current_min = float('inf')
        for sorted_list, pos in [(sorted_x, pos_x), (sorted_y, pos_y), (sorted_s, pos_s), (sorted_d, pos_d)]:
            p = pos[i]
            start = max(0, p - k)
            end = min(len(sorted_list) - 1, p + k)
            for idx in range(start, end + 1):
                j = sorted_list[idx]
                if j == i:
                    continue
                current_dist = abs(xs[i] - xs[j]) + abs(ys[i] - ys[j])
                if current_dist < current_min:
                    current_min = current_dist
        min_distances[i] = current_min
    
    min_p = float('inf')
    for i in range(n):
        a = max_s - s[i]
        b = s[i] - min_s
        c = max_d - d[i]
        d_i = d[i] - min_d
        current_max = max(a, b, c, d_i)
        current_p = abs(current_max - min_distances[i])
        if current_p < min_p:
            min_p = current_p
    
    print(min_p)

if __name__ == '__main__':
    main()
0