Problem p02616 (python)

Fixed submission:
import heapq
#import random
# n = random.randint(1, 10)
# k = random.randint(1, n)
# A = [random.randint(-10, 10) for _ in range(n)]
# print(n, k)
# print(A)

n, k = map(int, input().split())
A = list(map(int, input().split()))

MOD = 10**9+7

# n=kのとき、積の最大値は負になる可能性がある
if n == k:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(a)

# Aの要素全て負かつkが奇数の時、積の最大値は必ず負
if len(pos)==0 and k%2==1:
    neg.sort(reverse=True)
    ans = 1
    for a in neg[:k]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

# これより下は積の最大値は必ず正
pos = [-x for x in pos]
heapq.heapify(pos)
heapq.heapify(neg)

L_ans = []
last_pos = None
last_neg = None

ans_is_neg = False

for i in range(k):
    if not neg:
        last_pos = -heapq.heappop(pos)
        L_ans.append(last_pos)
        continue

    if not pos:
        last_neg = heapq.heappop(neg)
        L_ans.append(last_neg)
        ans_is_neg = not ans_is_neg
        continue

    if pos[0]<=neg[0]:
        last_pos = -heapq.heappop(pos)
        L_ans.append(last_pos)
        continue

    if pos[0]>neg[0]:
        last_neg = heapq.heappop(neg)
        L_ans.append(last_neg)
        ans_is_neg = not ans_is_neg
        continue

if ans_is_neg:
    if (last_pos==None) or (not neg):
        L_ans.remove(last_neg)
        L_ans.append(-heapq.heappop(pos))

    elif not pos:
        L_ans.remove(last_pos)
        L_ans.append(heapq.heappop(neg))

    else:
        new_pos = -pos[0]
        new_neg = neg[0]

        if new_pos*last_pos>=new_neg*last_neg:
            L_ans.remove(last_neg)
            L_ans.append(new_pos)
        else:
            L_ans.remove(last_pos)
            L_ans.append(new_neg)

ans = 1
for a in L_ans:
    ans *= a
    ans %= MOD

print(ans)

Buggy submission (verdict: Runtime Error):
import heapq

n, k = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9+7

# n=kのとき、積の最大値は負になる可能性がある
if n == k:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(a)

# Aの要素全て負かつkが奇数の時、積の最大値は必ず負
if len(pos)==0 and k%2==1:
    neg.sort(reverse=True)
    ans = 1
    for a in neg[:k]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

# これより下は積の最大値は必ず正
pos = [-x for x in pos]
heapq.heapify(pos)
heapq.heapify(neg)

L_ans = []
last_pos = None
last_neg = None

ans_is_neg = False

for i in range(k):
    if (not neg) or (pos[0]<=neg[0]):
        last_pos = -heapq.heappop(pos)
        L_ans.append(last_pos)
        continue

    if (not pos) or (pos[0]>neg[0]):
        last_neg = heapq.heappop(neg)
        L_ans.append(last_neg)
        ans_is_neg = not ans_is_neg
        continue

if ans_is_neg:
    if (last_pos==None) or (not neg):
        L_ans.remove(last_neg)
        L_ans.append(-heapq.heappop(pos))

    elif not pos:
        L_ans.remove(last_pos)
        L_ans.append(heapq.heappop(neg))

    else:
        new_pos = -pos[0]
        new_neg = neg[0]

        if new_pos*last_pos>=new_neg*last_neg:
            L_ans.remove(last_neg)
            L_ans.append(new_pos)
        else:
            L_ans.remove(last_pos)
            L_ans.append(new_neg)

ans = 1
for a in L_ans:
    ans *= a
    ans %= MOD

print(ans)

Buggy submission (verdict: Runtime Error):
import heapq

n, k = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9+7

# n=kのとき、積の最大値は負になる可能性がある
if n == k:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(a)

# Aの要素全て負かつkが奇数の時、積の最大値は必ず負
if len(pos)==0 and k%2==1:
    neg.sort(reverse=True)
    ans = 1
    for a in neg[:k]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

# これより下は積の最大値は必ず正
pos = [-x for x in pos]
heapq.heapify(pos)
heapq.heapify(neg)

