Problem p03343 (python)

Fixed submission:
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A) # A をソート
L = [[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)] # BからX-Yの最小パターンを出す
sL = sorted(L,key=lambda x:x[1]) # Lをソート

if Q == 1:
    # 一つしか選ばない -> max == min -> 0
    print(0)
    exit()

if Q == N - K + 1:
    # 全部の要素が選ばれる = 必ず最小値が選ばれる
    print(L[0][1])
    exit()

if K == 1:
    # 一つずつ選べる -> 必ず最小のパターンに出来る
    print(sL[0][1])
    exit()

if sL[0][0] == 0:
    # minが最小の時 最小のパターンになる時
    print(sL[0][1])
    exit()

if sL[0][1] == sL[len(sL)-1][1]:
    print(sL[0][1])
    exit()

now_max_value = -1
now_min_value = -1
now_min_XY = int(1e10)

for key,value in sL:
    max_value = B[key + Q - 1]
    min_value = B[key]
    C = [(i if i >= min_value else None) for i in A]
    i = 0
    j = 0
    count = 0
    min_OK = max_OK = False
    while i < N:
        if not C[i]:
            i += 1
            continue
        j = i + 1
        while j < N:
            if not C[j]:
                break
            j += 1
        tmp = (j-i) - K + 1
        if  tmp < 1:
            # 要素を取得できないパターン
            #if min(C[i:j]) < max_value:
            #    count = 0
            #    break
            i = j + 1
            continue
        sC = sorted(C[i:j])
        if not min_OK and (sC[0] == min_value):
            min_OK = True
        if not max_OK and max_value in sC[0:tmp]:
            max_OK = True
        #if sC[tmp] < max_value:
        #    count = 0
        #    break
        count += tmp - len([i for i in sC[:tmp] if i > max_value])
        i = j +1
    if min_OK and max_OK and (count >= Q):
        print(value)
        exit()
    now_min_XY = min(now_min_XY,now_max_value - now_min_value)
    now_max_value = -1
    now_min_value = -1

print(L[0][1])

Buggy submission (verdict: Runtime Error):
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A)
L = [[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)]
sL = sorted(L,key=lambda x:x[1])


#m_key = max(sL,key=lambda x:x[0])[0]
for key,value in sL:
    #if key >= m_key + K:
    #    continue
    f = False
    C = [(i if i >= B[key] else None) for i in A]
    i = 0
    j = 0
    max_value = B[key + Q - 1]
    length = 0
    over_length = 0
    while i < N:
        if not C[i]:
            i += 1
            continue
        j = i + 1
        while j < N:
            if not C[j]:
                break
            j += 1
        tmp = (j-i) - K + 1
        if  tmp <= 0:
            i = j + 1
            continue
        sC = sorted(C[i:j])
        if sC[tmp] < max_value:
            length = 0
            break
        over_length = len([i for i in sC[:tmp]if i > max_value])
        length += tmp
        i = j +1
    if length - over_length >= Q:
        f = True
            
    if f:
        print(value)
        exit()
    #m_key = min(m_key,key)

print(L[0][1])

Buggy submission (verdict: Runtime Error):
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A)
L = [[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)]
sL = sorted(L,key=lambda x:x[1])

if Q == 1:
    # 一つしか選ばない -> max == min -> 0
    print(0)
    exit()
if Q == N - K + 1:
    print(L[0][1])
    exit()
if K == 1:
    # 一つずつ選べる -> 必ず最小のパターンに出来る
    print(sL[0][1])
    exit()

a = A[N-K-Q+1:K+Q-1]
# 必ず選ばないといけない要素
if a:
    m_index = B.index(min(a))
    if m_index == 0:
        # 必ず最小値が含まれるなら
        print(L[0][1])
        exit()
    sL = [i for i in sL if i[0] <= m_index]
    # 最小値の幅が狭まるためsLを更新

if sL[0][0] == 0:
    # minが最小の時 最小のパターンになる時
    print(sL[0][1])
    exit()

if sL[0][1] == sL[len(sL)-1][1]:
    print(sL[0][1])
    exit()

m_key = max(sL,key=lambda x:x[0])
for key,value in sL:
    if key >= m_key + K:
        continue
    f = True
    for b_key in range(key,key+Q):
        b_value = B[b_key]
        a_indeces = [i for i, x in enumerate(A) if x == b_value]
        success_count = min(len(a_indeces),key + Q - b_key)
        count = 0

        for a_index in a_indeces:
            length = 1
            tmp_length = 1
            for j in range(a_index-1,-1,-1):
                if j < 0:
                    break 
                if A[j] < B[key]:
                    break
                if B[key] <= A[j] <= b_value:
                    continue
                tmp_length += 1
                if tmp_length >= K:
                    break
            tmp_length -= 1
            for j in range(a_index+1,N):
                if j > N-1:
                    break 
                if A[j] < B[key]:
                    break
                if B[key] <= A[j] < b_value:
                    continue
                length += 1
                if length >= K:
                    break
            length += tmp_length
            if length >= K:
                count += 1
        if count < success_count:
            f = False
            break
        
    if f:
        print(value)
        exit()
    m_key = min(m_key,key)
    

print(L[0][1])

Buggy submission (verdict: Runtime Error):
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A)
L = [[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)]
sL = sorted(L,key=lambda x:x[1])

if Q == 1:
    # 一つしか選ばない -> max == min -> 0
    print(0)
    exit()
if Q == N - K + 1:
    print(L[0][1])
    exit()
if K == 1:
    # 一つずつ選べる -> 必ず最小のパターンに出来る
    print(sL[0][1])
    exit()

if sL[0][0] == 0:
    # minが最小の時 最小のパターンになる時
    print(sL[0][1])
    exit()

a = A[N-K-Q+1:K+Q-1]
# 必ず選ばないといけない要素
if a:
    m_index = B.index(min(a))
    if m_index == 0:
        # 必ず最小値が含まれるなら
        print(L[0][1])
        exit()
    sL = [i for i in sL if i[0] <= m_index]
    # 最小値の幅が狭まるためsLを更新
for key,value in sL:
    f = True
    for b_value in B[key:key+Q]:
        a_index = a.index(b_value)
        length = 1
        for j in range(a_index-1,a_index-K,-1):
            if j < 0:
                break 
            if A[j] < b_value:
                break
            length += 1
        for j in range(a_index+1,a_index+K):
            if j > N-1:
                break 
            if A[j] < b_value:
                break
            length += 1
        if length < K:
            f = False
            break
        
    if f:
        print(value)
        exit()

print(L[0][1])

Buggy submission (verdict: Runtime Error):
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A)
L = [[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)]
sL = sorted(L,key=lambda x:x[1])

if Q == 1:
    print(0)
    exit()
if Q == N - K + 1:
    print(L[0][1])
    exit()
if K == 1:
    print(sL[0][1])
    exit()

if sL[0][0] == 0:
    print(sL[0][1])
    exit()

a = A[N-K-Q+1:K+Q-1]
if a:
    m_index = B.index(min(a))
    if m_index == 0:
        print(L[0][1])
        exit()
    sL = [i for i in sL if i[0] <= m_index]
for key,value in sL:
    f = True
    for b_value in B[key:key+Q]:
        a_index = a.index(b_value)
        length = 1
        for j in range(a_index-1,a_index-K,-1):
            if j < 0:
                break 
            if A[j] < b_value:
                break
            length += 1
        for j in range(a_index+1,a_index+K):
            if j > N-1:
                break 
            if A[j] < b_value:
                break
            length += 1
        if length < K:
            f = False
            break
        
    if f:
        print(value)
        exit()

print(L[0][1])