Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

We will choose exactly K of these elements. Find the maximum possible product of the chosen elements.

Then, print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Constraints

1 \leq K \leq N \leq 2\times 10^5

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

Print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

The possible products of the two chosen elements are 2, -3, -4, -6, -8, and 12, so the maximum product is 12.

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

The possible products of the three chosen elements are -24, -12, -8, and -6, so the maximum product is -6.

We print this value modulo (10^9+7), that is, 1000000001.

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

The possible products of the one chosen element are -1 and 1000000000, so the maximum product is 1000000000.

Sample Input 4

10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1

Sample Output 4

999983200

Be sure to print the product modulo (10^9+7).



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Runtime Error

Solution code:
mod=10**9+7
n,k=map(int,input().split())
A=list(map(int,input().split()))
count=k

B,C=[],[]
for i in A:
    if i>=0:B.append(i)
    else:C.append(i)

B.sort()
C.sort(key=lambda x:abs(x))

ans,flag=1,1
while k!=0:
    if k>=2:
        point=0
        if len(B)>=2 and len(C)>=2:
            if B[-1]*B[-2]>C[-1]*C[-2]:
                ans *=B.pop()
                point=1
            else:ans *=C.pop()*C.pop()
        elif len(B)>=2:ans *=B.pop()*B.pop()
        elif len(C)>=2:ans *=C.pop()*C.pop()
        else:flag=0
        k -=2-point
    else:
        if len(B)>=1:ans *=B.pop()
        else:flag=0
        k -=1
    ans %=mod

if flag:print(ans)
else:
    ans=1
    A=sorted(reverse=True)
    for i in range(count):
        ans *=A[i]
        ans %=mod
    print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7
ans = 1

if k == n:
    for i in range(n):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()
if max(a) < 0 and k%2 == 1:
    a.sort(reverse=True)
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()

a.sort(key=lambda x: abs(x))
cnt = 0
for i in range(1, k+1):
    ans *= a[-i]
    ans %= mod
    if a[-i] < 0:
        cnt += 1

if cnt%2 == 0:
    print(ans)
else:
    a_plus = None
    a_minus = None
    b_plus = None
    b_minus = None
    for i in range(k, 0, -1):
        if a[-i] >= 0 and a_plus == None:
            a_plus = a[-i]
        if a[-i] < 0 and a_minus == None:
            a_minus = a[-i]
    for i in range(k+1, n+1):
        if a[-i] >= 0 and b_plus == None:
            b_plus = a[-i]
        if a[-1] < 0 and b_minus == None:
            b_minus = a[-i]
    if a_plus == None or b_minus == None:
        ans *= pow(a_minus, mod-2, mod)
        ans %= mod
        ans *= b_plus
        ans %= mod
    elif a_minus == None or b_plus == None:
        ans *= pow(a_plus, mod-2, mod)
        ans %= mod
        ans *= b_minus
        ans %= mod
    else:
        if abs(a_plus*b_plus) > abs(a_minus*b_minus):
            ans *= pow(a_minus, mod-2, mod)
            ans %= mod
            ans *= b_plus
            ans %= mod
        else:
            ans *= pow(a_plus, mod-2, mod)
            ans %= mod
            ans *= b_minus
            ans %= mod
    print(ans)

Submission status: Runtime Error

Solution code:
import datetime
import string
import re
import math

def isort(list, _beg, _end):
    if _beg < _end:
        beg = _beg
        end = _end
        pivot = abs(list[int((beg + end)/2)])
        while(True):
            while abs(list[beg]) < pivot: beg += 1
            while abs(list[end]) > pivot: end -= 1
            if beg <= end:
                tmp = list[beg]
                list[beg] = list[end]
                list[end] = tmp
                beg += 1
                end -= 1
            else:
                break
        isort(list, _beg, end)
        isort(list, beg, _end)

def searchByBool(list):
    for i in range(len(list)):
        if check(list[i]): return i
    return -1

def check(num):
    if num >= 0: return True
    else: return False

sp = list(map(int, input().split()))
N = sp[0]
K = sp[1]
alist = list(map(int, input().split()))
klist = []
isK = True

isort(alist, 0, len(alist) - 1)
alist.reverse()

numMinus = 0
for i in range(K):
    if check(alist[i]) == False: numMinus += 1

