操作後の \(A\) を \(B\) とします。このとき、\(B_i\) は \(0\) か \(A_i\) のどちらかです。

辞書順最小を求める問題なので、前から順番に見ていき各要素を \(0\) にすることができるか判定していきます。

\(f_i\) を \(A_i\) を含む区間に対して行った操作回数とします（ただし \(f_0=0\)）。

\(i-1\) 番目の要素まで決まり、\(i\) 番目の要素を決めることを考えます。

\(A_{i-1}\) を \(B_{i-1}\) にするために \(f_{i-1}\) 回の操作を行ったため、これらの区間を \(i\) まで伸ばすことで \(A_i\) の値は \(X=(A_i+f_{i-1}) \bmod M\) になります。\(A_{i-1}\) から \(A_i\) に伸びる区間を \(X\) 個削ることで \(X\) の値を \(0\) にすることができますが、\(f_i \geq 0\) という制約からこれが不可能な場合があります。その場合は今まで区間を削って \(B_i=0\) としていた場所を区間を増やすことで \(B_i=0\) とするようにすれば良いです。これは各場所に対し何回追加の操作を行うことで \(B_i=0\) にできるか求め、それらを優先度付きキューでコストの昇順に保持しておけば良いです。もしどのようにしても操作回数が \(K\) 回を超えてしまう場合は \(B_i=0\) とすることは不可能なので、\(B_i=A_i\) となります。その場合 \(A_i\) を跨いだ操作は不可能なので、\(f_i=0\) として優先度付きキューをリセットする必要があります。

以上を適切に実装することでこの問題に正答することができます。計算量は \(O(N\log N)\) です。

実装例(Python3)

import sys
import heapq

input = sys.stdin.readline
for _ in range(int(input())):
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))
    f = 0
    q = []
    ans = [0] * N
    for i, a in enumerate(A):
        d = (f + a) % M
        f -= d
        heapq.heappush(q, M - d)
        if f < 0:
            if q[0] <= K:
                K -= heapq.heappop(q)
                f += M
            else:
                f = 0
                q.clear()
                ans[i] = a
    print(*ans)