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 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 = []

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]

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

if len(klist) != K:
    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]
            break

if len(klist) != K:
    klist = alist[N-K:N-1]

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 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 = []

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]

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

if len(klist) != K:
    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]
            break

if len(klist) != K:
    klist = alist[N-K:N-1]

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 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 = []

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]

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

if len(klist) != K:
    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]

if len(klist) != K:
    klist = alist[N-K:N-1]

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:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7
ans = 1

if k == 1:
    max(a)
    exit()

lst = []
minus = []
for i in range(n):
    if a[i] >= 0:
        lst.append([a[i], 1])
    else:
        minus.append(a[i])

if k % 2 == 1 and lst != []:
    lst.sort(key=lambda x: x[0])
    ans *= lst.pop()[0]
    k -= 1
elif k % 2 == 1 and lst == []:
    a.sort(reverse=True)
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()

minus.sort(reverse=True)
while minus != []:
    if len(minus) >= 2:
        a = minus.pop()
        b = minus.pop()
        lst.append([a*b, 2])
    else:
        a = minus.pop()
        lst.pop([a, 1])

lst.sort(key=lambda x: x[0])
while k > 0:
    lst1 = lst.pop()
    lst2 = lst.pop()
    if [lst1[1], lst2[1]] == [1, 1]:
        ans *= lst1[0]
        ans %= mod
        ans *= lst2[0]
        ans %= mod
    elif [lst1[1], lst2[1]] == [1, 2]:
        ans *= lst2[0]
        ans %= mod
        lst.append(lst1)
    elif [lst1[1], lst2[1]] == [2, 1]:
        ans *= lst1[0]
        ans %= mod
        lst.append(lst2)
    else:
        ans *= lst1[0]
        ans %= mod
        lst.append(lst2)
    k -= 2
print(ans)

Submission status: Runtime Error

Solution code:
n,k = list(map(int,input().split())); arr = list(map(int,input().split())); arr.sort(reverse=True)
absarr = [[abs(i),1 if i>0 else -1 if i<0 else 0] for i in arr]; absarr.sort(reverse=True, key=lambda x: x[0])
mod = 10**9+7

zeroflag = True if absarr[0] == 0 else False
from collections import Counter
posnegarr = Counter([i[1] for i in absarr[:k]])
pos = posnegarr[1]; neg = posnegarr[-1]

if absarr[-k] == 0:
    ans = 0
elif neg % 2 == 0 or n == k:
    ans = 1
    for i in absarr[:k]:
        ans *= i[0]; ans %= mod
    if n == k and neg % 2 == 1:
        ans = -ans % mod
else:
    ans = 1
    for i in absarr[:k]:
        ans *= i[0]; ans %= mod
    if pos > 0:
        if absarr[n-k-1][0] == 0:
            ans = 0
        nextpos = nextneg = 0
        tmp = n-k-1
        while tmp >= 0 and (nextpos == 0 or nextneg == 0):
            num = absarr[tmp]
            if num[0] == 0:
                break
            elif num[1] > 0 and nextpos == 0:
                nextpos = num[0]
            elif num[1] < 0 and nextneg == 0:
                nextneg = num[0]
            tmp -= 1
        backpos = backneg = 0
        tmp = n-k
        while backpos == 0 or backneg == 0:
            num = absarr[tmp]
            if num[1] > 0 and backpos == 0:
                backpos = num[0]
            elif num[1] < 0 and backneg == 0:
                backneg = num[0]
            tmp += 1
        if ans == 0:
            pass
        elif nextpos*backpos > nextneg*backneg:
            ans *= nextpos*pow(backneg,-1,mod); ans %= mod
        else:
            ans *= nextneg*pow(backpos,-1,mod); ans %= mod
    else:
        nextpos = 0
        tmp = n-k-1
        while tmp >= 0 and nextpos == 0:
            num = absarr[tmp]
            if num[1] > 0:
                nextpos = num[0]
            tmp -= 1
        backneg = absarr[n-k][0]
        if nextpos != 0:
            ans *= nextpos * pow(backneg,-1,mod)
        elif zeroflag:
            ans = 0
        else:
            ans = 1
            for i in arr[:k]:
                ans *= i; ans %= mod
        
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
lst = list(map(int, input().split()))
sortlst = sorted(lst, key = abs, reverse = True)
#print(sortlst)

