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:
import sys

if(__name__ == "__main__"):

    N, K = map( int, input().strip().split() )
    divisor = 10**9+7

    list_a = list( map(int, input().strip().split()) )

    """
    left, right側の2項の積で大きい方を選択
    選べるのが残り1項ならright側を選択
    """
    multiplies = 1
    if(N==K):
        for i in range(N):
            multiplies = multiplies * list_a[i] % divisor
    else:
        list_a.sort()
        flag_overzero = True
        """
        解が負になるのはN>Kの時には
        正の項が1つもなく、Kが奇数の時
        """
        if(list_a[-1] < 0 and K % 2 != 0):
            flag_overzero = False

        if(flag_overzero == True):
            left = 0
            right = N-1

            if(K%2 != 0):
                multiplies = multiplies * list_a[right] % divisor
                K -= 1
                right -= 1
            multiply_left = list_a[left] * list_a[left+1]
            multiply_right = list_a[right] * list_a[right-1]
            for k in range(K//2):

                if(multiply_left < multiply_right):
                    multiply_right %= divisor
                    multiplies = multiplies * multiply_right % divisor
                    right -= 2
                    multiply_right = list_a[right] * list_a[right-1]

                else:
                    multiply_left %= divisor
                    multiplies = multiplies * multiply_left % divisor
                    left += 2
                    multiply_left = list_a[left] * list_a[left+1]
        else:
            """
            全て負の項
            list_a = [-5, -3, -1]のようにソートされている
            末尾の項から選んでいく
            """
            for i in range(K):
                multiplies = multiplies * list_a[N-1-i] % divisor
    print(multiplies)

Submission status: Runtime Error

Solution code:
n , k = map(int, input().split())
a = list(map(int, input().split()))
neg = []
pos = []
mod = 10**9+7
for i in range(n):
    if a[i] >= 0:
        pos.append(a[i])
    else:
        neg.append(a[i])
neg.sort()
pos.sort(reverse = True)
if (len(pos) == 0 and k % 2 == 1):
    ans = 1
    a.sort(reverse = True)
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans % mod)
else:
    #最大化するとき
    from collections import deque
    ans = 1
    neg_new = []
    for i in range(0, len(neg)//2):
        neg_new.append(neg[2*i] * neg[2*i+1])
    neg_new = deque(sorted(neg_new, reverse = True))
    pos = deque(pos)
    if k % 2 == 1:
        k -= 1
        ans = pos.popleft()
    else:
        ans = 1
    while k > 0:
        if len(pos) >= 2 and len(neg_new) >= 1:
            if pos[0] * pos[1] > neg_new[0]:
                ans *= pos.popleft() * pos.popleft()
            else:
                ans *= neg_new.popleft()
        elif len(pos) >= 2:
            ans *= pos.popleft() * pos.popleft()
        else:
            ans *= neg_new.popleft()
        k -= 2
        ans %= mod
    print(ans % mod)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
m = 10**9+7
B = [abs(a) for a in A]
B.sort(reverse=True)
pos = [*filter(lambda x: x >= 0, A)]
neg = [*filter(lambda x: x < 0, A)]
pos.sort(reverse=True)
neg.sort()

ans = 1
i,j = 0,0
while i+j < K:
    flag = True
    if i == len(pos):
        flag = False
    elif j == len(neg):
        flag = True
    elif pos[i] >= -neg[j]:
        flag = True
    else:
        flag = False

    if flag:
        ans = ans * pos[i] % m
        i += 1
    else:
        ans = ans * neg[j] % m
        j += 1
if len(pos) == 0:
    ans = 1
    for i in range(K):
        ans = ans * neg[len(neg)-1-i] % m
    print(ans)
elif j % 2 == 0 or N==K or len(neg) == 0:
    print(ans)
else:
    # この操作ができないものを分類
    flag = True
    if i >= len(pos)-1:
        flag = False
    elif j >= len(neg)-1:
        flag = True
    elif pos[i]*pos[i+1] >= neg[j]*neg[j+1]:
        flag = True
    else:
        flag = False

    if flag:
        ans = ans * pow(neg[j],m-2,m) % m
        ans = ans * pos[i+1] % m
    else:
        ans = ans * pow(pos[i],m-2,m) % m
        ans = ans * neg[j+1] % m
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
n,k=map(int,input().split())
a = list(map(int,input().split()))
plus = sorted([i for i in a if i > 0],reverse=True)
minus = sorted([i for i in a if i < 0])
b = []
p = 0
m = 0
MOD = 10**9 + 7
if(n - len(plus) -len(minus) <= k):
    print(0)
    sys.exit()

while(True):
    if(len(plus) != 0 and len(minus) != 0):
        if(plus[p] >= -minus[m]):
            b.append(plus[p])
            p += 1
        else:
            b.append(minus[m])
            m += 1
    if(p == len(plus)):
        for i in range(k-p-m):
            b.append(minus[i+m])
        break
    if(m == len(minus)):
        for i in range(k-p-m):
            b.append(plus[i+p])
        break
    if(p+m == k):
        if(m % 2 == 1):
            if(minus[m]*minus[m-1] > plus[p]*plus[p-1]):
                b[b.index(plus[p-1])] = minus[m]
            else:
                b[b.index(minus[m-1])] = plus[p]
        break
if(len([i for i in b if i<0]) %2 != 0):
    if(0 in a):
        print(0)
        sys.exit()
    else:
        ans = 1
        p,m = len(plus)-1,len(minus)-1
        b = []
        if(len(plus) != 0 and len(minus) != 0):
            for i in range(k):
                if(plus[p] > -minus[m]):
                    b.append(minus[m])
                    m -= 1
                else:
                    b.append(plus[m])
                    p -= 1
        
            for i in range(k):
                ans = ans*b[i] % MOD
            #ans = -((-ans) % -MOD)
            ans = (-ans % MOD)
            print(ans)
            sys.exit()
        if(len(plus) == 0):
            a = sorted(a,reverse=True)
            for i in range(k):
                ans = ans*a[i] % MOD
            print(ans)
            sys.exit()
ans = 1
for i in b:
    ans = ans*i % MOD
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

N, K = tuple(map(int, input().strip().split()))
As = list(map(int, input().strip().split()))

D = int(1E9 + 7)
r = 1

if K == N:
    for a in As:
        r = (r * (a % D)) % D
    print(r)

elif K % 2 == 1 and all(a < 0 for a in As):
    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * (a % D)) % D
    print(r)