L_ans = []
last_pos = None
last_neg = None

ans_is_neg = False

for i in range(k):
    if (not neg) or (pos[0]<=neg[0]):
        last_pos = -heapq.heappop(pos)
        L_ans.append(last_pos)
        continue

    if (not pos) or (pos[0]>neg[0]):
        last_neg = heapq.heappop(neg)
        L_ans.append(last_neg)
        ans_is_neg = not ans_is_neg
        continue
print(L_ans)
if ans_is_neg:
    if (last_pos==None) or (not neg):
        L_ans.remove(last_neg)
        L_ans.append(-heapq.heappop(pos))

    elif not pos:
        L_ans.remove(last_pos)
        L_ans.append(heapq.heappop(neg))

    else:
        new_pos = -pos[0]
        new_neg = neg[0]

        if new_pos*last_pos>=new_neg*last_neg:
            L_ans.remove(last_neg)
            L_ans.append(new_pos)
        else:
            L_ans.remove(last_pos)
            L_ans.append(new_neg)

ans = 1
for a in L_ans:
    ans *= a
    ans %= MOD

print(ans)

Buggy submission (verdict: Runtime Error):
import heapq

n, k = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9+7

# n=kのとき、積の最大値は負になる可能性がある
if n == k:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(a)

# Aの要素全て負かつkが奇数の時、積の最大値は必ず負
if len(pos)==0 and k%2==1:
    neg.sort(reverse=True)
    ans = 1
    for a in neg[:k]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

# これより下は積の最大値は必ず正
pos = [-x for x in pos]
heapq.heapify(pos)
heapq.heapify(neg)

L_ans = []
last_pos = None
last_neg = None

ans_is_neg = False

for i in range(k):
    if (not neg) or (pos[0]<=neg[0]):
        last_pos = -heapq.heappop(pos)
        L_ans.append(last_pos)
        continue

    if (not pos) or (pos[0]>neg[0]):
        last_neg = heapq.heappop(neg)
        L_ans.append(last_neg)
        ans_is_neg = not ans_is_neg
        continue

if ans_is_neg:
    if (last_pos==None) or (not neg):
        L_ans.remove(last_neg)
        L_ans.append(-heapq.heappop(pos))

    elif not pos:
        L_ans.remove(last_pos)
        L_ans.append(heapq.heappop(neg))

    else:
        new_pos = pos[0]
        new_neg = neg[0]

        if new_pos*last_pos>=new_pos*last_neg:
            L_ans.remove(last_neg)
            L_ans.append(new_pos)
        else:
            L_ans.remove(last_pos)
            L_ans.append(new_neg)

ans = 1
for a in L_ans:
    ans *= a
    ans %= MOD

print(ans)

Buggy submission (verdict: Runtime Error):
import heapq

n, k = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9+7

# n=kのとき、積の最大値は負になる可能性がある
if n == k:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(a)

# Aの要素全て負かつkが奇数の時、積の最大値は必ず負
if len(pos)==0 and k%2==1:
    neg.sort(reverse=True)
    ans = 1
    for a in neg[:k]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

# これより下は積の最大値は必ず正
pos = [-x for x in pos]
heapq.heapify(pos)
heapq.heapify(neg)

L_ans = []
last_pos = None
last_neg = None

ans_is_neg = False

for i in range(k):
    if (not neg) or (pos[0]<=neg[0]):
        last_pos = -heapq.heappop(pos)
        L_ans.append(last_pos)
        continue

    if (not pos) or (pos[0]>neg[0]):
        last_neg = heapq.heappop(neg)
        L_ans.append(last_neg)
        ans_is_neg = not ans_is_neg
        continue

if ans_is_neg:
    if (last_pos==None) or (not neg):
        L_ans.pop(last_neg)
        L_ans.append(-heapq.heappop(pos))

    elif not pos:
        L_ans.pop(last_pos)
        L_ans.append(heapq.heappop(neg))

    else:
        new_pos = pos[0]
        new_neg = neg[0]

        if new_pos*last_pos>=new_pos*last_neg:
            L_ans.pop(last_neg)
            L_ans.append(new_pos)
        else:
            L_ans.pop(last_pos)
            L_ans.append(new_neg)