signlst = ["posi" if sortlst[i] >= 0 else "nega" for i in range(n)] 
#print(signlst)

if "nega" not in signlst:
#	print("posi only")
	ans = 1
	for j in range(k):
		ans *= sortlst[j] 

elif "posi" not in signlst:
#	print("only nega")
	ans = 1
	if k % 2 == 0:
#		print("nega even")
		for l in range(k):
			ans *= sortlst[l]
		
	else:
#		print("nega odd")
		resortlst = sorted(lst, key = abs, reverse = False)
#		print(resortlst)
		ans = 1
		for m in range(k):
			ans *= resortlst[m]

else:
#	print("mix")
	ans = 0
	seki = 1
	for o in range(k):
		seki *= sortlst[o]

	if seki >= 0:
		ans = seki
		
	else:
		if "posi" not in signlst[k : n] and "nega" not in signlst[k : n]:
			ans = seki
			
		else:
			sortlst2 = sorted(sortlst[:k], reverse = True)
			minposi_index = max([i for i in range(k) if sortlst2[i] >= 0])
			kouho1 = seki / sortlst2[minposi_index + 1] * max(sortlst[k : n])
			kouho2 = seki / sortlst2[minposi_index] * min(sortlst[k : n])
			if "nega" not in signlst[k : n]:
				ans = kouho1
				
			elif "posi" not in signlst[k : n]:
				ans = kouho2
				
			else:
				ans = max(kouho1, kouho2)

#print(ans)
print(ans % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
# coding: utf-8
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]
        if ans>0:
            ans=ans%MOD
elif max(A)<0 and K%2==1:
    A.sort(reverse=True)
    for i in range(K):
        ans*=A[i]
        if ans>0:
            ans=ans%MOD
