結果

問題 No.3588 Already Ready
コンテスト
ユーザー marc2825
提出日時 2026-05-28 13:21:32
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,524 ms / 3,000 ms
コード長 5,515 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 231 ms
コンパイル使用メモリ 95,912 KB
実行使用メモリ 148,832 KB
最終ジャッジ日時 2026-07-10 20:54:26
合計ジャッジ時間 13,523 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 69
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

# 再帰上限の引き上げ（セグメント木用）
sys.setrecursionlimit(2000000)

def solve():
    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)
    if total_A % (N + 1) != 0:
        print(-1)
        return
    
    T = total_A // (N + 1)
    if T == 0:
        print(-1)
        return
        
    W = [0] * (N + 1)
    for i in range(1, N + 1):
        W[i] = A[i-1] - T
        if W[i] < 0:
            print(-1)
            return
            
    if W[M] == 0 or A[M-1] < K + 2:
        print(-1)
        return
        
    C = [0] * (N + 1)
    U = [0] * (N + 1)
    for i in range(1, N + 1):
        if i != M:
            C[i] = W[i]
            U[i] = K - W[i]
        else:
            C[i] = W[i] - 1
            U[i] = K - W[i] + 1
            
        if C[i] > 0 and U[i] < 0:
            print(-1)
            return
            
        U[i] = min(U[i], T - 2)
        
    if T == 1:
        # T=1 の場合、上記の A[M-1] < K + 2 の判定で既にはじかれているはずですが念のため
        print(-1)
        return

    MAX_T = T - 1
    count_U = [0] * MAX_T
    for i in range(1, N + 1):
        if C[i] > 0:
            count_U[U[i]] += C[i]
            
    S = [0] * MAX_T
    curr_S = 0
    for x in range(MAX_T):
        curr_S += count_U[x]
        S[x] = curr_S
        
    V = [0] * MAX_T
    for x in range(MAX_T):
        V[x] = x - S[x]
        if V[x] < -1:
            print(-1)
            return

    # V用 セグメント木の配列と関数
    v_tree = [0] * (4 * MAX_T)
    v_lazy = [0] * (4 * MAX_T)

    def build_v(node, start, end):
        if start == end:
            v_tree[node] = V[start]
            return
        mid = (start + end) // 2
        build_v(2 * node, start, mid)
        build_v(2 * node + 1, mid + 1, end)
        v_tree[node] = min(v_tree[2 * node], v_tree[2 * node + 1])

    def add_v(node, start, end, l, r, val):
        if r < start or end < l:
            return
        if l <= start and end <= r:
            v_tree[node] += val
            v_lazy[node] += val
            return
        lz = v_lazy[node]
        if lz != 0:
            v_tree[2 * node] += lz
            v_lazy[2 * node] += lz
            v_tree[2 * node + 1] += lz
            v_lazy[2 * node + 1] += lz
            v_lazy[node] = 0
        mid = (start + end) // 2
        add_v(2 * node, start, mid, l, r, val)
        add_v(2 * node + 1, mid + 1, end, l, r, val)
        v_tree[node] = min(v_tree[2 * node], v_tree[2 * node + 1])

    def find_first_v(node, start, end, t, target):
        if v_tree[node] > target or end < t:
            return -1
        if start == end:
            return start
        lz = v_lazy[node]
        if lz != 0:
            v_tree[2 * node] += lz
            v_lazy[2 * node] += lz
            v_tree[2 * node + 1] += lz
            v_lazy[2 * node + 1] += lz
            v_lazy[node] = 0
        mid = (start + end) // 2
        res = find_first_v(2 * node, start, mid, t, target)
        if res != -1:
            return res
        return find_first_v(2 * node + 1, mid + 1, end, t, target)

    # チーム探索用 セグメント木の配列と関数
    MAX_N = N
    INF = 10**9
    team_tree = [INF] * (4 * (MAX_N + 1))

    def build_team(node, start, end):
        if start == end:
            team_tree[node] = U[start] if C[start] > 0 else INF
            return
        mid = (start + end) // 2
        build_team(2 * node, start, mid)
        build_team(2 * node + 1, mid + 1, end)
        team_tree[node] = min(team_tree[2 * node], team_tree[2 * node + 1])

    def update_team(node, start, end, idx, val):
        if start == end:
            team_tree[node] = val
            return
        mid = (start + end) // 2
        if idx <= mid:
            update_team(2 * node, start, mid, idx, val)
        else:
            update_team(2 * node + 1, mid + 1, end, idx, val)
        team_tree[node] = min(team_tree[2 * node], team_tree[2 * node + 1])

    def find_first_team(node, start, end, X):
        if team_tree[node] > X:
            return -1
        if start == end:
            return start
        mid = (start + end) // 2
        res = find_first_team(2 * node, start, mid, X)
        if res != -1:
            return res
        return find_first_team(2 * node + 1, mid + 1, end, X)

    # 初期化
    build_v(1, 0, MAX_T - 1)
    build_team(1, 0, MAX_N)

    ans = []
    # 各試合（最後の試合を除く）の勝者を貪欲に決定
    for t in range(MAX_T):
        X = find_first_v(1, 0, MAX_T - 1, t, t - 1)
        if X == -1:
            print(-1)
            return
            
        best_team = find_first_team(1, 0, MAX_N, X)
        if best_team == -1:
            print(-1)
            return
            
        ans.append(best_team)
        C[best_team] -= 1
        
        # 必要な勝利数を満たしたチームは除外
        if C[best_team] == 0:
            update_team(1, 0, MAX_N, best_team, INF)
            
        # V配列の更新（使ったチームのデッドライン以降の余裕度が回復する）
        add_v(1, 0, MAX_T - 1, U[best_team], MAX_T - 1, 1)

    # 最後の試合は必ずMが勝利する
    ans.append(M)
    
    print(T)
    print(" ".join(map(str, ans)))

if __name__ == '__main__':
    solve()
0