# select biggest K numbers in terms of absolute value

# for all chosen numbers
# if the number of negative number is even
if numMinus % 2 == 0:
    klist = alist[0:K]
    isK = False

# if odd
# -> choose the smallest number, and search opposite number
if isK and K < N:
    _right = -1
    for right in range(K,N):
        if check(alist[K-1]) != check(alist[right]):
            isK = False
            _right = right
            klist = alist[0:K]
            klist[K-1]=alist[_right]
            break
    for left in range(K):
        if check(alist[K-1-left]) != check(alist[K]):
            if _right == -1:
                alist[K-1-left] = alist[K]
            elif abs(alist[K-1-left])/abs(alist[K]) < abs(alist[K-1])/abs(alist[_right]):
                alist[K-1-left] = alist[K]
            klist = alist[0:K]
            isK = False
            break

if isK:
    alist.reverse()
    klist = alist[0:K]

multi = klist[0]
for i in range(1, K):
    multi *= klist[i]
    multi = multi % 1000000007

print(multi)

Submission status: Runtime Error

Solution code:
import datetime
import string
import re
import math

def isort(list, _beg, _end):
    if _beg < _end:
        beg = _beg
        end = _end
        pivot = abs(list[int((beg + end)/2)])
        while(True):
            while abs(list[beg]) < pivot: beg += 1
            while abs(list[end]) > pivot: end -= 1
            if beg <= end:
                tmp = list[beg]
                list[beg] = list[end]
                list[end] = tmp
                beg += 1
                end -= 1
            else:
                break
        isort(list, _beg, end)
        isort(list, beg, _end)

def searchByBool(list):
    for i in range(len(list)):
        if check(list[i]): return i
    return -1

def check(num):
    if num >= 0: return True
    else: return False

sp = list(map(int, input().split()))
N = sp[0]
K = sp[1]
alist = list(map(int, input().split()))
klist = []
isK = True

isort(alist, 0, len(alist) - 1)
alist.reverse()

numMinus = 0
for i in range(K):
    if check(alist[i]) == False: numMinus += 1

# select biggest K numbers in terms of absolute value

# for all chosen numbers
# if the number of negative number is even
if numMinus % 2 == 0:
    klist = alist[0:K]
    isK = False

# if odd
# -> choose the smallest number, and search opposite number
if isK and K < N:
    _right = -1
    for right in range(K,N):
        if check(alist[K-1]) != check(alist[right]):
            isK = False
            _right = right
            klist = alist[0:K]
            klist[K-1]=alist[_right]
            break
    for left in range(K):
        if check(alist[K-1-left]) != check(alist[K-1]):
            if _right == -1:
                alist[K-1-left] = alist[K]
            elif abs(alist[K-1-left])/abs(alist[K]) < abs(alist[K-1])/abs(alist[_right]):
                alist[K-1-left] = alist[K]
            klist = alist[0:K]
            isK = False
            break

if isK:
    alist.reverse()
    klist = alist[0:K]

multi = klist[0]
for i in range(1, K):
    multi *= klist[i]
    multi = multi % 1000000007

print(multi)

Submission status: Runtime Error

Solution code:
import datetime
import string
import re
import math

def isort(list, _beg, _end):
    if _beg < _end:
        beg = _beg
        end = _end
        pivot = abs(list[int((beg + end)/2)])
        while(True):
            while abs(list[beg]) < pivot: beg += 1
            while abs(list[end]) > pivot: end -= 1
            if beg <= end:
                tmp = list[beg]
                list[beg] = list[end]
                list[end] = tmp
                beg += 1
                end -= 1
            else:
                break
        isort(list, _beg, end)
        isort(list, beg, _end)

def searchByBool(list):
    for i in range(len(list)):
        if check(list[i]): return i
    return -1

def check(num):
    if num >= 0: return True
    else: return False

sp = list(map(int, input().split()))
N = sp[0]
K = sp[1]
alist = list(map(int, input().split()))
klist = []
isK = True

isort(alist, 0, len(alist) - 1)
alist.reverse()

numMinus = 0
for i in range(K):
    if check(alist[i]) == False: numMinus += 1

# select biggest K numbers in terms of absolute value

