#1167699 (PyPy3) No.3588 Already Ready

• 問題: No.3588 Already Ready
• ユーザー: marc2825
• 提出日時: 2026-05-30 08:34:47
• 言語: PyPy3 (7.3.17)
• 結果: AC
• 実行時間: 1,632 ms / 3,000 ms
• コード長: 6,528 bytes
• コンパイル時間: 239 ms
• コンパイル使用メモリ: 95,724 KB
• 実行使用メモリ: 164,068 KB
• 最終ジャッジ日時: 2026-07-10 21:13:07
• 合計ジャッジ時間: 13,113 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge3_0

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

ソースコード

import sys

# Pythonでの深い再帰の対応
sys.setrecursionlimit(300000)

class LazySegTree:
    """区間加算と区間最小値取得、および条件を満たす最初のインデックス検索をサポートするセグメント木"""
    def __init__(self, data):
        self.n = len(data)
        self.size = 1
        while self.size < self.n:
            self.size *= 2
        self.tree = [float('inf')] * (2 * self.size)
        self.lazy = [0] * (2 * self.size)
        for i in range(self.n):
            self.tree[self.size - 1 + i] = data[i]
        for i in range(self.size - 2, -1, -1):
            self.tree[i] = min(self.tree[2 * i + 1], self.tree[2 * i + 2])

    def _eval(self, k, l, r):
        if self.lazy[k] != 0:
            self.tree[k] += self.lazy[k]
            if r - l > 1:
                self.lazy[2 * k + 1] += self.lazy[k]
                self.lazy[2 * k + 2] += self.lazy[k]
            self.lazy[k] = 0

    def add(self, a, b, x):
        self._add(a, b, x, 0, 0, self.size)

    def _add(self, a, b, x, k, l, r):
        self._eval(k, l, r)
        if a <= l and r <= b:
            self.lazy[k] += x
            self._eval(k, l, r)
        elif a < r and l < b:
            mid = (l + r) // 2
            self._add(a, b, x, 2 * k + 1, l, mid)
            self._add(a, b, x, 2 * k + 2, mid, r)
            self.tree[k] = min(self.tree[2 * k + 1], self.tree[2 * k + 2])

    def find_first(self, a, b, x):
        """区間 [a, b) の中で値が x 以下となる最初のインデックスを返す"""
        return self._find_first(a, b, x, 0, 0, self.size)
        
    def _find_first(self, a, b, x, k, l, r):
        self._eval(k, l, r)
        if b <= l or r <= a or self.tree[k] > x:
            return -1
        if r - l == 1:
            return l
        mid = (l + r) // 2
        res = self._find_first(a, b, x, 2 * k + 1, l, mid)
        if res != -1:
            return res
        return self._find_first(a, b, x, 2 * k + 2, mid, r)

class PointSegTree:
    """点更新と区間最小値取得を非再帰で行うセグメント木 (チーム選択用)"""
    def __init__(self, n):
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.tree = [(float('inf'), -1)] * (2 * self.size)
        
    def update(self, i, val):
        i += self.size - 1
        self.tree[i] = val
        while i > 0:
            i = (i - 1) // 2
            self.tree[i] = min(self.tree[2 * i + 1], self.tree[2 * i + 2])
            
    def get_min(self, a, b):
        res = (float('inf'), -1)
        l = a + self.size - 1
        r = b + self.size - 1
        while l < r:
            if not (l & 1):  # l が親の右側の子
                if self.tree[l][0] < res[0]:
                    res = self.tree[l]
                l += 1
            if not (r & 1):  # r が親の右側の子
                r -= 1
                if self.tree[r][0] < res[0]:
                    res = self.tree[r]
            l = (l - 1) // 2
            r = (r - 1) // 2
        return res

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    K = int(input_data[1])
    M = int(input_data[2])
    A = [int(x) for x in input_data[3:3+N]]
    
    total_A = sum(A)
    # 合計スコアが1試合ごとの加算量(N+1)で割り切れない場合は矛盾
    if total_A % (N + 1) != 0:
        print("-1")
        return
    T = total_A // (N + 1)
    
    if T == 0:
        print("-1")
        return
        
    W = [a - T for a in A]
    for w in W:
        if w < 0:
            print("-1")
            return
            
    # Mチームは最低でも1回(最後の試合)勝ち、最終的にスコアが(K+2)以上でなければならない
    if W[M - 1] < 1 or A[M - 1] < K + 2:
        print("-1")
        return

    # 1試合のみの場合は条件が揃っているかだけですでに確定
    if T == 1:
        print(1)
        print(M)
        return

    V = [0] * N
    D = [0] * N
    for i in range(N):
        if i == M - 1:
            V[i] = W[i] - 1
            D[i] = K - W[i] + 2
        else:
            V[i] = W[i]
            D[i] = K - W[i] + 1
            
        if V[i] > 0 and D[i] <= 0:
            print("-1")
            return

    # 全てのスロットは最大でもT-1までしかスケジュールできない
    D_prime = [0] * N
    for i in range(N):
        if V[i] > 0:
            D_prime[i] = min(T - 1, D[i])

    C = [0] * T
    for i in range(N):
        if V[i] > 0:
            C[D_prime[i]] += V[i]

    # 初期の猶予(E_init)を計算
    E_init = [0] * T
    S_val = 0
    for k in range(1, T):
        S_val += C[k]
        E_init[k] = k - S_val
        # 猶予がマイナスになる場合は最初からスケジュール不能
        if E_init[k] < 0:
            print("-1")
            return

    # チームを期限別に割り当て
    teams = [[] for _ in range(T)]
    for i in range(N):
        if V[i] > 0:
            for _ in range(V[i]):
                teams[D_prime[i]].append(i + 1)

    for d in range(1, T):
        teams[d].sort(reverse=True)

    # チーム探索用のセグメント木初期化
    team_seg = PointSegTree(T)
    for d in range(1, T):
        if teams[d]:
            team_seg.update(d, (teams[d][-1], d))
        else:
            team_seg.update(d, (float('inf'), d))

    e_seg = LazySegTree(E_init)

    ans = []
    # 各スロット t = 1, 2, ..., T-1 について前から順に貪欲に決定
    for t in range(1, T):
        # 条件を破らないギリギリの期限(xcrit)を特定
        xcrit = e_seg.find_first(t, T, t - 1)
        if xcrit == -1:
            xcrit = T - 1
            
        # 猶予の中で辞書順最小のチームを選択
        min_team, d_opt = team_seg.get_min(t, xcrit + 1)
        if min_team == float('inf'):
            print("-1")
            return
            
        ans.append(min_team)
        teams[d_opt].pop()
        
        # 抽出元の期限リストを更新
        if teams[d_opt]:
            team_seg.update(d_opt, (teams[d_opt][-1], d_opt))
        else:
            team_seg.update(d_opt, (float('inf'), d_opt))
            
        # 選択したチームの期限以後の猶予を回復させる
        e_seg.add(d_opt, T, 1)

    # 最後に優勝チームを追加して出力
    ans.append(M)
    print(T)
    print(" ".join(map(str, ans)))

if __name__ == '__main__':
    main()