結果

問題 No.3051 Make All Divisible
コンテスト
ユーザー suisen
提出日時 2025-01-18 16:04:35
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 102 ms / 2,000 ms
+ 134µs
コード長 967 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 232 ms
コンパイル使用メモリ 96,364 KB
実行使用メモリ 96,980 KB
最終ジャッジ日時 2026-07-12 10:36:39
合計ジャッジ時間 4,496 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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