# for all chosen numbers
# if the number of negative number is even
if numMinus % 2 == 0:
    klist = alist[0:K]
    isK = False

# if odd
# -> choose the smallest number, and search opposite number
if isK and K < N:
    _right = -1
    for right in range(K,N):
        if check(alist[K-1]) != check(alist[right]):
            isK = False
            _right = right
            klist = alist[0:K]
            klist[K-1]=alist[_right]
            break
    for left in range(K-1):
        if check(alist[K-1-left]) != check(alist[K-1]):
            if _right == -1:
                alist[K-1-left] = alist[K]
            elif abs(alist[K-1-left])/abs(alist[K]) < abs(alist[K-1])/abs(alist[_right]):
                alist[K-1-left] = alist[K]
            klist = alist[0:K]
            isK = False
            break

if isK:
    alist.reverse()
    klist = alist[0:K]

multi = klist[0]
for i in range(1, K):
    multi *= klist[i]
    multi = multi % 1000000007

print(multi)

Submission status: Runtime Error

Solution code:
import datetime
import string
import re
import math

def isort(list, _beg, _end):
    if _beg < _end:
        beg = _beg
        end = _end
        pivot = abs(list[int((beg + end)/2)])
        while(True):
            while abs(list[beg]) < pivot: beg += 1
            while abs(list[end]) > pivot: end -= 1
            if beg <= end:
                tmp = list[beg]
                list[beg] = list[end]
                list[end] = tmp
                beg += 1
                end -= 1
            else:
                break
        isort(list, _beg, end)
        isort(list, beg, _end)

def searchByBool(list):
    for i in range(len(list)):
        if check(list[i]): return i
    return -1

def check(num):
    if num >= 0: return True
    else: return False

sp = list(map(int, input().split()))
N = sp[0]
K = sp[1]
alist = list(map(int, input().split()))
klist = []
isK = True

isort(alist, 0, len(alist) - 1)
alist.reverse()

numMinus = 0
for i in range(K):
    if check(alist[i]) == False: numMinus += 1

# select biggest K numbers in terms of absolute value

# for all chosen numbers
# if the number of negative number is even
if numMinus % 2 == 0:
    klist = alist[0:K]
    isK = False

# if odd
# -> choose the smallest number, and search opposite number
if isK and K < N:
    _right = -1
    for right in range(K,N):
        if check(alist[K-1]) != check(alist[right]):
            isK = False
            _right = right
            klist = alist[0:K]
            klist[K-1]=alist[_right]
            break
    for left in range(K-1):
        if check(alist[K-1-left]) != check(alist[K-1]):
            if _right == -1 or abs(alist[K-1-left])/abs(alist[K]) < abs(alist[K-1])/abs(alist[_right]):
                alist[K-1-left] = alist[K]
            klist = alist[0:K]
            isK = False
            break

if isK:
    alist.reverse()
    klist = alist[0:K]

multi = klist[0]
for i in range(1, K):
    multi *= klist[i]
    multi = multi % 1000000007

print(multi)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7
ans = 1

if k == n:
    for i in range(n):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()
if max(a) < 0 and k%2 == 1:
    a.sort(reverse=True)
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()

a.sort(key=lambda x: abs(x))
cnt = 0
for i in range(1, k+1):
    ans *= abs(a[-i])
    ans %= mod
    if a[-i] < 0:
        cnt += 1

if cnt%2 == 0:
    print(ans)
else:
    a_plus = None
    a_minus = None
    b_plus = None
    b_minus = None
    for i in range(k, 0, -1):
        if a[-i] >= 0 and a_plus == None:
            a_plus = abs(a[-i])
        if a[-i] < 0 and a_minus == None:
            a_minus = abs(a[-i])
    for i in range(k+1, n+1):
        if a[-i] >= 0 and b_plus == None:
            b_plus = abs(a[-i])
        if a[-1] < 0 and b_minus == None:
            b_minus = abs(a[-i])
    if a_plus == None or b_minus == None:
        ans *= pow(a_minus, mod-2, mod)
        ans %= mod
        ans *= b_plus
        ans %= mod
    elif a_minus == None or b_plus == None:
        ans *= pow(a_plus, mod-2, mod)
        ans %= mod
        ans *= b_minus
        ans %= mod
    else:
        if a_plus*b_plus > a_minus*b_minus:
            ans *= pow(a_minus, mod-2, mod)
            ans %= mod
            ans *= b_plus
            ans %= mod
        else:
            ans *= pow(a_plus, mod-2, mod)
            ans %= mod
            ans *= b_minus
            ans %= mod
    print(ans)