else:

    k = 0

    Ps = sorted([a for a in As if a > 0], reverse=True)
    Qs = sorted([a for a in As if a < 0])

    while k < K:
    
        if len(Ps) == len(Qs) == 0:
            print(0)
            exit()

        elif len(Ps) == 0:
            q1 = Qs.pop(0)
            q2 = Qs.pop(0)
            q  = q1 * q2
            r = (r * (q % D)) % D
            k += 2

        elif len(Qs) < 2:
            p = Ps.pop(0)
            r = (r * (p % D)) % D
            k += 1

        else:
            p1 = Ps.pop(0)
            p2 = Ps.pop(0)
            p  = p1 * p2
            q1 = Qs.pop(0)
            q2 = Qs.pop(0)
            q  = q1 * q2
            if p > q:
                r = (r * (p1 % D)) % D
                Ps = [p2] + Ps
                Qs = [q1, q2] + Qs
                k += 1
            else:
                r = (r * (q % D)) % D
                Ps = [p1, p2] + Ps
                k += 2

    print(r)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

P = []
M = []
zero = 0
for a in A:
    if a > 0:
        P.append(a)
    elif a < 0:
        M.append(a)
    else:
        zero += 1

# 0 を選ぶしかない場合
if len(P) + len(M) < K:
    print(0)
    exit()

P.sort(reverse=True)
M.sort()

# a >= 0 のとき
if len(P) + zero == N:
    ans = 1
    for k in range(K):
        ans *= P[k]
        ans %= MOD
    print(ans)
    exit()

# a <= 0 のとき
if len(M) + zero == N:
    ans = 1
    if K % 2 == 0:
        for k in range(K):
            ans *= M[k]
            ans %= MOD
        print(ans)
    else:
        if zero > 0:
            print(0)
        else:
            M.sort(reverse=True)
            for k in range(K):
                ans *= M[k]
                ans %= MOD
            print(ans)
    exit()

# a に正・負両方含まれる場合
cur_p = 0
cur_m = 0
ans = 1
for k in range(K):
    if cur_p == len(P):
        ans *= M[cur_m]
        cur_m += 1
    elif cur_m == len(M):
        ans *= P[cur_p]
        cur_p += 1
    else:
        if P[cur_p] < abs(M[cur_m]):
            ans *= M[cur_m]
            cur_m += 1
        else:
            ans *= P[cur_p]
            cur_p += 1
    ans %= MOD

