結果

問題 No.3166 [Cherry 7th Tune *] 桜の守人
ユーザー detteiuu
提出日時 2025-06-25 21:37:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,325 ms / 2,000 ms
コード長 1,036 bytes
コンパイル時間 452 ms
コンパイル使用メモリ 82,044 KB
実行使用メモリ 192,456 KB
最終ジャッジ日時 2025-06-25 21:38:22
合計ジャッジ時間 29,929 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #

def compress(A):
    S = sorted(A)
    D = dict()
    for i in range(len(S)):
        D[S[i]] = i
    return D

def func(P):
    R = []
    IDX = set()
    for x in X:
        l, r = x-P, x+P
        if l < 0:
            R.append((l%L, 1))
            IDX.add(l%L)
            l = 0
        if L < r:
            R.append((0, 1))
            IDX.add(0)
            R.append((r%L+0.5, -1))
            IDX.add(r%L+0.5)
            r = L
        R.append((l, 1))
        IDX.add(l)
        if r < L:
            R.append((r+0.5, -1))
            IDX.add(r+0.5)
    IDX = compress(IDX)
    C = [0]*len(IDX)
    for n, d in R:
        C[IDX[n]] += d
    for i in range(1, len(IDX)):
        C[i] += C[i-1]
    return K <= min(C)

for _ in range(int(input())):
    N, L, K = map(int, input().split())
    X = list(map(int, input().split()))

    left = 0
    right = (L+1)//2
    while left+1 < right:
        mid = (left+right)//2
        if not func(mid):
            left = mid
        else:
            right = mid
    
    print(right)
0