#1167728 (PyPy3) No.3588 Already Ready

• 問題: No.3588 Already Ready
• ユーザー: marc2825
• 提出日時: 2026-05-30 09:24:17
• 言語: PyPy3 (7.3.17)
• 結果: WA
• 実行時間: -
• コード長: 5,509 bytes
• コンパイル時間: 228 ms
• コンパイル使用メモリ: 96,096 KB
• 実行使用メモリ: 143,488 KB
• 最終ジャッジ日時: 2026-07-10 20:57:51
• 合計ジャッジ時間: 8,267 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 1 WA * 2
other	AC * 36 WA * 33

ソースコード

import sys

INF = 10**18

class SegMinAdd:
    def __init__(self, arr):
        self.n0 = 1
        while self.n0 < len(arr):
            self.n0 <<= 1
        self.mn = [INF] * (2 * self.n0)
        self.lazy = [0] * (2 * self.n0)

        for i, x in enumerate(arr):
            self.mn[self.n0 + i] = x
        for i in range(self.n0 - 1, 0, -1):
            self.mn[i] = min(self.mn[i << 1], self.mn[i << 1 | 1])

    def _apply(self, k, x):
        self.mn[k] += x
        self.lazy[k] += x

    def _push(self, k):
        if self.lazy[k]:
            z = self.lazy[k]
            self._apply(k << 1, z)
            self._apply(k << 1 | 1, z)
            self.lazy[k] = 0

    def range_add(self, l, r, x):
        self._range_add(l, r, x, 1, 0, self.n0)

    def _range_add(self, l, r, x, k, nl, nr):
        if r <= nl or nr <= l:
            return
        if l <= nl and nr <= r:
            self._apply(k, x)
            return
        self._push(k)
        mid = (nl + nr) >> 1
        self._range_add(l, r, x, k << 1, nl, mid)
        self._range_add(l, r, x, k << 1 | 1, mid, nr)
        self.mn[k] = min(self.mn[k << 1], self.mn[k << 1 | 1])

    def all_min(self):
        return self.mn[1]

    def first_le(self, x):
        if self.mn[1] > x:
            return None
        k = 1
        l = 0
        r = self.n0
        while k < self.n0:
            self._push(k)
            mid = (l + r) >> 1
            if self.mn[k << 1] <= x:
                k = k << 1
                r = mid
            else:
                k = k << 1 | 1
                l = mid
        return l


class SegMinPoint:
    def __init__(self, arr):
        self.n0 = 1
        while self.n0 < len(arr):
            self.n0 <<= 1
        self.mn = [INF] * (2 * self.n0)

        for i, x in enumerate(arr):
            self.mn[self.n0 + i] = x
        for i in range(self.n0 - 1, 0, -1):
            self.mn[i] = min(self.mn[i << 1], self.mn[i << 1 | 1])

    def set(self, i, x):
        i += self.n0
        self.mn[i] = x
        i >>= 1
        while i:
            self.mn[i] = min(self.mn[i << 1], self.mn[i << 1 | 1])
            i >>= 1

    def first_le(self, x):
        if self.mn[1] > x:
            return None
        k = 1
        l = 0
        r = self.n0
        while k < self.n0:
            mid = (l + r) >> 1
            if self.mn[k << 1] <= x:
                k = k << 1
                r = mid
            else:
                k = k << 1 | 1
                l = mid
        return l


def construct(N, K, M, A):
    M -= 1

    total = sum(A)
    if total % (N + 1) != 0:
        return None

    T = total // (N + 1)
    if T <= 0:
        return None

    w = [a - T for a in A]
    if any(x < 0 for x in w):
        return None
    if sum(w) != T:
        return None

    if w[M] <= 0:
        return None

    if A[M] - 2 < K:
        return None

    # 最後の M の 1 勝を除いた、前半 T-1 試合での勝利回数
    rem = w[:]
    rem[M] -= 1

    L = T - 1

    if sum(rem) != L:
        return None

    if L == 0:
        return [M + 1]

    # 各チームについて、残り c 回勝つ必要があるとき、
    # その勝利たちの締切は
    # K - 2c + 2, K - 2c + 3, ..., K - c + 1
    #
    # 締切が 1 未満なら不可能
    diff = [0] * (K + 3)

    deadline = [INF] * N

    for i in range(N):
        c = rem[i]
        if c == 0:
            continue

        l = K - 2 * c + 2
        r = K - c + 1

        if l < 1:
            return None
        if r > K:
            return None

        diff[l] += 1
        diff[r + 1] -= 1
        deadline[i] = l

    # B[q] = q - 「締切 <= q の残り勝利数」
    # 常に B[q] >= 現在時刻-1 である必要がある
    count_exact = [0] * (K + 1)
    cur = 0
    for q in range(1, K + 1):
        cur += diff[q]
        count_exact[q] = cur

    arr = []
    pref = 0
    for q in range(1, K + 1):
        pref += count_exact[q]
        arr.append(q - pref)

    seg_deadline_condition = SegMinAdd(arr)
    seg_team = SegMinPoint(deadline)

    if seg_deadline_condition.all_min() < 0:
        return None

    ans = []

    for t in range(1, L + 1):
        # 現在の状態が実行可能か
        if seg_deadline_condition.all_min() < t - 1:
            return None

        # B[q] == t-1 となる最初の q があるなら、
        # 締切がそれより後の勝利を今選ぶと破綻する
        if seg_deadline_condition.all_min() == t - 1:
            limit = seg_deadline_condition.first_le(t - 1) + 1
        else:
            limit = K + 1

        i = seg_team.first_le(limit)
        if i is None or i >= N:
            return None

        d = deadline[i]
        if d < t or d > limit:
            return None

        ans.append(i + 1)

        # 締切 d の勝利を 1 つ消費する
        # count(deadline <= q) が q >= d で 1 減るので、
        # B[q] は q >= d で +1 される
        seg_deadline_condition.range_add(d - 1, K, 1)

        rem[i] -= 1
        if rem[i] == 0:
            deadline[i] = INF
        else:
            deadline[i] = d + 1

        seg_team.set(i, deadline[i])

    ans.append(M + 1)

    return ans


def solve():
    input = sys.stdin.readline

    N, K = map(int, input().split())
    M = int(input())
    A = list(map(int, input().split()))

    ans = construct(N, K, M, A)

    if ans is None:
        print(-1)
    else:
        print(len(ans))
        print(*ans)

if __name__ == "__main__":
    solve()