if cur_m % 2 == 0:
    print(ans)
else:
    if cur_p == len(P):
        ans *= M[cur_m]
        ans *= pow(P[cur_p - 1], MOD - 2, MOD)
        ans %= MOD
    elif cur_m == len(M):
        ans *= P[cur_p]
        ans *= pow(M[cur_m - 1], MOD - 2, MOD)
        ans %= MOD
    else:
        m1 = M[cur_m - 1]
        p1 = P[cur_p]
        m2 = M[cur_m]
        p2 = P[cur_p - 1]
        if p1 / m1 > m2 / p2:
            ans *= p1
            ans *= pow(m1, MOD - 2, MOD)
            ans %= MOD
        else:
            ans *= m2
            ans *= pow(p2, MOD - 2, MOD)
            ans %= MOD
    print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
cross = reduce(lambda a, b: a*b, a[:k])
asw = cross % 1000000007
print(asw)

Submission status: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n,k = m()

a = l()

a.sort()

mina = []

pra = []

for i in range(n):
	if a[i] >= 0:
		pra.append(a[i])
	else:
		mina.append(a[i])

lp = len(pra)

lm = len(mina)
ans = 1
if lp == 0:
	if k % 2 != 0:
		for i in range(0,k,2):
			if i == k-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		for i in range(0,k,2):
			ans *= (mina[i]*mina[i+1]) % mod
			ans %= mod
		print(ans % mod)