Submission status: Runtime Error

Solution code:
import datetime
import string
import re
import math

def isort(list, _beg, _end):
    if _beg < _end:
        beg = _beg
        end = _end
        pivot = abs(list[int((beg + end)/2)])
        while(True):
            while abs(list[beg]) < pivot: beg += 1
            while abs(list[end]) > pivot: end -= 1
            if beg <= end:
                tmp = list[beg]
                list[beg] = list[end]
                list[end] = tmp
                beg += 1
                end -= 1
            else:
                break
        isort(list, _beg, end)
        isort(list, beg, _end)

def searchByBool(list):
    for i in range(len(list)):
        if check(list[i]): return i
    return -1

def check(num):
    if num >= 0: return True
    else: return False

sp = list(map(int, input().split()))
N = sp[0]
K = sp[1]
alist = list(map(int, input().split()))
klist = []
isK = True

isort(alist, 0, len(alist) - 1)
alist.reverse()

numMinus = 0
for i in range(K):
    if check(alist[i]) == False: numMinus += 1

# select biggest K numbers in terms of absolute value

# for all chosen numbers
# if the number of negative number is even
if numMinus % 2 == 0:
    klist = alist[0:K]
    isK = False

# if odd
# -> choose the smallest number, and search opposite number
if isK:
    for i in range(K,N):
        if check(alist[K-1]) != check(alist[i]):
            alist[K-1]=alist[i]
            klist = alist[0:K]
            isK = False
            break

if isK:
    for i in range(K-1):
        if check(alist[K-1-i]) != check(alist[K-1]):
            alist[K-1-i] = alist[K]
            klist = alist[0:K]
            isK = False
            break

if isK:
    print(-1)
    alist.reverse()
    klist = alist[0:K]

multi = klist[0]
for i in range(1, K):
    multi *= klist[i]
    multi = multi % 1000000007

print(multi)

Submission status: Runtime Error

Solution code:
import datetime
import string
import re
import math

def isort(list, _beg, _end):
    if _beg < _end:
        beg = _beg
        end = _end
        pivot = abs(list[int((beg + end)/2)])
        while(True):
            while abs(list[beg]) < pivot: beg += 1
            while abs(list[end]) > pivot: end -= 1
            if beg <= end:
                tmp = list[beg]
                list[beg] = list[end]
                list[end] = tmp
                beg += 1
                end -= 1
            else:
                break
        isort(list, _beg, end)
        isort(list, beg, _end)

def searchByBool(list):
    for i in range(len(list)):
        if check(list[i]): return i
    return -1

def check(num):
    if num >= 0: return True
    else: return False

sp = list(map(int, input().split()))
N = sp[0]
K = sp[1]
alist = list(map(int, input().split()))
klist = []
isK = True

isort(alist, 0, len(alist) - 1)
alist.reverse()

numMinus = 0
for i in range(K):
    if check(alist[i]) == False: numMinus += 1

# select biggest K numbers in terms of absolute value

# for all chosen numbers
# if the number of negative number is even
if numMinus % 2 == 0:
    klist = alist[0:K]
    isK = False

# if odd
# -> choose the smallest number, and search opposite number
if isK:
    for i in range(K,N):
        if check(alist[K-1]) != check(alist[i]):
            alist[K-1]=alist[i]
            klist = alist[0:K]
            isK = False
            break

if isK:
    for i in range(K-1):
        if check(alist[K-1-i]) != check(alist[K-1]):
            alist[K-1-i] = alist[K]
            klist = alist[0:K]
            isK = False
            break

if isK:
    print(-1)
    return
    alist.reverse()
    klist = alist[0:K]

multi = klist[0]
for i in range(1, K):
    multi *= klist[i]
    multi = multi % 1000000007

print(multi)

Submission status: Runtime Error

Solution code:
import datetime
import string
import re
import math