ans = 1
for a in L_ans:
    ans *= a
    ans %= MOD

print(ans)

Buggy submission (verdict: Runtime Error):
import heapq

n, k = map(int, input().split())
A = list(map(int, input().split()))

MOD = 10**9+7

A_pos = []
A_neg = []
for a in A:
    if a >= 0:
        A_pos.append(-a)
    else:
        A_neg.append(a)

# 積が負にしかならない
if len(A_pos) == 0 and k%2==1:
    A_neg.sort(reverse=True)
    ans = 1
    for a in A_neg[:k]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

A_pos2 = [-A_pos[i*2]*A_neg[i*2+1] for i in range(len(A_pos)//2)]
A_neg2 = [-A_neg[i*2]*A_neg[i*2+1] for i in range(len(A_neg)//2)]

heapq.heapify(A_pos2)  # 絶対値が大きいものが先頭
heapq.heapify(A_neg2)  # 絶対値が大きいものが先頭

if k%2==0:
    ans = 1
    for i in range(k//2):
        if not A_pos2:
            ans *= -heapq.heappop(A_neg2)
            ans %= MOD
        elif not A_neg2:
            ans *= -heapq.heappop(A_pos2)
            ans %= MOD
        else:
            if A_pos[0] <= A_neg[0]:
                ans *= -heapq.heappop(A_pos2)
                ans %= MOD
            else:
                ans *= -heapq.heappop(A_neg2)
                ans %= MOD
    print(ans)
    exit()

if False:
    ans = 1
    cnt = 0
    for i in range(k // 2 - 1):
        if not A_pos2:
            ans *= -heapq.heappop(A_neg2)
            ans %= MOD
        elif not A_neg2:
            ans *= -heapq.heappop(A_pos2)
            ans %= MOD
            cnt += 1
        else:
            if A_pos[0] <= A_neg[0]:
                ans *= -heapq.heappop(A_pos2)
                ans %= MOD
                cnt += 1
            else:
                ans *= -heapq.heappop(A_neg2)
                ans %= MOD
    # if cnt*2+1 == len(A_pos):

else:
    ans = 1
    cnt = 0
    for i in range(k // 2):
        if not A_pos2:
            ans *= -heapq.heappop(A_neg2)
            ans %= MOD
        elif not A_neg2:
            ans *= -heapq.heappop(A_pos2)
            ans %= MOD
            cnt += 1
        else:
            if A_pos[0] <= A_neg[0]:
                ans *= -heapq.heappop(A_pos2)
                ans %= MOD
                cnt += 1
            else:
                ans *= -heapq.heappop(A_neg2)
                ans %= MOD
    A_pos.sort(reverse=True)
    ans *= A_pos[cnt*2]
    ans %= MOD
    print(ans)

Buggy submission (verdict: Runtime Error):
import heapq

n, k = map(int, input().split())
A = list(map(int, input().split()))

MOD = 10**9+7

A_pos = []
A_neg = []
for a in A:
    if a >= 0:
        A_pos.append(-a)
    else:
        A_neg.append(a)

# 積が負にしかならない
if len(A_pos) == 0 and k%2==1:
    A_neg.sort(reverse=True)
    ans = 1
    for a in A_neg[:k]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

A_pos2 = [-A_pos[i*2]*A_neg[i*2+1] for i in range(len(A_pos)//2)]
A_neg2 = [-A_neg[i*2]*A_neg[i*2+1] for i in range(len(A_neg)//2)]

heapq.heapify(A_pos2)  # 絶対値が大きいものが先頭
heapq.heapify(A_neg2)  # 絶対値が大きいものが先頭

if k%2==0:
    ans = 1
    for i in range(k//2):
        if not A_pos2:
            ans *= -heapq.heappop(A_neg2)
            ans %= MOD
        elif not A_neg2:
            ans *= -heapq.heappop(A_pos2)
            ans %= MOD
        else:
            if A_pos[0] <= A_neg[0]:
                ans *= -heapq.heappop(A_pos2)
                ans %= MOD
            else:
                ans *= -heapq.heappop(A_neg2)
                ans %= MOD
    print(ans)
    exit()

if False:
    ans = 1
    cnt = 0
    for i in range(k // 2 - 1):
        if not A_pos2:
            ans *= -heapq.heappop(A_neg2)
            ans %= MOD
        elif not A_neg2:
            ans *= -heapq.heappop(A_pos2)
            ans %= MOD
            cnt += 1
        else:
            if A_pos[0] <= A_neg[0]:
                ans *= -heapq.heappop(A_pos2)
                ans %= MOD
                cnt += 1
            else:
                ans *= -heapq.heappop(A_neg2)
                ans %= MOD
    # if cnt*2+1 == len(A_pos):

else:
    ans = 1
    cnt = 0
    for i in range(k // 2):
        if not A_pos2:
            ans *= -heapq.heappop(A_neg2)
            ans %= MOD
        elif not A_neg2:
            ans *= -heapq.heappop(A_pos2)
            ans %= MOD
            cnt += 1
        else:
            if A_pos[0] <= A_neg[0]:
                ans *= -heapq.heappop(A_pos2)
                ans %= MOD
                cnt += 1
            else:
                ans *= -heapq.heappop(A_neg2)
                ans %= MOD
    A_pos.sort(reverse=True)
    ans *= A_pos[cnt*2]
    ans %= MOD
    print(ans)

Buggy submission (verdict: Runtime Error):
import heapq

n, k = map(int, input().split())
A = list(map(int, input().split()))

MOD = 10**9+7

A_pos = []
A_neg = []
for a in A:
    if a >= 0:
        A_pos.append(-a)
    else:
        A_neg.append(a)

# 積が負にしかならない
if len(A_pos) == 0 and k%2==1:
    A_neg.sort(reverse=True)
    ans = 1
    for a in A_neg[:k]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

A_pos2 = [-A_pos[i*2]*A_neg[i*2+1] for i in range(len(A_pos)//2)]
A_neg2 = [-A_neg[i*2]*A_neg[i*2+1] for i in range(len(A_neg)//2)]

heapq.heapify(A_pos2)  # 絶対値が大きいものが先頭
heapq.heapify(A_neg2)  # 絶対値が大きいものが先頭

if k%2==0:
    ans = 1
    for i in range(k//2):
        if not A_pos2:
            ans *= -heapq.heappop(A_neg2)
            ans %= MOD
        elif not A_neg2:
            ans *= -heapq.heappop(A_pos2)
            ans %= MOD
        else:
            if A_pos[0] <= A_neg[0]:
                ans *= -heapq.heappop(A_pos2)
                ans %= MOD
            else:
                ans *= -heapq.heappop(A_neg2)
                ans %= MOD
    print(ans)
    exit()

if False:
    ans = 1
    cnt = 0
    for i in range(k // 2 - 1):
        if not A_pos2:
            ans *= -heapq.heappop(A_neg2)
            ans %= MOD
        elif not A_neg2:
            ans *= -heapq.heappop(A_pos2)
            ans %= MOD
            cnt += 1
        else:
            if A_pos[0] <= A_neg[0]:
                ans *= -heapq.heappop(A_pos2)
                ans %= MOD
                cnt += 1
            else:
                ans *= -heapq.heappop(A_neg2)
                ans %= MOD
    if cnt*2+1 == len(A_pos):
        
else:
    ans = 1
    cnt = 0
    for i in range(k // 2):
        if not A_pos2:
            ans *= -heapq.heappop(A_neg2)
            ans %= MOD
        elif not A_neg2:
            ans *= -heapq.heappop(A_pos2)
            ans %= MOD
            cnt += 1
        else:
            if A_pos[0] <= A_neg[0]:
                ans *= -heapq.heappop(A_pos2)
                ans %= MOD
                cnt += 1
            else:
                ans *= -heapq.heappop(A_neg2)
                ans %= MOD
    A_pos.sort(reverse=True)
    ans *= A_pos[cnt*2]
    ans %= MOD
    print(ans)