結果

問題 No.3051 Make All Divisible
ユーザー suisen
提出日時 2025-01-18 16:04:35
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 108 ms / 2,000 ms
コード長 967 bytes
コンパイル時間 233 ms
コンパイル使用メモリ 82,064 KB
実行使用メモリ 86,704 KB
最終ジャッジ日時 2025-06-20 02:20:23
合計ジャッジ時間 3,565 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque


def solve(n: int, k: int, a: list[int]) -> None:
    if sum(a) % k:
        print(-1)
        return

    dq: deque[int] = deque()
    threshold = k * (k - 1) // 2
    for i in range(n):
        q = (max(0, a[i] - threshold) + (k - 1)) // k
        a[i] -= q * k

    # O(n log n), but can be optimized to O(k^2) by using bucket sort
    a.sort(reverse=True)
    dq.append(a[0])
    next_push = 1

    INF = 1 << 30
    ans = INF
    t = sum(a) // k
    while True:
        e = dq.popleft()
        if e <= t:
            ans = t
        e -= k
        if e < 0:
            break

        while next_push < n and a[next_push] >= e:
            dq.append(a[next_push])
            next_push += 1

        dq.append(e)
        t -= 1

    if ans == INF:
        print(-1)
    else:
        print(ans)


t = int(input())

for _ in range(t):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    solve(n, k, a)
0