#1167732 (PyPy3) No.3588 Already Ready

• 問題: No.3588 Already Ready
• ユーザー: marc2825
• 提出日時: 2026-05-30 09:32:58
• 言語: PyPy3 (7.3.17)
• 結果: AC
• 実行時間: 1,395 ms / 3,000 ms
• コード長: 5,911 bytes
• コンパイル時間: 228 ms
• コンパイル使用メモリ: 96,488 KB
• 実行使用メモリ: 144,828 KB
• 最終ジャッジ日時: 2026-07-10 20:58:22
• 合計ジャッジ時間: 13,753 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 69

ソースコード

import sys

INF = 10**18
BIG = 10**30


class RangeMinAddSeg:
    def __init__(self, arr):
        self.n = len(arr) - 1
        self.mn = [INF] * (4 * (self.n + 5))
        self.lazy = [0] * (4 * (self.n + 5))
        self.arr = arr
        self._build(1, 1, self.n)

    def _build(self, node, l, r):
        if l == r:
            self.mn[node] = self.arr[l]
            return
        mid = (l + r) // 2
        self._build(node * 2, l, mid)
        self._build(node * 2 + 1, mid + 1, r)
        self.mn[node] = min(self.mn[node * 2], self.mn[node * 2 + 1])

    def _push(self, node):
        z = self.lazy[node]
        if z:
            for ch in (node * 2, node * 2 + 1):
                self.mn[ch] += z
                self.lazy[ch] += z
            self.lazy[node] = 0

    def range_add(self, ql, qr, x):
        if ql > qr:
            return
        ql = max(ql, 1)
        qr = min(qr, self.n)
        if ql > qr:
            return
        self._range_add(1, 1, self.n, ql, qr, x)

    def _range_add(self, node, l, r, ql, qr, x):
        if qr < l or r < ql:
            return
        if ql <= l and r <= qr:
            self.mn[node] += x
            self.lazy[node] += x
            return

        self._push(node)
        mid = (l + r) // 2
        self._range_add(node * 2, l, mid, ql, qr, x)
        self._range_add(node * 2 + 1, mid + 1, r, ql, qr, x)
        self.mn[node] = min(self.mn[node * 2], self.mn[node * 2 + 1])

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

    def first_zero_from(self, ql):
        if ql > self.n:
            return INF
        return self._first_zero_from(1, 1, self.n, ql)

    def _first_zero_from(self, node, l, r, ql):
        if r < ql or self.mn[node] > 0:
            return INF
        if l == r:
            return l

        self._push(node)
        mid = (l + r) // 2

        res = self._first_zero_from(node * 2, l, mid, ql)
        if res != INF:
            return res
        return self._first_zero_from(node * 2 + 1, mid + 1, r, ql)


class LabelMinSeg:
    def __init__(self, vals):
        self.n = len(vals)
        self.mn = [BIG] * (4 * (self.n + 5))
        self.vals = vals
        self._build(1, 0, self.n - 1)

    def _build(self, node, l, r):
        if l == r:
            self.mn[node] = self.vals[l]
            return
        mid = (l + r) // 2
        self._build(node * 2, l, mid)
        self._build(node * 2 + 1, mid + 1, r)
        self.mn[node] = min(self.mn[node * 2], self.mn[node * 2 + 1])

    def update(self, idx, val):
        self._update(1, 0, self.n - 1, idx, val)

    def _update(self, node, l, r, idx, val):
        if l == r:
            self.mn[node] = val
            return
        mid = (l + r) // 2
        if idx <= mid:
            self._update(node * 2, l, mid, idx, val)
        else:
            self._update(node * 2 + 1, mid + 1, r, idx, val)
        self.mn[node] = min(self.mn[node * 2], self.mn[node * 2 + 1])

    def first_leq(self, x):
        if self.mn[1] > x:
            return -1
        return self._first_leq(1, 0, self.n - 1, x)

    def _first_leq(self, node, l, r, x):
        if l == r:
            return l
        mid = (l + r) // 2
        if self.mn[node * 2] <= x:
            return self._first_leq(node * 2, l, mid, x)
        return self._first_leq(node * 2 + 1, mid + 1, r, x)


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

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

    S = sum(A)

    # sum A_i = (N + 1) * T
    if S % (N + 1) != 0:
        print(-1)
        return

    T = S // (N + 1)

    if T <= 0:
        print(-1)
        return

    if any(a < T for a in A):
        print(-1)
        return

    w = [a - T for a in A]

    if sum(w) != T:
        print(-1)
        return

    # 最後の勝者は M
    if w[M] <= 0:
        print(-1)
        return

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

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

    L = T - 1

    # 前半の試合は、どの勝者も ready であってはいけない
    if L > K:
        print(-1)
        return

    deadline = [BIG] * N
    cnt_deadline = [0] * (K + 1)

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

        # d[i] 回勝つチームは、最後の勝利を K - d[i] + 1 試合目までに終える必要がある
        if d[i] > K:
            print(-1)
            return

        D = K - d[i] + 1

        if D <= 0:
            print(-1)
            return

        deadline[i] = D
        cnt_deadline[D] += d[i]

    # slack[x] = x - 締切 x 以下の残り仕事数
    slack = [0] * (K + 1)
    pref = 0
    for x in range(1, K + 1):
        pref += cnt_deadline[x]
        slack[x] = x - pref

    slack_seg = RangeMinAddSeg(slack)

    if slack_seg.all_min() < 0:
        print(-1)
        return

    label_vals = [deadline[i] if d[i] > 0 else BIG for i in range(N)]
    label_seg = LabelMinSeg(label_vals)

    ans = []

    for p in range(1, L + 1):
        # 最初に slack が 0 になる締切より後のものを選ぶと詰む
        e = slack_seg.first_zero_from(p)

        # slack が 0 になる点がないなら、任意の有効締切でよい
        if e == INF:
            e = K

        idx = label_seg.first_leq(e)

        if idx == -1:
            print(-1)
            return

        D = deadline[idx]

        if D < p:
            print(-1)
            return

        ans.append(idx + 1)

        d[idx] -= 1
        if d[idx] == 0:
            label_seg.update(idx, BIG)

        # D より前の締切については、残りスロットが 1 減る
        slack_seg.range_add(p + 1, D - 1, -1)

    ans.append(M + 1)

    print(T)
    print(*ans)


if __name__ == "__main__":
    solve()