def isort(list, _beg, _end):
    if _beg < _end:
        beg = _beg
        end = _end
        pivot = abs(list[int((beg + end)/2)])
        while(True):
            while abs(list[beg]) < pivot: beg += 1
            while abs(list[end]) > pivot: end -= 1
            if beg <= end:
                tmp = list[beg]
                list[beg] = list[end]
                list[end] = tmp
                beg += 1
                end -= 1
            else:
                break
        isort(list, _beg, end)
        isort(list, beg, _end)

def searchByBool(list):
    for i in range(len(list)):
        if check(list[i]): return i
    return -1

def check(num):
    if num >= 0: return True
    else: return False

sp = list(map(int, input().split()))
N = sp[0]
K = sp[1]
alist = list(map(int, input().split()))
klist = []
isK = True

isort(alist, 0, len(alist) - 1)
alist.reverse()

numMinus = 0
for i in range(K):
    if check(alist[i]) == False: numMinus += 1

# select biggest K numbers in terms of absolute value

# for all chosen numbers
# if the number of negative number is even
if numMinus % 2 == 0:
    klist = alist[0:K]
    isK = False

# if odd
# -> choose the smallest number, and search opposite number
if isK:
    for i in range(K,N):
        if check(alist[K-1]) != check(alist[i]):
            alist[K-1]=alist[i]
            klist = alist[0:K]
            isK = False
            break

if isK:
    for i in range(K-1):
        if check(alist[K-1-i]) != check(alist[K-1]):
            alist[K-1-i] = alist[K]
            klist = alist[0:K]
            isK = False
            break

if isK:
    alist.reverse()
    klist = alist[0:K]

multi = klist[0]
for i in range(1, K):
    multi *= klist[i]
    multi = multi % 1000000007

print(multi)

Submission status: Runtime Error

Solution code:
import datetime
import string
import re
import math

def isort(list, _beg, _end):
    if _beg < _end:
        beg = _beg
        end = _end
        pivot = abs(list[int((beg + end)/2)])
        while(True):
            while abs(list[beg]) < pivot: beg += 1
            while abs(list[end]) > pivot: end -= 1
            if beg <= end:
                tmp = list[beg]
                list[beg] = list[end]
                list[end] = tmp
                beg += 1
                end -= 1
            else:
                break
        isort(list, _beg, end)
        isort(list, beg, _end)

def searchByBool(list):
    for i in range(len(list)):
        if check(list[i]): return i
    return -1

def check(num):
    if num >= 0: return True
    else: return False

sp = list(map(int, input().split()))
N = sp[0]
K = sp[1]
alist = list(map(int, input().split()))
klist = []
isK = True

isort(alist, 0, len(alist) - 1)
alist.reverse()

numMinus = 0
for i in range(K):
    if check(alist[i]) == False: numMinus += 1

# select biggest K numbers in terms of absolute value

# for all chosen numbers
# if the number of negative number is even
if numMinus % 2 == 0:
    klist = alist[0:K]
    isK = False

# if odd
# -> choose the smallest number, and search opposite number
if isK:
    for i in range(K,N):
        if check(alist[K-1]) != check(alist[i]):
            alist[K-1]=alist[i]
            klist = alist[0:K]
            isK = False
            break

if isK:
    for i in range(K):
        if check(alist[K-1-i]) != check(alist[K-1]):
            alist[K-1-i] = alist[K]
            klist = alist[0:K]
            isK = False
            break

if isK:
    alist.reverse()
    klist = alist[0:K]

multi = klist[0]
for i in range(1, K):
    multi *= klist[i]
    multi = multi % 1000000007

print(multi)

Submission status: Runtime Error

Solution code:
import datetime
import string
import re
import math

def isort(list, _beg, _end):
    if _beg < _end:
        beg = _beg
        end = _end
        pivot = abs(list[int((beg + end)/2)])
        while(True):
            while abs(list[beg]) < pivot: beg += 1
            while abs(list[end]) > pivot: end -= 1
            if beg <= end:
                tmp = list[beg]
                list[beg] = list[end]
                list[end] = tmp
                beg += 1
                end -= 1
            else:
                break
        isort(list, _beg, end)
        isort(list, beg, _end)

def searchByBool(list):
    for i in range(len(list)):
        if check(list[i]): return i
    return -1

def check(num):
    if num >= 0: return True
    else: return False