elif lp == 1:
	if n == k:
		ans *= pra[0]
		for i in range(0,lp,2):
			if i == lp-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		if k % 2 == 0:
			for i in range(0,k,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
		else:
			ans *= pra[0] 
			for i in range(0,k-1,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
else:
	cp = lp-1
	cm = 0
	count = 0
	#data = []
	
	for _ in range(k):
		if cp != -1 and cm != lm:
			if abs(mina[cm]) < pra[cp]:
				if cp == 0:
					if (k-lp) % 2 == 0:
						count += 1
						#ans *= pra[cp]
						#data.append(pra[cp])
						cp -= 1
					else:
						count += 1
						#ans *= mina[cm]
						#data.append(mina[cm])
						cm += 1

				else:
					count += 1
					#ans *= pra[cp]
					#data.append(pra[cp])
					cp -= 1
			else:
				if cm == lm-1:
					if lm % 2 == 0:
						count += 1
						#ans *= mina[cm]
						#data.append(mina[cm])
						cm += 1
					else:
						count += 1
						#ans *= pra[cp]
						#data.append(pra[cp])
						cp -= 1


				else:
					count += 1
					#ans *= mina[cm]
					#data.append(mina[cm])
					cm += 1
		elif cp != -1:
			#ans *= pra[cp]
			#data.append(pra[cp])
			cp -= 1
			count += 1
		elif cm != lm:
			#ans *= mina[cm]
			#data.append(mina[cm])
			cm += 1
			count += 1

		else:
			break
	if cm % 2 != 0:
		if cp == lp-1:
			cp -= 1
			cm -= 1

		else:
			if cp != -1 and cm != lm:
				if pra[cp+1] != 0 and pra[cp]/-mina[cm-1] >= -mina[cm]/pra[cp+1]:
					cp += 1
					cm += 1
				else:
					cp -= 1
					cm -= 1
			elif cp != -1:
				cp -= 1
				cm -= 1
			elif cm != lm:
				cp += 1
				cm += 1

		

	#data.sort()
	co = 0

	for i in range(0,cm,2):
		ans *= (mina[i] * mina[i+1]) % mod
		ans %= mod
	for i in range(lp-1,cp,-1):
		ans *= pra[i] % mod
		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
p=[]
n=[]
for i in range(N):
    if A[i]<0:
        n.append(A[i])
    else:
        p.append(A[i])
p.sort(reverse=True)
n.sort()
numplus=len(p)
if N==K:
    for i in range(N):
        ans=(ans*A[i])%MOD
elif numplus==0 and K%2==1:
    for i in range(1,K+1):
        ans=(ans*n[i*(-1)])%MOD
else:
    minus=0
    A.sort(reverse=True,key=lambda x:abs(x))
    for i in range(K):
        ans=(ans*A[i])%MOD
        if A[i]<0:
            minus+=1
    if minus%2==1 and ans!=0:
        pwaru=float('inf')
        nwaru=float('inf')
        for i in range(K-1,-1,-1):
            if A[i]>0:
                pwaru=A[i]
            elif A[i]<0:
                nwaru=B[i]
            if pwaru!=float('inf') and nwaru != float('inf'):
                break
        if pwaru==float('inf'):
            pkakeru=float('inf')
            for i in range(K,N):
                if A[i]>=0:
                    pkakeru=A[i]
                    break
            ans=(ans*pkakeru*pow(nwaru,MOD-2,MOD))%MOD
        else:
            pkakeru=0
            for i in range(K,N):
                if A[i]>=0:
                    pkakeru=A[i]
                    break
            nkakeru=0
            for i in range(K,N):
                if A[i]<0:
                    nkakeru=A[i]
                    break
            if nwaru*nkakeru>pwaru*pkakeru:
                ans=(ans*nkakeru*pow(pwaru,MOD-2,MOD))%MOD
            else:
                ans=(ans*pkakeru[i]*pow(nwaru,MOD-2,MOD))%MOD
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True, key = lambda x: abs(x))
mod = 10**9+7
nega = 0
posi = 0
zero = 0
for i in range(n):
    if a[i] > 0:
        posi += 1
    elif a[i] == 0:
        zero += 1
    else:
        nega += 1

if n == k:
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod
    if nega%2 == 1:
        ans *= -1

elif posi == 0:

    if k % 2 == 0:
        ans = 1
        for i in range(k):
            ans *= abs(a[i])
            ans %= mod

    else:
        if zero > 0:
            ans = 0
        else:
            a.reverse()
            ans = 1
            for i in range(k):
                ans *= abs(a[i])
                ans %= mod

            ans *= -1


else:
    posi = 0
    nega = 0
    zero = 0
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod

    for i in range(k):
        if a[i] > 0:
            posi += 1
        elif a[i] < 0:
            nega += 1
        else:
            zero += 1

    if zero > 0:
        ans = 0

    elif nega % 2 != 0:
        minposi = 0
        minnega = 0
        for i in range(k-1, -1, -1):
            if a[i] > 0:
                if minposi == 0:
                    minposi = a[i]
            else:
                if minnega == 0:
                    minnega = a[i]

        maxposi = 0
        maxnega = 0
        flag = 0
        for i in range(k, n):
            if a[i] > 0:
                if maxposi == 0:
                    maxposi = a[i]
            elif a[i] < 0:
                if maxnega == 0:
                    maxnega = a[i]

        if minposi == 0:
            pp

        if abs(minposi*maxposi) <= abs(minnega*maxnega):
            ans *= pow(abs(minposi), mod-2, mod)
            ans *= abs(maxnega)

        else:
            ans *= pow(abs(minnega), mod-2, mod)
            ans *= abs(maxposi)



print(ans % mod)

Submission status: Runtime Error

Solution code:
import sys
n,k=map(int,input().split())
a = list(map(int,input().split()))
plus = sorted([i for i in a if i > 0],reverse=True)
minus = sorted([i for i in a if i < 0])
b = []
p = 0
m = 0
MOD = 10**9 + 7

while(True):
    if(len(plus) != 0 and len(minus) != 0):
        if(plus[p] >= -minus[m]):
            b.append(plus[p])
            p += 1
        else:
            b.append(minus[m])
            m += 1
    if(p == len(plus)):
        for i in range(k-p-m):
            b.append(minus[i+m])
        break
    if(m == len(minus)):
        for i in range(k-p-m):
            b.append(plus[i+p])
        break
    if(p+m == k):
        if(m % 2 == 1):
            if(minus[m]*minus[m-1] > plus[p]*plus[p-1]):
                b[b.index(plus[p-1])] = minus[m]
            else:
                b[b.index(minus[m-1])] = plus[p]
        break
if(len([i for i in b if i<0]) %2 != 0):
    if(0 in a):
        print(0)
        sys.exit()
    else:
        ans = 1
        p,m = len(plus)-1,len(minus)-1
        b = []
        if(len(plus) != 0 and len(minus) != 0):
            for i in range(k):
                if(plus[p] > -minus[m]):
                    b.append(minus[m])
                    m -= 1
                else:
                    b.append(plus[m])
                    p -= 1
        
            for i in range(k):
                ans = ans*b[i] % MOD
            #ans = -((-ans) % -MOD)
            ans = (-ans % MOD)
            print(ans)
            sys.exit()
        if(len(plus) == 0):
            a = sorted(a,reverse=True)
            for i in range(k):
                ans = ans*a[i] % MOD
            print(ans)
            sys.exit()
ans = 1
for i in b:
    ans = ans*i % MOD
print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
list = list(map(int,input().split()))
list.sort()
ans = 1
if (list[0] >= 0) or (N == K):
    for i in range(K):
        seki *= list[-i]
elif (list[-1] < 0) and (K % 2 !=0):
    for i in range(K):
        seki *= list[-i]
elif (list[-1] < 0) and (K % 2 ==0):
    for i in range(K):
        seki *= list[i]
else:
    for i in range(K):
        seki *= list[-i]
    count = -1
    if seki < 0:
        while seki < 0:
            seki = seki / list[count] * list[-K + count]
            count -= 1
print(seki%((10**9)+7))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
modulo = 10 ** 9 + 7
*arr, = map(int, input().split())
inverses = [pow(v, modulo - 2, modulo) for v in arr]
neg_cnt = 0
for v in arr:
    if v < 0:
        neg_cnt += 1


def max_pos(arr):
    arr.sort(key=lambda obj: abs(obj), reverse=True)

    neg = []
    pos = []
    res = 1
    for i in range(k):
        res *= arr[i]
        res %= modulo
        if arr[i] < 0:
            neg.append(i)
        else:
            pos.append(i)

    if len(neg) % 2 == 0 or k == len(arr):
        return res

    next_neg = i
    next_pos = i
    while next_neg < len(arr) and arr[next_neg] >= 0:
        next_neg += 1

    while next_pos < len(arr) and arr[next_pos] < 0:
        next_pos += 1

    prev_neg = neg[-1]
    prev_pos = -1 if not pos else pos[-1]

    if (prev_pos == -1 or abs(arr[next_pos] * arr[prev_neg]) > abs(arr[prev_pos] * arr[next_neg])) and next_pos != len(arr):
        return (res * arr[next_pos] * inverses[prev_neg]) % modulo
    return (res * arr[next_neg] * inverses[prev_pos]) % modulo

def min_pos(arr):
    arr.sort(key=lambda obj: abs(obj))

    neg = []
    pos = []
    res = 1
    for i in range(k):
        res *= arr[i]
        res %= modulo
        if arr[i] < 0:
            neg.append(i)
        else:
            pos.append(i)

    if len(neg) % 2 == 1 or k == len(arr):
        return res

    next_neg = i
    next_pos = i
    while next_neg < len(arr) and arr[next_neg] >= 0:
        next_neg += 1

    while next_pos < len(arr) and arr[next_pos] < 0:
        next_pos += 1

    prev_neg = neg[-1]
    prev_pos = -1 if not pos else pos[-1]

    if (prev_pos == -1 or abs(arr[next_pos] * arr[prev_neg]) < abs(arr[prev_pos] * arr[next_neg])) and next_pos != len(arr):
        print(next_pos)
        return (res * arr[next_pos] * inverses[prev_neg]) % modulo
    return (res * arr[next_neg] * inverses[prev_pos]) % modulo


if neg_cnt == n and k % 2 == 1:
    print(min_pos(arr))
elif k == 1:
    print(max(arr) % modulo)
else:
    print(max_pos(arr))

Submission status: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n,k = m()

a = l()

a.sort()

mina = []

pra = []

for i in range(n):
	if a[i] >= 0:
		pra.append(a[i])
	else:
		mina.append(a[i])

lp = len(pra)

lm = len(mina)
ans = 1
if lp == 0:
	if k % 2 != 0:
		for i in range(0,k,2):
			if i == k-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		for i in range(0,k,2):
			ans *= (mina[i]*mina[i+1]) % mod
			ans %= mod
		print(ans % mod)
elif lp == 1:
	if n == k:
		ans *= pra[0]
		for i in range(0,lp,2):
			if i == lp-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		if k % 2 == 0:
			for i in range(0,k,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
		else:
			ans *= pra[0] 
			for i in range(0,k-1,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
else:
	cp = lp-1
	cm = 0
	count = 0
	#data = []
	
	for _ in range(k):
		if cp != -1 and cm != lm:
			if abs(mina[cm]) < pra[cp]:
				if cp == 0:
					if (k-lp) % 2 == 0:
						count += 1
						#ans *= pra[cp]
						#data.append(pra[cp])
						cp -= 1
					else:
						count += 1
						#ans *= mina[cm]
						#data.append(mina[cm])
						cm += 1

				else:
					count += 1
					#ans *= pra[cp]
					#data.append(pra[cp])
					cp -= 1
			else:
				if cm == lm-1:
					if lm % 2 == 0:
						count += 1
						#ans *= mina[cm]
						#data.append(mina[cm])
						cm += 1
					else:
						count += 1
						#ans *= pra[cp]
						#data.append(pra[cp])
						cp -= 1


				else:
					count += 1
					#ans *= mina[cm]
					#data.append(mina[cm])
					cm += 1
		elif cp != -1:
			#ans *= pra[cp]
			#data.append(pra[cp])
			cp -= 1
			count += 1
		elif cm != lm:
			#ans *= mina[cm]
			#data.append(mina[cm])
			cm += 1
			count += 1

		else:
			break
	if cm % 2 == 0:
		if cp == lp-1:
			cp -= 1
			cm -= 1

		else:
			if cp != -1 and cm != lm:
				if pra[cp+1] != 0 and pra[cp]/-mina[cm-1] <= -mina[cm]/pra[cp+1]:
					cp += 1
					cm += 1
				else:
					cp -= 1
					cm -= 1
			elif cp != -1:
				cp -= 1
				cm -= 1
			elif cm != lm:
				cp += 1
				cm += 1

		

	#data.sort()
	co = 0

	for i in range(0,cm,2):
		ans *= (mina[i] * mina[i+1]) % mod
		ans %= mod
	for i in range(lp-1,cp,-1):
		ans *= pra[i] % mod
		ans %= mod


		
	print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
n,k = map(int,input().split())
a_list = sorted(map(int,input().split()))
mod = 10**9+7
if n-k < a_list.count(0):
    print(0)
    exit()
if sum([1 for a in a_list if np.sign(a)==-1])==k and k%2==1:
    a_list.sort(key = abs)
    ans = 1
    for num in a_list[:k]:
        ans *= num
        ans %= mod
    print(ans)
    exit()
else:
    a_list.sort(key = abs,reverse = True)
    add = 1
    remove = 1
    if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
        nagative_big = [num for num in a_list[:k] if np.sign(num)==-1]
        positive_big = [num for num in a_list[:k] if np.sign(num)!=-1]
        negative_small = [num for num in a_list[k:] if np.sign(num)==-1]
        positive_small = [num for num in a_list[k:] if np.sign(num)!=-1]
        
        if len(negative_big)==0 or len(positive_small):
            remove = min(positive_big)
            add = min(negative_small)
        elif len(positive_big)==0 or len(negative_small):
            remove = max(negative_big)
            add = max(positive_small)
        else:
            if max(positive_small)/max(negative_big) < min(negative_small)/min(positive_big):
                remove = max(negative_big)
                add = max(positive_small)
            else:
                remove = positive_big
                add = negative_small
ans = 1
for num in a_list[:k]:
    ans *= num
    ans %= mod
    
if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
    ans *= add
    ans %= mod
    ans *= pow(remove, mod-2, mod)
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush
mod = 10**9+7
n, k = map(int, input().split())
a = [int(x) for x in input().split()]


def sgn(x):
    if x > 0:
        return 0
    elif x < 0:
        return 1
    else:
        return 2


pl = []
mn = []
zr = []

for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mn.append(-x)
    else:
        zr.append(x)

pl = sorted(pl, reverse=True)
mn = sorted(mn, reverse=True)


b = [(abs(a[i]), sgn(a[i])) for i in range(n)]
b = sorted(b, reverse=True)

c = [0, 0, 0]
for i in range(k):
    c[b[i][1]] += 1
    if c[2] > 1:
        print(0)
        exit()


def solve(c):
    ans = 1
    for i in range(c[0]):
        ans *= pl[i]
        ans %= mod
    for i in range(c[1]):
        ans *= mn[i]
        ans %= mod
    return ans


if c[1] % 2 == 0:
    print(solve(c))
elif c[0] <= len(pl) - 1:
    c[0] += 1
    c[1] -= 1
    print(solve(c))
elif c[0] == len(pl):
    if c[0] == 0:
        if len(zr) > 0:
            print(0)
            exit()
        else:
            tmp = 1
            for i in range(k):
                tmp *= mn[-i-1]
                tmp %= mod
            print((-tmp) % mod)
    else:
        if c[1] <= len(mn) - 1:
            c[0] -= 1
            c[1] += 1
            print(solve())
        else:
            print(solve())