else:
    Ap=[]
    Am=[]
    
    for i in range(N):
        if A[i]>0:
            Ap.append(A[i])
        else:
            Am.append(A[i])
        

    Ap.sort(reverse=True)
    Am.sort()
    
    if K%2==1:
        ans*=Ap.pop(0)
    
    if len(Ap)%2==1:
        Ap.append(1)
    
    P=[]
    
    for i in range(len(Ap)//2):
        P.append(Ap[i*2]*Ap[i*2+1]%MOD)
    
    for i in range(len(Am)//2):
        P.append(Am[i*2]*Am[i*2+1]%MOD)
    
    P.sort(reverse=True)
    
    for i in range(K//2):
        ans*=P[i]
        ans=ans%MOD

print(ans%MOD)

Submission status: Runtime Error

Solution code:
# coding: utf-8
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]
        if ans>0
            ans=ans%MOD
elif max(A)<0 and K%2==1:
    A.sort(reverse=True)
    for i in range(K):
        ans*=A[i]
        if ans>0
            ans=ans%MOD
else:
    Ap=[]
    Am=[]
    
    for i in range(N):
        if A[i]>0:
            Ap.append(A[i])
        else:
            Am.append(A[i])
        

    Ap.sort(reverse=True)
    Am.sort()
    
    if K%2==1:
        ans*=Ap.pop(0)
    
    if len(Ap)%2==1:
        Ap.append(1)
    
    P=[]
    
    for i in range(len(Ap)//2):
        P.append(Ap[i*2]*Ap[i*2+1]%MOD)
    
    for i in range(len(Am)//2):
        P.append(Am[i*2]*Am[i*2+1]%MOD)
    
    P.sort(reverse=True)
    
    for i in range(K//2):
        ans*=P[i]
        ans=ans%MOD

print(ans%MOD)

Submission status: Runtime Error

Solution code:
# coding: utf-8
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=ans%MOD
elif max(A)<0 and K%2==1:
    A.sort(reverse=True)
    for i in range(K):
        ans*=A[i]
        ans=ans%MOD
else:
    Ap=[]
    Am=[]
    
    for i in range(N):
        if A[i]>0:
            Ap.append(A[i])
        else:
            Am.append(A[i])
        

    Ap.sort(reverse=True)
    Am.sort()
    
    if K%2==1:
        ans*=Ap.pop(0)
    
    if len(Ap)%2==1:
        Ap.append(1)
    
    P=[]
    
    for i in range(len(Ap)//2):
        P.append(Ap[i*2]*Ap[i*2+1]%MOD)
    
    for i in range(len(Am)//2):
        P.append(Am[i*2]*Am[i*2+1]%MOD)
    
    P.sort(reverse=True)
    
    for i in range(K//2):
        ans*=P[i]
        ans=ans%MOD

print(ans%MOD)

Submission status: Runtime Error

Solution code:
# coding: utf-8
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
elif max(A)<0 and K%2==1:
    A.sort(reverse=True)
    for i in range(K):
        ans*=A[i]
        ans%MOD
else:
    Ap=[]
    Am=[]
    
    for i in range(N):
        if A[i]>0:
            Ap.append(A[i])
        else:
            Am.append(A[i])
        

    Ap.sort(reverse=True)
    Am.sort()
    
    if K%2==1:
        ans*=Ap.pop(0)
    
    if len(Ap)%2==1:
        Ap.append(1)
    
    P=[]
    
    for i in range(len(Ap)//2):
        P.append(Ap[i*2]*Ap[i*2+1]%MOD)
    
    for i in range(len(Am)//2):
        P.append(Am[i*2]*Am[i*2+1]%MOD)
    
    P.sort(reverse=True)
    
    for i in range(K//2):
        ans*=P[i]
        ans%MOD

print(ans%MOD)

Submission status: Runtime Error

Solution code:
# coding: utf-8
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
elif max(A)<0 and K%2==1:
    A.sort(reverse=True)
    for i in range(K):
        ans*=A[i]
        ans%MOD
else:
    Ap=[]
    Am=[]
    
    for i in range(N):
        if A[i]>0:
            Ap.append(A[i])
        else:
            Am.append(A[i])
        

    Ap.sort(reverse=True)
    Am.sort()
    
    if K%2==1:
        ans*=Ap.pop(0)
    
    if len(Ap)%2==1:
        Ap.append(1)
    
    P=[]
    
    for i in range(len(Ap)//2):
        P.append(Ap[i*2]*Ap[i*2+1])
    
    for i in range(len(Am)//2):
        P.append(Am[i*2]*Am[i*2+1])
    
    P.sort(reverse=True)
    
    for i in range(K//2):
        ans*=P[i]
        ans%MOD

print(ans%MOD)

Submission status: Runtime Error

Solution code:
# coding: utf-8
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]
elif max(A)<0 and K%2==1:
    A.sort(reverse=True)
    for i in range(K):
        ans*=A[i]
else:
    Ap=[]
    Am=[]
    
    for i in range(N):
        if A[i]>0:
            Ap.append(A[i])
        else:
            Am.append(A[i])
        

    Ap.sort(reverse=True)
    Am.sort()
    
    if K%2==1:
        ans*=Ap.pop(0)
    
    if len(Ap)%2==1:
        Ap.append(1)
    
    P=[]
    
    for i in range(len(Ap)//2):
        P.append(Ap[i*2]*Ap[i*2+1])
    
    for i in range(len(Am)//2):
        P.append(Am[i*2]*Am[i*2+1])
    
    P.sort(reverse=True)
    
    for i in range(K//2):
        ans*=P[i]

print(ans%MOD)

Submission status: Runtime Error

Solution code:
import sys
MOD=10**9+7

def moddiv(a,m):
    return pow(a,m-2,m)

def solve():
    res=-10**30
    minus,plus,zero=[],[],[]
    for i in range(N):
        if A[i]<0:
            minus.append(A[i])
        elif A[i]>0:
            plus.append(A[i])
        else:
            zero.append(A[i])
    cump=1
    plus.sort()
    minus.sort()
    for i in range(len(plus)):
        cump=cump*plus[i]%MOD
    j=0
    i=0
    cumm=1
    while(j<=min(len(minus),K)):
        if j>0:
            cumm=cumm*minus[j-1]*minus[j-2]%MOD
            newm=minus[j-1]*minus[j-2]
        isbig=True
        if K-j>len(plus):
            j+=2
            continue
        oldp=1
        while(K-j<len(plus)-i):
            cump=cump*moddiv(plus[i],MOD)%MOD
            if isbig:
                oldp*=plus[i]
            if oldp>newm:
                isbig=False
            i+=1
        if j>0:
            if isbig:
                res=cumm*cump%MOD
        else:
            res=max(res,cumm*cump%MOD)
        j+=2
    if res!=-10**30:
        return res
    if len(zero)>0:
        return 0
    li=minus+plus
    li.sort(key=lambda x:abs(x))
    res=1
    for i in range(K):
        res=res*li[i]%MOD
    return res
N,K=map(int,input().split())
A=list(map(int,input().split()))

if min(A)>=0:
    res=1
    A.sort(reverse=True)
    for i in range(K):
        res=res*A[i]%MOD
elif max(A)<=0:
    res=1
    if not K%2:
        A.sort()
        for i in range(K):
            res=res*A[i]%MOD
    else:
        A.sort(reverse=True)
        for i in range(K):
            res=res*A[i]%MOD
else:
    res=solve()
print(res)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
MOD=10**9+7

def moddiv(a,m):
    return pow(a,m-2,m)

def solve():
    res=-10**30
    minus,plus,zero=[],[],[]
    for i in range(N):
        if A[i]<0:
            minus.append(A[i])
        elif A[i]>0:
            plus.append(A[i])
        else:
            zero.append(A[i])
    cump=1
    plus.sort()
    minus.sort()
    for i in range(len(plus)):
        cump=cump*plus[i]%MOD
    j=0
    i=0
    cumm=1
    while(j<=min(len(minus),K)):
        if j>0:
            cumm=cumm*minus[j-1]%MOD*minus[j-2]%MOD
            newm=minus[j-1]*minus[j-2]
        isbig=True
        if K-j>len(plus):
            j+=2
            continue
        oldp=1
        while(K-j<len(plus)-i):
            cump=cump*moddiv(plus[i],MOD)%MOD
            if isbig:
                oldp*=plus[i]
            if oldp>newm:
                isbig=False
            i+=1
        if j>0:
            if isbig:
                res=cumm*cump%MOD
        else:
            res=max(res,cumm*cump%MOD)
        j+=2
    if res!=-10**30:
        return res
    if len(zero)>0:
        return 0
    li=minus+plus
    li.sort(key=lambda x:abs(x))
    res=1
    for i in range(K):
        res=res*li[i]%MOD
    return res
N,K=map(int,input().split())
A=list(map(int,input().split()))

if min(A)>=0:
    res=1
    A.sort(reverse=True)
    for i in range(K):
        res=res*A[i]%MOD
elif max(A)<=0:
    res=1
    if not K%2:
        A.sort()
        for i in range(K):
            res=res*A[i]%MOD
    else:
        A.sort(reverse=True)
        for i in range(K):
            res=res*A[i]%MOD
else:
    res=solve()
print(res)

Submission status: Runtime Error

Solution code:
def solve(ls, k, debug=0):
    modulo = 10 ** 9 + 7
    n = len(ls)
    n_neg = 0
    for i in range(n):
        n_neg += ls[i] < 0
    n_pos = n - n_neg

    # Sort by abs
    ls_abs = [abs(x) for x in ls]
    ls_abs_argsort = sorted(list(range(n)), key=lambda i: -ls_abs[i])

    # Check if positive result is impossible
    l = min(k, n_neg) # consider if we pick as many negatives as possible
    nagative = l % 2 and n_pos <= max(0, k - n_neg)

    # If positive impossible, pick smaller ones
    if nagative:
        p = 1
        for i in range(k):
            x = ls[ls_abs_argsort[-1 - i]]
            p *= x
            p %= modulo
        return p

    # If positive possible, ...

    # Check sign when we pick "abs" large ones
    s = 1
    for i in range(k):
        x = ls[ls_abs_argsort[i]]
        s *= -1 if x < 0 else 1

    # If non-negative, we take as it is
    if s > 0:
        p = 1
        for i in range(k):
            x = ls[ls_abs_argsort[i]]
            p *= x
            p %= modulo
        return p

    # If negative, replace small negative with large positive
    swap_pos = None
    for i in range(k, n):
        if ls[ls_abs_argsort[i]] >= 0:
            swap_pos = i
            break

    swap_neg = None
    for i in range(k)[::-1]:
        if ls[ls_abs_argsort[i]] < 0:
            swap_neg = i
            break

    p = 1
    p *= ls[ls_abs_argsort[swap_pos]]
    p %= modulo
    for i in range(k):
        if i == swap_neg:
            continue
        x = ls[ls_abs_argsort[i]]
        p *= x
        p %= modulo
    return p


def main(istr, ostr):
    n, k = list(map(int, istr.readline().strip().split()))
    ls = list(map(int, istr.readline().strip().split()))
    result = solve(ls, k)
    print(result, file=ostr)


if __name__ == "__main__":
    import sys

    main(sys.stdin, sys.stdout)

Submission status: Runtime Error

Solution code:
def solve(ls, k, debug=0):
    modulo = 10 ** 9 + 7
    n = len(ls)
    n_neg = 0
    for i in range(n):
        n_neg += ls[i] < 0
    n_pos = n - n_neg

    # Sort by abs
    ls_abs = [abs(x) for x in ls]
    ls_abs_argsort = sorted(list(range(n)), key=lambda i: -ls_abs[i])

    # Check if positive result is impossible
    l = min(k, n_neg)
    positive = n_pos > max(0, k - n_neg)

    # If positive impossible, pick smaller ones
    if not positive:
        p = 1
        for i in range(k):
            x = ls[ls_abs_argsort[-1 - i]]
            p *= x
            p %= modulo
        return p

    # If positive possible, ...

    # Check sign when we pick "abs" large ones
    s = 1
    for i in range(k):
        x = ls[ls_abs_argsort[i]]
        s *= -1 if x < 0 else 1

    # If non-negative, we take as it is
    if s > 0:
        p = 1
        for i in range(k):
            x = ls[ls_abs_argsort[i]]
            p *= x
            p %= modulo
        return p

    # If negative, replace small negative with large positive
    swap_pos = None
    for i in range(k, n):
        if ls[ls_abs_argsort[i]] >= 0:
            swap_pos = i
            break

    swap_neg = None
    for i in range(k)[::-1]:
        if ls[ls_abs_argsort[i]] < 0:
            swap_neg = i
            break

    p = 1
    p *= ls[ls_abs_argsort[swap_pos]]
    p %= modulo
    for i in range(k):
        if i == swap_neg:
            continue
        x = ls[ls_abs_argsort[i]]
        p *= x
        p %= modulo
    return p


def main(istr, ostr):
    n, k = list(map(int, istr.readline().strip().split()))
    ls = list(map(int, istr.readline().strip().split()))
    result = solve(ls, k)
    print(result, file=ostr)


if __name__ == "__main__":
    import sys

    main(sys.stdin, sys.stdout)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A_p = []
A_m = []
A = []
a, *an = map(float, input().split())
A.append(a)
A += an

A_sort = sorted(A, key=lambda x: abs(x), reverse = True)
#print(A_sort)

for a in A:
    if a < 0:
        A_m.append(a)
    else:
        A_p.append(a)
A_p.sort()
A_p.reverse()
A_m.sort()
#print(A_p)
#print(A_m)

m = 0
dot = 1
m_id = 0
p_id = 0
        
for k in range(K):
    if A_sort[k] < 0:
        m_id += 1
    else:
        p_id += 1
    dot = dot*A_sort[k]
    
#print(m_id, p_id)

f1 = False
f2 = False

if m_id % 2 == 1:
    if p_id + 1 <= len(A_p):
        f1 = True
        dot2 = dot / A_m[m_id-1]
        dot2 = dot2 * A_p[p_id]
    
    if m_id + 1 <= len(A_m) and len(A_p) > 0:
        f2 = True
        dot3 = dot / A_p[p_id-1]
        dot3 = dot3 * A_m[m_id]
        
    if f1 == False and f2 == False:
        #print("CANT")
        dot = 1
        A_m.reverse()
        for k in range(K):
            dot = dot * A_m[k]

    if f1 and f2:
        if dot3 > dot2:
            print(int(dot3 % 1000000007))
        else:
            print(int(dot2 % 1000000007))
    elif f1:
        print(int(dot2 % 1000000007))
    elif f2:
        print(int(dot3 % 1000000007))
    else:
        #print("Yes",str(dot))
        print(int(dot % 1000000007))
else:
    #print(dot)
    print(int(dot % 1000000007))

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A_p = []
A_m = []
A = []
a, *an = map(float, input().split())
A.append(a)
A += an

A_sort = sorted(A, key=lambda x: abs(x), reverse = True)
#print(A_sort)

for a in A:
    if a < 0:
        A_m.append(a)
    else:
        A_p.append(a)
A_p.sort()
A_p.reverse()
A_m.sort()
#print(A_p)
#print(A_m)

m = 0
dot = 1
m_id = 0
p_id = 0
        
for k in range(K):
    if A_sort[k] < 0:
        m_id += 1
    else:
        p_id += 1
    dot = dot*A_sort[k]
    
#print(m_id, p_id)

f1 = False
f2 = False

if m_id % 2 == 1:
    if p_id + 1 <= len(A_p):
        f1 = True
        dot2 = dot / A_m[m_id-1]
        dot2 = dot2 * A_p[p_id]
    
    elif m_id + 1 <= len(A_m) and len(A_p) > 0:
        f2 = True
        dot3 = dot / A_p[p_id-1]
        dot3 = dot3 * A_m[m_id]
    else:
        #print("CANT")
        dot = 1
        A_m.reverse()
        for k in range(K):
            dot = dot * A_m[k]

    if f1 and f2:
        if dot3 > dot2:
            print(int(dot3 % 1000000007))
        else:
            print(int(dot2 % 1000000007))
    elif f1:
        print(int(dot2 % 1000000007))
    elif f2:
        print(int(dot3 % 1000000007))
    else:
        #print("Yes",str(dot))
        print(int(dot % 1000000007))
else:
    #print(dot)
    print(int(dot % 1000000007))

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A_p = []
A_m = []
A = []
a, *an = map(float, input().split())
A.append(a)
A += an

A_sort = sorted(A, key=lambda x: abs(x), reverse = True)
#print(A_sort)

for a in A:
    if a < 0:
        A_m.append(a)
    else:
        A_p.append(a)
A_p.sort()
A_p.reverse()
A_m.sort()
#print(A_p)
#print(A_m)

m = 0
dot = 1
m_id = 0
p_id = 0
        
for k in range(K):
    if A_sort[k] < 0:
        m_id += 1
    else:
        p_id += 1
    dot = dot*A_sort[k]
    
#print(m_id, p_id)

f1 = False
f2 = False

if m_id % 2 == 1:
    if p_id + 1 <= len(A_p):
        f1 = True
        dot2 = dot / A_m[m_id-1]
        dot2 = dot2 * A_p[p_id]
    
    elif m_id + 1 <= len(A_m) and len(A_p) > 0:
        f2 = True
        dot3 = dot / A_p[p_id-1]
        dot3 = dot3 * A_m[m_id]
    else:
        #print("CANT")
        dot = 1
        A_m.reverse()
        for k in range(K):
            dot = dot * A_m[k]

    if f1 and f2:
        if dot3 > dot2:
            print(int(dot3 % 1000000007))
        else:
            print(int(dot2 % 1000000007))
    elif f1:
        print(int(dot2 % 1000000007))
    elif f2:
        print(int(dot3 % 1000000007))
    els3e:
        #print("Yes",str(dot))
        print(int(dot % 1000000007))
else:
    #print(dot)
    print(int(dot % 1000000007))

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A_p = []
A_m = []
A = []
a, *an = map(float, input().split())
A.append(a)
A += an

A_sort = sorted(A, key=lambda x: abs(x), reverse = True)
#print(A_sort)

for a in A:
    if a < 0:
        A_m.append(a)
    else:
        A_p.append(a)
A_p.sort()
A_p.reverse()
A_m.sort()
#print(A_p)
#print(A_m)

m = 0
dot = 1
m_id = 0
p_id = 0
        
for k in range(K):
    if A_sort[k] < 0:
        m_id += 1
    else:
        p_id += 1
    dot = dot*A_sort[k]
    
#print(m_id, p_id)

f1 = False
f2 = False

if m_id % 2 == 1:
    if p_id + 1 <= len(A_p):
        f1 = True
        dot2 = dot / A_m[m_id-1]
        dot2 = dot2 * A_p[p_id]
    
    elif m_id + 1 <= len(A_m) and len(A_p) > 0:
        f2 = True
        dot3 = dot / A_p[p_id-1]
        dot3 = dot3 * A_m[m_id]
    else:
        #print("CANT")
        dot = 1
        A_m.reverse()
        for k in range(K):
            dot = dot * A_m[k]

    if f1 and f2:
        if dot3 > dot2:
            print(int(dot3 % 1000000007))
        else:
            print(int(dot2 % 1000000007))
    elif f1:
        print(int(dot2 % 1000000007))
    elif f2:
        print(int(dot3 % 1000000007))
    els3e:
        print("Yes",str(dot))
        print(int(dot % 1000000007))
else:
    #print(dot)
    print(int(dot % 1000000007))

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

n_k = list(map(int, input().split()))
n = n_k[0]
k = n_k[1]
a = list(map(int, input().split()))
a_pos = list(filter(lambda v: v >= 0, a))
a_neg = list(filter(lambda v: v < 0, a))

a_pos.sort(reverse=True)
a_neg.sort()

mod = 10**9+7

ans = 1
if n == k:
    for a_i in a:
        ans = ans * a_i % mod
elif len(a_pos) == 0 and k % 2 == 1:
    for i in reversed(range(len(a_neg) - k, len(a_neg))):
        ans = ans * a_neg[i] % mod
else:
    i_p = 0
    i_n = 0
    i = 0
    while i < k:
        if i_p < k and (i == k - 1 or i_n+1 >= len(a_neg) or a_pos[i_p] * (a_pos[i_p+1] if i_p+1 < len(a_pos) else 1) > a_neg[i_n] * a_neg[i_n+1]):
            ans = ans * a_pos[i_p] % mod
            i_p += 1
            i += 1
        else:
            ans = ans * a_neg[i_n] % mod * a_neg[i_n+1] % mod
            i_n += 2
            i += 2
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from functools import reduce

mod = 10**9 + 7
n, k, *a = map(int, open(0).read().split())
a.sort(key=lambda x: abs(x))
ans = reduce(lambda a, b: (a * b) % mod, a[-k:])

c = a[-k:]
j = sum(i < 0 for i in c) % 2
if j:
    c = a[-k:]
    neg = [i for i in c if i < 0]
    pos = [i for i in c if i > 0]
    b = sorted(a[:n - k])
    if 0 >= b[-1] / neg[0] > b[0] / pos[0]:
        ans = ans * pow(neg[0], mod - 2, mod) * b[-1] % mod
    elif b[-1] / neg[0] <= 0:
        ans = ans * pow(pos[0], mod - 2, mod) * b[0] % mod
    else:
        ans = reduce(lambda a, b: (a * b) % mod, a[:k])
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from functools import reduce

mod = 10**9 + 7
n, k, *a = map(int, open(0).read().split())
a.sort(key=lambda x: abs(x))
ans = reduce(lambda a, b: (a * b) % mod, a[-k:])

c = a[-k:]
j = sum(i < 0 for i in c) % 2
if j:
    c = a[-k:]
    neg = [i for i in c if i < 0]
    pos = [i for i in c if i > 0]
    b = sorted(a[:n - k])
    if 0 >= b[-1] / neg[0] > b[0] / pos[0]:
        ans = ans * pow(pos[0], mod - 2, mod) * b[0] % mod
    elif b[-1] / neg[0] <= 0:
        ans = ans * pow(pos[0], mod - 2, mod) * b[0] % mod
    else:
        ans = reduce(lambda a, b: (a * b) % mod, a[:k])
print(ans)