sp = list(map(int, input().split()))
N = sp[0]
K = sp[1]
alist = list(map(int, input().split()))
klist = []
isK = True

isort(alist, 0, len(alist) - 1)
alist.reverse()

numMinus = 0
for i in range(K):
    if check(alist[i]) == False: numMinus += 1

# select biggest K numbers in terms of absolute value

# for all chosen numbers
# if the number of negative number is even
if numMinus % 2 == 0:
    klist = alist[0:K]
    isK = False

# if odd
# -> choose the smallest number, and search opposite number
if isK:
    for i in range(K,N):
        if check(alist[K-1]) != check(alist[i]):
            alist[K-1]=alist[i]
            klist = alist[0:K]
            isK = False
            break

if isK:
    for i in range(K):
        if check(alist[K-1-i]) != check(alist[K-1]):
            alist[K-1-i] = alist[K]
            klist = alist[0:K]
            isK = False
            break

if isK:
    klist = alist[N-K:N]

multi = klist[0]
for i in range(1, K):
    multi *= klist[i]
    multi = multi % 1000000007

print(multi)

Submission status: Runtime Error

Solution code:
import datetime
import string
import re
import math

def isort(list, _beg, _end):
    if _beg < _end:
        beg = _beg
        end = _end
        pivot = abs(list[int((beg + end)/2)])
        while(True):
            while abs(list[beg]) < pivot: beg += 1
            while abs(list[end]) > pivot: end -= 1
            if beg <= end:
                tmp = list[beg]
                list[beg] = list[end]
                list[end] = tmp
                beg += 1
                end -= 1
            else:
                break
        isort(list, _beg, end)
        isort(list, beg, _end)

def searchByBool(list):
    for i in range(len(list)):
        if check(list[i]): return i
    return -1

def check(num):
    if num >= 0: return True
    else: return False

sp = list(map(int, input().split()))
N = sp[0]
K = sp[1]
alist = list(map(int, input().split()))
klist = []
isK = True

isort(alist, 0, len(alist) - 1)
alist.reverse()

numMinus = 0
for i in range(K):
    if check(alist[i]) == False: numMinus += 1

# select biggest K numbers in terms of absolute value

# for all chosen numbers
# if the number of negative number is even
if numMinus % 2 == 0:
    klist = alist[0:K]
    isK = False

# if odd
# -> choose the smallest number, and search opposite number
if isK:
    for i in range(K,N):
        if check(alist[K-1]) != check(alist[i]):
            alist[K-1]=alist[i]
            klist = alist[0:K]
            isK = False
            break

if isK:
    for i in range(K):
        if check(alist[K-1-i]) != check(alist[K-1]):
            alist[K-1-i] = alist[K]
            klist = alist[0:K]
            isK = False
            break

if isK:
    klist = alist[N-K:N]
print(klist)

multi = klist[0]
for i in range(1, K):
    multi *= klist[i]
    multi = multi % 1000000007

print(multi)

Submission status: Runtime Error

Solution code:
import sys
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
sys.setrecursionlimit(int(1e+6))
MOD = int(1e+9) + 7
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3

def main():
    N, K = i2nn()
    A = i2nn()
    # 選択の余地がない場合、全部掛けるしかない
    if N == K:
        n = 1
        for a in A:
            n = (n * a) % MOD
        print(n)
        return

    Ap = [ n for n in A if n >= 0]
    An = [-n for n in A if n < 0]
    Ap.sort()
    Ap.reverse()
    An.sort()
    An.reverse()
    Np = len(Ap)
    Nn = len(An)
    # 結果はプラスにしたい。Aiが全部マイナスかつKが奇数だとNG
    # 結果をプラスにできない場合、絶対値を最小化する
    if N == Nn and K % 2 == 1:
        n = 1
        A.sort()
        A.reverse()
        for i in range(K):
            n = (n * A[i]) % MOD
        print(n)
        return

    n = 1
    k = K
    i = 0
    j = 0
    # 結果をプラスに場合、プラスを維持しつつ、絶対値を最大化する
    # Kは偶数で考えたい。Kが奇数のとき、一番大きな正の数を取る
    if k % 2 == 1:
        n = (n * Ap[i]) % MOD
        i += 1
        k -= 1
    while k > 0:
        if Np - i == 0:
            n = (n * An[j]) % MOD
            j += 1
            n = (n * An[j]) % MOD
            j += 1
        elif Nn - j == 0:
            n = (n * Ap[i]) % MOD
            i += 1
            n = (n * Ap[i]) % MOD
            i += 1
        else:
            np = Ap[i] * Ap[i+1]
            nn = An[j] * An[j+1]
            if np >= nn:
                n = (n * np) % MOD
                i += 2
            else:
                n = (n * nn) % MOD
                j += 2
        k -= 2
    print(n)

