結果

問題 No.2157 崖
ユーザー LyricalMaestro
提出日時 2025-03-29 17:46:57
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,954 bytes
コンパイル時間 444 ms
コンパイル使用メモリ 82,644 KB
実行使用メモリ 104,452 KB
最終ジャッジ日時 2025-03-29 17:47:17
合計ジャッジ時間 13,614 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11 TLE * 2 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2157

def binary_search(base_d_array, v):
    if v < base_d_array[0]:
        return -1

    low = 0
    high = len(base_d_array) - 1
    while high - low > 1:
        mid = (high + low) //2
        if base_d_array[mid] <= v:
            low = mid
        else:
            high = mid
    if base_d_array[high] <= v:
        return high
    else:
        return low
    

def solve(N, M, D, K):
    d_array = D[0]
    for i in range(1, N):
        base_d_array = d_array
        d_array = []
        for j in range(M):
            d = D[i][j]

            # 2分探索
            if d < base_d_array[0]:
                continue

            low_i_1 = binary_search(base_d_array, d - K - 1)
            highi = binary_search(base_d_array, d)
            if highi - low_i_1 > 0:
                d_array.append(d)
        if len(d_array) == 0:
            return False
    if len(d_array) == 0:
        return False
    
    return True


def main():
    N, M = map(int, input().split())
    D = []
    for _ in range(N):
        D.append(list(map(int, input().split())))

    # まずはソート
    for d_list in D:
        d_list.sort()
    
    # 座標圧縮つきBITの用意
    d_array = D[0]
    for i in range(1, N):
        base_d_array = d_array
        d_array = []
        for j in range(M):
            d = D[i][j]

            # 2分探索
            if d < base_d_array[0]:
                continue
            d_array.append(d)
        if len(d_array) == 0:
            print(-1)
            return
    if len(d_array) == 0:
        print(-1)
        return

    # 最小値を計算
    low = 0
    high = 10 ** 9
    while high - low > 1:
        mid = (high  + low) // 2
        if solve(N, M, D, mid):
            high = mid
        else:
            low = mid

    if solve(N, M, D, low):
        print(low)
    else:
        print(high)
            






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