#1171038 (PyPy3) No.3588 Already Ready

• 問題: No.3588 Already Ready
• ユーザー: kidodesu
• 提出日時: 2026-07-10 23:10:11
• 言語: PyPy3 (7.3.17)
• 結果: WA
• 実行時間: -
• コード長: 3,259 bytes
• コンパイル時間: 890 ms
• コンパイル使用メモリ: 95,468 KB
• 実行使用メモリ: 157,240 KB
• 最終ジャッジ日時: 2026-07-10 23:10:39
• 合計ジャッジ時間: 11,116 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 49 WA * 20

ソースコード

def main():
    n, k = list(map(int, input().split()))
    last = int(input())-1
    A = list(map(lambda x: int(x)-1, input().split()))
    A[last] -= 1
    if A[last] < k: return []
    if min(A) < 0: return []
    ma = sum(A)
    N = n+1
    if ma % N: return []
    cnt = ma // N
    for i in range(n):
        A[i] -= cnt
        if A[i] < 0: return []
    sa = max(A)
    E = [[] for _ in range(sa+1)]
    LR = [[-1, -1] for _ in range(n)]
    for i in range(n):
        if not A[i]: continue
        E[A[i]].append(i)
    F = []
    for a in range(sa, 0, -1):
        for now in E[a]:
            LR[now][0] = len(F)
            for _ in range(a):
                F.append(now)
            LR[now][1] = len(F)
    nk = k
    B = [0] * n
    V = []
    for i in range(cnt):
        nk -= 1
        if B[F[i]] > nk: return []
        V.append(nk-B[F[i]])
        B[F[i]] += 1
    def op(a, b):
        return min(a, b)
    def mapp(a, b):
        return a+b
    def comp(a, b):
        return a+b


    INF = 2**31-1
    N = cnt
    LV = (N-1).bit_length()
    N0 = 2**LV
    data = [0]*(2*N0)
    for i in range(cnt):
        data[i] = V[i]
    lazy = [0]*(2*N0)
    
    def gindex(l, r):
        L = (l + N0) >> 1; R = (r + N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1; R >>= 1
    
    # 遅延伝搬処理
    def propagates(*ids):
        for i in reversed(ids):
            v = lazy[i-1]
            if not v:
                continue
            lazy[2*i-1] += v; lazy[2*i] += v
            data[2*i-1] += v; data[2*i] += v
            lazy[i-1] = 0
    
    # 区間[l, r)にxを加算
    def update(l, r, x):
        *ids, = gindex(l, r)
        propagates(*ids)
    
        L = N0 + l; R = N0 + r
        while L < R:
            if R & 1:
                R -= 1
                lazy[R-1] += x; data[R-1] += x
            if L & 1:
                lazy[L-1] += x; data[L-1] += x
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            data[i-1] = min(data[2*i-1], data[2*i])
    
    # 区間[l, r)内の最小値を求める
    def query(l, r):
        propagates(*gindex(l, r))
        L = N0 + l; R = N0 + r
    
        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, data[R-1])
            if L & 1:
                s = min(s, data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

    Ans = []
    NG = [1] * cnt
    for now in range(n):
        l, r = LR[now]
        for m in range(l, r):
            if query(0, m) == 0:
                break
            Ans.append(now)
            update(0, m, -1)
            update(m, m+1, 1<<60)
            NG[m] = 0
    for i in range(cnt):
        if NG[i]:
            Ans.append(F[i])
    Ans.append(last)
    X = [0] * n
    nk = k
    for i in range(cnt-1):
        now = F[i]
        if nk <= X[now]: assert 0
        X[now] += 1
        nk -= 1
    return [ans+1 for ans in Ans]

Ans = main()
if Ans:
    print(len(Ans))
    print(*Ans)
else:
    print(-1)