main()

Submission status: Runtime Error

Solution code:
import datetime
import string
import re
import math

def isort(list, _beg, _end):
    if _beg < _end:
        beg = _beg
        end = _end
        pivot = abs(list[int((beg + end)/2)])
        while(True):
            while abs(list[beg]) < pivot: beg += 1
            while abs(list[end]) > pivot: end -= 1
            if beg <= end:
                tmp = list[beg]
                list[beg] = list[end]
                list[end] = tmp
                beg += 1
                end -= 1
            else:
                break
        isort(list, _beg, end)
        isort(list, beg, _end)

def searchByBool(list):
    for i in range(len(list)):
        if check(list[i]): return i
    return -1

def check(num):
    if num >= 0: return True
    else: return False

sp = list(map(int, input().split()))
N = sp[0]
K = sp[1]
alist = list(map(int, input().split()))
klist = []
isK = True

isort(alist, 0, len(alist) - 1)
alist.reverse()

numMinus = 0
for i in range(K):
    if check(alist[i]) == False: numMinus += 1

# select biggest K numbers in terms of absolute value

# for all chosen numbers
# if the number of negative number is even
if numMinus % 2 == 0:
    klist = alist[0:K]
    isK = False

# if odd
# -> choose the smallest number, and search opposite number
# if isK:
#     for i in range(K,N):
#         if check(alist[K-1]) != check(alist[i]):
#             klist = alist[0:K-1].append(alist[i])
#             isK = False
#             break

# if isK:
#     for i in range(K):
#         if check(alist[K-1-i]) != check(alist[K-1]):
#             klist = alist[0:K-1-i] + list(alist[K]) + alist[K-i:K]
#             isK = False
#             break

if isK:
    klist = alist[N-K:N-1]

multi = klist[0]
for i in range(1, K):
    multi *= klist[i]
    multi = multi % 1000000007

print(multi)

Submission status: Runtime Error

Solution code:
import datetime
import string
import re
import math

def isort(list, _beg, _end):
    if _beg < _end:
        beg = _beg
        end = _end
        pivot = abs(list[int((beg + end)/2)])
        while(True):
            while abs(list[beg]) < pivot: beg += 1
            while abs(list[end]) > pivot: end -= 1
            if beg <= end:
                tmp = list[beg]
                list[beg] = list[end]
                list[end] = tmp
                beg += 1
                end -= 1
            else:
                break
        isort(list, _beg, end)
        isort(list, beg, _end)

def searchByBool(list):
    for i in range(len(list)):
        if check(list[i]): return i
    return -1

def check(num):
    if num >= 0: return True
    else: return False

sp = list(map(int, input().split()))
N = sp[0]
K = sp[1]
alist = list(map(int, input().split()))
klist = []
isK = True

isort(alist, 0, len(alist) - 1)
alist.reverse()

numMinus = 0
for i in range(K):
    if check(alist[i]) == False: numMinus += 1

# select biggest K numbers in terms of absolute value

# for all chosen numbers
# if the number of negative number is even
if numMinus % 2 == 0:
    klist = alist[0:K]
    isK = False

# if odd
# -> choose the smallest number, and search opposite number
if isK:
    for i in range(K,N):
        if check(alist[K-1]) != check(alist[i]):
            klist = alist[0:K-1].append(alist[i])
            isK = False
            break

if isK:
    for i in range(K):
        if check(alist[K-1-i]) != check(alist[K-1]):
            klist = alist[0:K-1-i] + list(alist[K]) + alist[K-i:K]
            isK = False
            break

if isK:
    klist = alist[N-K:N-1]

multi = klist[0]
for i in range(1, K):
    multi *= klist[i]
    multi = multi % 1000000007

print(multi)