#1167729 (PyPy3) No.3588 Already Ready

• 問題: No.3588 Already Ready
• ユーザー: marc2825
• 提出日時: 2026-05-30 09:26:05
• 言語: PyPy3 (7.3.17)
• 結果: WA
• 実行時間: -
• コード長: 6,216 bytes
• コンパイル時間: 237 ms
• コンパイル使用メモリ: 96,236 KB
• 実行使用メモリ: 141,824 KB
• 最終ジャッジ日時: 2026-07-10 20:58:06
• 合計ジャッジ時間: 16,690 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

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

ソースコード

import sys

INF = 10**18

class SegMinAdd:
    def __init__(self, arr):
        self.n = len(arr)
        self.n0 = 1
        while self.n0 < self.n:
            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):
        if l >= r:
            return
        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 range_min(self, l, r):
        if l >= r:
            return INF
        return self._range_min(l, r, 1, 0, self.n0)

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

    def first_le_from(self, l, x):
        return self._first_le_from(l, x, 1, 0, self.n0)

    def _first_le_from(self, l, x, k, nl, nr):
        if nr <= l or self.mn[k] > x:
            return None
        if k >= self.n0:
            if nl >= self.n:
                return None
            return nl
        self._push(k)
        mid = (nl + nr) >> 1
        res = self._first_le_from(l, x, k << 1, nl, mid)
        if res is not None:
            return res
        return self._first_le_from(l, x, k << 1 | 1, mid, nr)


class SegMinPoint:
    def __init__(self, arr):
        self.n = len(arr)
        self.n0 = 1
        while self.n0 < self.n:
            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 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:
            mid = (l + r) >> 1
            if self.mn[k << 1] <= x:
                k = k << 1
                r = mid
            else:
                k = k << 1 | 1
                l = mid
        if l >= self.n:
            return None
        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

    # 最後の試合開始直前に M が ready である必要がある
    if A[M] - 2 < K:
        return None

    # 最後の M の 1 勝を除く
    rem = w[:]
    rem[M] -= 1

    L = T - 1
    if sum(rem) != L:
        return None

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

    # チーム i が前半で c 回勝つなら、
    # 1回目の締切 K, 2回目の締切 K-1, ..., c回目の締切 K-c+1
    # よって残り締切の集合は [K-c+1, K]
    diff = [0] * (K + 3)
    deadline = [INF] * N

    for i, c in enumerate(rem):
        if c == 0:
            continue
        if c > K:
            return None

        l = K - c + 1
        r = K

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

    # F(q) = q - count(deadline <= q)
    # 時刻 t で、q >= t について F(q) >= t-1 が必要
    arr = []
    cur_exact = 0
    pref = 0
    for q in range(1, K + 1):
        cur_exact += diff[q]
        pref += cur_exact
        arr.append(q - pref)

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

    ans = []

    for t in range(1, L + 1):
        # 締切が現在時刻より前の勝利が残っていたら不可能
        if seg_team.all_min() < t:
            return None

        # 現在の残り勝利集合が実行可能か
        if seg_cond.range_min(t - 1, K) < t - 1:
            return None

        # F(q) == t-1 となる最初の q がある場合、
        # 締切が q より後の勝利を今選ぶと破綻する
        if seg_cond.range_min(t - 1, K) == t - 1:
            pos = seg_cond.first_le_from(t - 1, t - 1)
            limit = pos + 1
        else:
            limit = K

        # 辞書順最小にしたいので、選べる最小番号を取る
        i = seg_team.first_le(limit)
        if i is None:
            return None

        d = deadline[i]
        if not (t <= d <= limit):
            return None

        ans.append(i + 1)

        # 締切 d の勝利を1つ消費
        # count(deadline <= q) が q >= d で1減るので、
        # F(q) は q >= d で1増える
        seg_cond.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()