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:
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, k = MAP()
a = sorted(LIST())

if k == 1:
    ans = a[n-1]
elif k % 2 == 0:
    b = sorted([abs(a[i]) for i in range(n)], reverse=True)
    ans = 1
    for i in range(k):
        ans = ( ans * b[i] ) % (10**9+7)
else:
    if a[n-1] == 0:
        ans = 0
    elif a[n-1] < 0:
        ans = 1
        for i in range(k):
            ans = ( ans * a[n-1-i] ) % (10**9+7)
    else:
        ans = 1
        for i in range(k):
            ans = ( ans * a[n-1-i] ) % (10**9+7)
            ans = min(0, ans % (10**9+7))
        for i in range(1,k,1):
            ans = max(ans, ans//a[n-k+i-2]//a[n-k+i-1]*a[i-2]*a[i-1])
            ans = min(0, ans % (10**9+7))
        ans = ans % (10**9+7)
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    n,k = map(int,input().split())
    A = list(map(int,input().split()))

    MOD = 10**9 + 7

    absA = [abs(a) for a in A]
    flg = 0
    m = []
    p = []
    dict = []
    T = []
    for i in A:
        if i < 0:
            m.append(i)
            T.append(tuple([abs(i),-1]))
        elif i > 0:
            p.append(i)
            T.append(tuple([abs(i),1]))
        else:
            flg = 1

    T.sort(reverse=True)


    ans = T[:k]
    c = 0
    for i in ans:
        if i[1] == -1:
            c += 1

    if c % 2 == 0:
        l = 1
        for i in ans:
            l *= i[0]
            l %= MOD
        print(l)

    else:
        flg_1,flg_2 = 0,0
        for j in range(k-1,-1,-1):
            if T[j][1] == -1:
                flg_1 = 1
                min_m = T[j][0]
                break

        for j in range(k,len(T)):
            if T[j][1] == 1:
                flg_2 ^= 1
                # print('AaA')
                max_p = T[j][0]
                break

        # print(min_m,max_p)

        if flg_1 and flg_2:
            flg = 1
        else:
            flg = 0

        flg_1,flg_2 = 0,0

        for j in range(k-1,-1,-1):
            if T[j][1] == 1:
                flg_1 = 1
                min_p = T[j][0]
                break
        
        for j in range(k,len(T)):
            if T[j][1] == -1:
                flg_2 = 1
                max_m = T[j][0]
                break

        if flg_1 and flg_2:
            flg2 = 1
        else:
            flg2 = 0


        l = 1
        for i in ans:
            l *= abs(i[0])
            l %= MOD 

        # print(l)

        if flg == 1 and flg2 == 1:
            if min_p * max_p >= min_m * max_m:
                l *= max_p
                l *= pow(min_m,MOD-2,MOD)
            else:
                l *= max_m
                l *= pow(min_p,MOD-2,MOD)
        elif flg == 1:
                l *= max_p
                l *= pow(min_m,MOD-2,MOD)
        elif flg2 == 1:
                l *= max_m
                l *= pow(min_p,MOD-2,MOD)
        else:
            if 0 in A:
                l = 0
            else:
                A.sort(reverse=True)
                l = 1
                for i in range(k):
                    l *= A[i]
                    l %= MOD
                print(l)
                exit()

            
        print(l%MOD)




    

            

main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right

mod = 10 ** 9 + 7
n, k = map(int, input().split())
A = list(map(int, input().split()))
# dp = [[[0] * (2) for _ in range(k+1)]for _ in range(n+1)]
# # dp[桁][数][負数の数=1,0]

A.sort()
n_minus = bisect_left(A, 0)
n_zero = bisect_right(A, 0) - n_minus
n_plus = n - n_minus - n_zero

possible_max = min(k, n_minus)
possible_min = max(k - (n_plus + n_zero), 0)
ans = 1
if possible_max == possible_min and possible_min % 2 == 1:
    if k - (possible_min) > 0 and n_zero > 0:
        print(0)
        exit()
    A_plus = A[n - (n_plus) :]
    A_minus = A[:n_minus]
    A_minus.sort(reverse=True)
    # 負の数は奇数個小さい方から選ぶ
    for i in range(possible_min):
        ans *= A_minus[i]
        ans %= mod
    for i in range(k - possible_min):
        ans *= A_plus[i]
        ans %= mod
else:
    # 正の数に成る→大きいものがほしい
    # 負の数は偶数個、これの数を決め打つ
    # 計算すると大変だから大小を考える

    A_plus = A[n - (n_plus) :]
    A_plus.sort(reverse=True)
    A_minus = A[:n_minus]

    # 負の数を使う数を決め打つ
    # 最終的に正にできるパターン
    minus_num_max = min(n_minus // 2, k // 2)
    select = k - 2 * minus_num_max
    if n_plus < select:
        print(0)
        exit()
    # 負の数にしかできないパターン
    # 遊びがない時に奇数個の負の数を選ばざるを得ない
    # その時に0があるかどうかパターン
    kouho = []
    for i in range(minus_num_max):
        if 2 * i + 1 >= n_minus:
            break
        temp = A_minus[2 * i] * A_minus[2 * i + 1]
        kouho.append((temp, -1))
    for i in range(n_plus // 2):
        temp = A_plus[2 * i] * A_plus[2 * i + 1]
        kouho.append((temp, +1))
    kouho.sort(reverse=True)
    if k % 2 == 0:
        for i in range(k // 2):
            ans *= kouho[i][0]
            ans %= mod
    else:
        cnt = 0
        i = 0
        for i in range(k // 2):
            num, f = kouho[i]
            if f == 1:
                cnt += 1
            ans *= num
            ans %= mod
        ans *= A_plus[2 * i]
        ans %= mod


print(ans)

Submission status: Runtime Error

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

l_pos=[]
l_neg=[]
for i in range(n):
  if l[i]<0:
    l_neg.append(l[i])
  else:
    l_pos.append(l[i])

l_neg.sort()
l_pos.sort()
a=len(l_neg)
b=len(l_pos)
a=a-1
b=b-1

if len(a)==0:
  ans=1
  for i in range(k):
    ans*=l_pos[-1-i]
    ans=ans%mod

elif len(b)==0:
  ans=1
  for j in range(k):
    ans*=l_neg[i]
    ans=ans%mod

elif k==n:
  ans=1
  for i in range(n):
    ans*=l[i]
    ans=ans%mod

else:
  ans=1
  cntodd=0
  while a>0 and b>0:
    if l_pos[b]>=abs(l_neg[a]):
      ans*=l_pos[b]
      ans=ans%mod
      b-=1
    
    elif l_pos[b]<abs(l_neg[a]):
      ans*=l_pos[b]
      ans=ans%mod
      a-=1
      cntodd+=1
    k-=1
    if k==1:
      break

  if cntodd%2==0 and k==1:
    ans*=l_pos[b]
    k-=1
  elif cntodd%2!=0 and k==1:
    if b+1<len(l_neg):
      b+=1
    ans=ans//l_neg[b]
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

N, K = map(int, input().split())
a_list = list(map(int, input().split()))
a_list = deque(sorted(a_list))
MOD = 10**9 + 7
 
 
def choose1():
    l = 1
    if a_list[-1]*a_list[-2] >= a_list[0]*a_list[1]:
        l *= a_list.popleft()
        l *= a_list.popleft()
    else:
        l *= a_list.pop()
        l *= a_list.pop()
    return l % MOD

def choose2():
    l = 1
    if a_list[-1]*a_list[-2] >= a_list[0]*a_list[1]:
        l *= a_list.pop()
        l *= a_list.pop()
    else:
        l *= a_list.popleft()
        l *= a_list.popleft()
    return l % MOD
 
 
ans = 1
if K == 1:
    print(a_list[-1]%MOD)
    exit()
else:
    if K % 2 == 0:
        for _ in range(K//2):
            ans *= choose2()
    else:
        ans *= a_list.pop(-1)
        if ans < 0:
            for _ in range((K-1)//2):
                ans *= choose1()
        else:
            for _ in range((K-1)//2):
                ans *= choose2()
 
print(ans%MOD)

Submission status: Runtime Error

Solution code:
M = 1000000007
n, k = map(int, input().split())
l = list(map(int, input().split()))
pos = []
neg = []
zero = []
for i in l:
    if i > 0: pos.append(i)
    if i < 0: neg.append(i)
    if i == 0: zero.append(i)
pos.sort(reverse = True)
neg.sort()

check = 0
if k % 2 == 1:
    check = 1
    k -= 3

p1, p2 = 0, 0
n1, n2 = len(pos), len(neg)

ans = 1
ch1, ch2 = 1, 1
while 1:
    if k == 0: break
    
    if p1 + 1 >= n1: ch1 = 0 
    if p2 + 1 >= n2: ch2 = 0
    
    if ch1 and ch2:
        k -= 2
        t1 = pos[p1] * pos[p1 + 1]
        t2 = neg[p2] * neg[p2 + 1]
        if t1 >= t2:
            p1 += 2
            ans = (ans * t1) % M
        else:
            p2 += 2
            ans = (ans * t2) % M
    elif ch1:
        k -= 2
        t1 = pos[p1] * pos[p1 + 1]
        ans = (ans * t1) % M
        p1 += 2
    elif ch2:
        k -= 2
        t2 = neg[p2] * neg[p2 + 1]
        ans = (ans * t2) % M
        p2 += 2
    else: break

if k != 0:
    if p1 + 1 >= n1 and p2 + 1 >= n2:
        ans = (ans * pos[p1]) % M
        ans = (ans * neg[p2]) % M
else:
    ch1, ch2 = 1, 1
    if check:
        if p1 + 2 >= n1: ch1 = 0 
        if p2 + 1 >= n2: ch2 = 0
        
        if ch1 and ch2:
            t1 = pos[p1] * pos[p1 + 1] * pos[p1 + 2]
            t2 = neg[p2] * neg[p2 + 1] * pos[p1]
            if t1 >= t2:
                ans = (ans * t1) % M
            else:
                ans = (ans * t2) % M
        elif ch1:
            t1 = pos[p1] * pos[p1 + 1] * pos[p1 + 2]
            ans = (ans * t1) % M
        elif ch2:
            if p1 < n:
                t2 = neg[p2] * neg[p2 + 1] * pos[p1]
                ans = (ans * t2) % M
            else:
                if len(zero) > 0: ans = 0
                else:
                    tmp = []
                    for i in range(n):
                        if l[i] >= 0: tmp.append(l[i], 1)
                        else: tmp.append(-l[i], 0)
                    tmp.sort()
                    Ans = 1
                    for i in range(k):
                        if tmp[i][1] == 1: Ans = (Ans * tmp[i][0]) % M
                        else: Ans = (Ans * tmp[i][0] * -1) % M
                    ans = Ans
        else:
            if len(zero) > 0: ans = 0
            else:
                t2 = neg[p2] * pos[p1] * pos[p1 + 1]
                ans = (ans * t2) % M
print(ans)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 1
pls = 1
mod = 10**9+7
a_minu = [i for i in a if i <0]
if k==len(a):
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)

elif len(a_minu)==len(a) and k%2==1:
    a.sort(reverse=True)
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)

else:
    alis = []
    lasim = -1
    lasip = -1
    for i in a:
        if i<0:
            alis.append([-i,-1])
        else:
            alis.append([i,1])
    alis.sort(key=lambda x:x[0], reverse=True)
    for i in range(k):
        if alis[i][1]==-1:
            lasim =  i
        else:
            lasip = i
        ans *= alis[i][0]
        ans %= mod
        pls *= alis[i][1]
    if pls ==1:
        print(ans)
    else:
        ju= 0
        jud = 0
        if lasim >= 0:
            tmp = ans*pow(alis[lasim][0],mod-2,mod)
            for i in range(lasim+1,n):
                if alis[i][1]==-1:
                    continue
                else:
                    tmp *= alis[i][0]
                    ju = 1
                    break
            if ju==0:
                tmp = 0
        if lasip >= 0:
            tmp2 = ans*pow(alis[lasip][0],mod-2,mod)
            for i in range(lasip+1,n):
                if alis[i][1]==1:
                    continue
                else:
                    tmp2 *= alis[i][0]
                    jud = 1
                    break
            if jud==0:
                tmp2 = 0
        if tmp2>=tmp:
            print(tmp2%mod)
        else:
            print(tmp%mod)

Submission status: Runtime Error

Solution code:
import bisect
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]

rrn = lambda n: [ rr() for _ in xrange(n)]
MOD = 10**9+7
N, K = rrm()
arr = rrm()
def solve(N, K, arr):
    if N ==K:
        ans = arr[0]
        for i in range(1, N):
            ans*= arr[i] %MOD
        return ans %MOD
    neg, pos = [], []
    has = False
    for num in arr:
        if num<0:
            neg.append(num)
        elif num>0:
            pos.append(num)
        else:
            has = True
    neg = sorted(neg)
    pos = sorted(pos)
    pos_prefix = [1]
    for i in range(len(pos)-1, -1, -1):
        pos_prefix.append(pos_prefix[-1]*pos[i] %MOD)
    neg_prefix = [1]
    for i in range(len(neg)):
        neg_prefix.append(neg_prefix[-1]*neg[i] %MOD)
    if has:
        ans = 0
    neg_len = min(K-K%2, len(neg)-len(neg)%2)
    ans = float('-inf')
    for i in range(0, neg_len+2, 2):
        pre = neg_prefix[i]
        need = K-i
        if need<=len(pos):
            after = pos_prefix[need]
            ans = max(ans, pre*after%MOD)
    if ans > float('-inf'):
        return ans
    else:
        neg_len = min(len(neg), K)
        ans = 1
        for i in range(1, neg_len+1):
            ans*=neg[-i]%MOD
        if neg_len<K:
            for i in range(1, K-neg_len+1):
                ans *= pos[i]%MOD
        return ans
            
        
print(solve(N,K, arr) % (10**9+7))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

mod = int(10e8+7)

n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))

a_ = np.abs(a)
isN = (a!=a_).astype(int)

a = a[np.argsort(a_)[::-1]]
isN = isN[np.argsort(a_)[::-1]]
a_ = np.sort(a_)[::-1]

numN = np.sum(isN)
numP = n-numN

if k==1:
    print(np.max(a))
    sys.exit()

if np.sum(isN[:k])%2==0:
    k = isP
    ans = 1
    for i in range(k):
        ans *= a_[i]
        ans %= mod
    print(int(ans))
    sys.exit()

if not numP:
    ans = 1
    for i in range(1, k+1)[::-1]:
        ans *= -a_[-i]
        ans %= mod

    print(int(ans))
    sys.exit()

maxN = 0
maxP = 0

for i in range(k, n):
    if isN[i]:
        maxN = i
        break

for i in range(k, n):
    if not isN[i]:
        maxP = i
        break

minN = n
minP = n

for i in range(k)[::-1]:
    if isN[i]:
        minN = i
        break

for i in range(k)[::-1]:
    if not isN[i]:
        minP = i
        break

ans_1 = 1

for i in range(k):
    if i == minP:
        if maxN:
            ans_1 *= a_[maxN]
            ans_1 %= mod
        continue

    ans_1 *= a_[i]
    ans_1 %= mod

ans_2 = 1

for i in range(k):
    if i == minN:
        if maxP:
            ans_2 *= a_[maxP]
            ans_2 %= mod
        continue

    ans_2 *= a_[i]
    ans_2 %= mod

print(int(max(ans_1, ans_2)))

Submission status: Runtime Error

Solution code:
def mergesort(l):
    n = len(l)
    if(n == 0):
        return 0
    elif(n == 1):
        return l
    elif(n <= 2):
        if(l[0] > l[1]):
            return [l[1],l[0]]
        else:
            return l
    else:
        tmp1 = mergesort(l[:n//2])
        tmp2 = mergesort(l[n//2:])
        x = n//2
        y = n-x
        l = []
        for i in range(n):
            if(tmp1[-x] < tmp2[-y]):
                l.append(tmp1[-x])
                x -= 1
            else:
                l.append(tmp2[-y])
                y -= 1
            if(x*y == 0):
                if(x == 0):
                    l += tmp2[-y:]
                else:
                    l += tmp1[-x:]
                break
        return l
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = []
c = []
s,t,u = 0,0,0
for i in range(n):
    if(a[i] < 0):
        t += 1
        c.append(a[i])
    else:
        s += 1
        b.append(a[i])
b = mergesort(b)
c = mergesort(c)
p = 1
if(s == 0 and k%2 == 1):
    for i in range(1,k+1):
        p *= c[-i]
        p %= 1000000007
else:
    if(k%2 == 1):
        s-=1
        p = b[s]
        k -= 1
    while(k>0):
        if(s > 0 and t > u):
            if(b[s-1]*b[s-2] > c[u]*c[u+1]):
                p *= b[s-1]*b[s-2]
                p %= 1000000007
                s -= 2
            else:
                p *= c[u]*c[u+1]
                p %= 1000000007
                u += 2
        elif(s == 0):
            p *= c[u]*c[u+1]
            p %= 1000000007
            u += 2
        else:
            p *= b[s-1]*b[s-2]
            p %= 1000000007
            s -= 2
        k -= 2
print(p)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
m = 10**9+7
p = []
q = []
r = []
for i in range(N):
    if A[i] > 0:
        p.append(A[i])
    elif A[i] < 0:
        q.append(A[i])
    else:
        r.append(A[i])
p.sort()
q.sort()
P = len(p)
Q = len(q)
if P+Q < K:
    print(0)
    exit()
if P > 0:
    if P+Q == K:
        ans = 1
        for i in range(P):
            ans = ans * p[i] % m
        for i in range(Q):
            ans = ans * q[i] % m
        print(ans)
    else:
        i = K
        j = 0
        while i > P:
            i -= 2
            j += 2
            
        while i >= 1 and j < Q-1:
            if p[P-i]*p[P-i+1] < q[Q-j-1]*q[Q-j-2]:
                if i-2 >= 1:
                    i -= 2
                j += 2
            else:
                break
        ans = 1
        for k in range(max(0,i)):
            ans = ans * p[P-k-1] % m
        for l in range(min(Q,j)):
            ans = ans * q[Q-l-1] % m
        print(ans)
else:
    if K % 2 == 0:
        if Q >= K:
            ans = 1
            for i in range(K):
                ans = ans * q[Q-1-i] % m
            print(ans)
        else:
            print(0)
    else:
        if len(r) > 0:
            print(0)
        else:
            ans = 1
            for i in range(K):
                ans = ans * q[Q-1-i] % m
            print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    A_neg = [a for a in A if a < 0]
    A_zero = [a for a in A if a == 0]
    A_pos = [a for a in A if a > 0]

    A_neg.sort(reverse=True)
    A_pos.sort()

    if K > len(A_neg) + len(A_pos):
        print(0)
        return
    elif len(A_pos) == 0:
        if len(A_zero) > 0:
            print(0)
            return
        elif K % 2:
            ans = 1
            for a in A_neg[:K]:
                ans = (ans * a) % MOD
            print(ans)
            return
        else:
            ans = 1
            for a in A_neg[-K:]:
                ans = (ans * a) % MOD
            print(ans)
            return

    tmp_pos = []
    tmp_neg = []

    ans = 1
    neg = 0
    for i in range(K):
        if not A_neg:
            tmp_pos.append(A_pos[-1])
            ans = ans * A_pos.pop() % MOD
        elif not A_pos:
            tmp_neg.append(A_neg[-1])
            ans = ans * A_neg.pop() % MOD
            neg = 1 - neg
        elif -A_neg[-1] > A_pos[-1]:
            tmp_neg.append(A_neg[-1])
            ans = ans * A_neg.pop() % MOD
            neg = 1 - neg
        else:
            tmp_pos.append(A_pos[-1])
            ans = ans * A_pos.pop() % MOD

    if neg:
        if A_pos:
            ans = ans * pow(tmp_neg[-1], MOD - 2, MOD) * A_pos.pop() % MOD
        else:
            ans = ans * pow(tmp_pos[-1], MOD - 2, MOD) * A_neg.pop() % MOD

    print(ans % MOD)

    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m



n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

table = [[]]

count = 0
for i in range(n):
    table[i].append(abs(a[i]))
    if(a[i] >= 0):
        temp = 1
        count += 1
    else:
        temp = -1
    table[i].append(temp)
    if(i < n - 1):
        table.append([])

table.sort(reverse = True)

kotae = 1
seifu = 1
for i in range(k):
    kotae = kotae * table[i][0] * table[i][1] % MOD
    seifu = seifu * table[i][1]

if(n == k):
    print(kotae)
else:
    temp = 0.0
    temp2 = 0.0
    flag = 0

    if(seifu < 0):
        for i in range(k, n):
            if (table[k-1][1] != table[i][1]):
                temp = table[i][0] / table[k-1][0]
                flag = 1
                break

        for j in reversed(range(k)):
            if(table[k][1] != table[j][1]):
                temp2 = table[k][0] / table[j][0]
                flag = 1
                break

        if(flag == 1):
            irekae = []
            if(temp >= temp2):
                irekae.append(k-1)
                irekae.append(i)
            else:
                irekae.append(j)
                irekae.append(k)
            kotae = kotae * table[irekae[1]][0] * table[irekae[1]][1] % MOD
            kotae = kotae * mod_inv(table[irekae[0]][0] * table[irekae[0]][1], MOD) % MOD
        else:
            table.sort()
            kotae = 1
            for i in range(k):
                kotae = kotae * table[i][0] * table[i][1] % MOD

    print(kotae)

Submission status: Runtime Error

Solution code:
#: Author - Soumya Saurav
import sys,io,os,time
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

input = sys.stdin.readline

########################################
n , k = map(int , input().split())
kk = k-1
arr = list(map(int , input().split()))
mod = 10**9 + 7
poss = 0
neg = 0
for i in range(n):
	if arr[i] < 0:
		neg+=1
	else:
		poss+=1
if neg == n:
	ans = 1
	arr.sort(key = lambda x : abs(x))
	for i in range(k):
		ans*=arr[i]
		ans%=mod
		#print(arr[i])
	print(ans%mod)
	exit()
if poss == n:
	ans = 1
	arr.sort(reverse=True)
	for i in range(k):
		ans*=arr[i]
		ans%=mod
	print(ans)
	exit()
arr.sort(key = lambda x : abs(x), reverse=True)
#print(arr)
ptr = 1
ans = 1
sign = 0 if arr[0] < 0 else 1
#1 +ve and 0 is -ve

while kk:
	temp = 0 if arr[ptr] < 0 else 1
	sign = not(sign^temp)
	ptr+=1
	kk-=1
if sign:
	ans = 1
	for i in range(k):
		ans*=abs(arr[i])
		ans=ans%mod
	print(ans%mod)
else:
	tt = None
	gg = arr[ptr-1]
	while ptr < n:
		temp = 0 if arr[ptr] < 0 else 1
		if temp:
			tt = arr[ptr]
			break
		ptr+=1
	ans = 1
	for i in range(k):
		ans*=i
		ans%=mod
	if tt == None:
		print(mod%mod)
	else:
		print((ans*tt//gg)%mod)

Submission status: Runtime Error

Solution code:

n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
m=[]
p=[]

for i in range(n):
    if a[i]<0:
        m.append(a[i])
    else:
        p.append(a[i])
m.sort(reverse=True)
p.sort()
ans=1

if len(m)==n and k%2==1:
    for i in range(k):
        ans*=m[i]
        ans%=mod

elif k==1:
    ans=p[-1]

elif len(m)==1:
    if n==k:
        for i in range(len(p)):
            ans*=p[i]
            ans%=mod
        ans%m[-1]
    else:
        for i in range(k):
            ans*=p[i]
            ans%=mod

elif len(p)==1:
    if n==k:
        for i in range(len(m)):
            ans*=m[i]
            ans%=mod
        ans%p[-1]
    elif k%2==0:
        for i in range(k):
            ans*=m[i]
            ans%=mod
    else:
        for i in range(k-1):
            ans*=m[i]
            ans%=mod
        ans*=p[-1]

else:
    cnt=0
    for i in range(k-2):
        if len(m)==0:
            ans*=p.pop()
        elif len(p)==0:
            ans*=m.pop()
            cnt+=1
        else:
            if abs(m[-1])<p[-1]:
                ans*=p.pop()
            else:
                ans*=m.pop()
                cnt+=1
        ans%=mod
    
    if cnt%2==0:
        if len(p)>1 and len(m)>1:
            ans*=max(p[-1]*p[-2],m[-1]*m[-2])
        elif len(p)<2:
            ans*=m[-1]*m[-2]
        else:
            ans*=p[-1]*p[-2]
    else:
        ans*=p[-1]*m[-1]

print(ans%mod)

Submission status: Runtime Error

Solution code:
PRIME = 10 ** 9 + 7

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

_a = sorted(a,key=abs,reverse=True)

ans = 1
if n == k:
  for i in range(k):
    ans = (ans * _a[i]) % PRIME
else:
  minus_n = 0
  minus_k = 0
  zero = 0
  min_minus = -1
  min_plus = -1
  max_minus = -1
  min_plus = -1
  
  for i in range(n):
    if _a[i] < 0:
      minus_n += 1
      if i < k:
        minus_k += 1
        min_minus = i
      else:
        max_minus = i
    elif _a[i] == 0:
      zero += 1
    elif i < k:
      min_plus = i
    else:
      max_plus = i
  
  if minus_n + zero == n and k % 2 == 1:
    for i in range(1, k + 1):
      ans = (ans * _a[-i]) % PRIME
  elif minus_k % 2 == 0:
    for i in range(k):
      ans = (ans * _a[i]) % PRIME
  elif min_plus < 0 or (max_plus >= 0 and (max_minus < 0 or abs(a[max_minus] / a[min_plus]) < abs(a[max_plus] / a[min_minus]))):
    for i in range(k):
      if i != min_minus:
        ans = (ans * _a[i]) % PRIME
    ans = (ans * _a[max_plus]) % PRIME
  else:
    for i in range(k):
      if i != min_plus:
        ans = (ans * _a[i]) % PRIME
    ans = (ans * _a[max_minus]) % PRIME
    
print(ans)

Submission status: Runtime Error

Solution code:
import sys
n,k=map(int,input().split())
A=[]
mod=10**9+7

zero=0
a=list(map(int,input().split()))
for i in range(n):
    if a[i]>0:
        A.append([a[i],0])
    elif a[i]<0:
        A.append([-a[i],1])
    else:
        zero+=1        
if k>n-zero:
    print(0)
    sys.exit()

A=list(reversed(sorted(A)))
cnt=0
for i in range(k):
    cnt+=A[i][1]
chk=0
for i in range(n-zero):
    chk+=A[i][1]
    
if cnt%2==0:
    ans=1
    for i in range(k):
        ans=ans*A[i][0]%mod
    print(ans)
elif chk==n-zero:
    if zero>0:
        print(0)
        sys.exit()
    ans=1
    for i in range(k):
        ans=ans*A[n-i-1][0]%mod
    print((-ans)%mod)
elif k==n-zero:
    if zero>0:
        print(0)
    else:
        for i in range(k):
            ans=ans*A[i][0]%mod
        print((-ans)%mod)
        
else:
    if A[k][1]==0:
        p=A[k][0]
        m=0
        for i in range(k+1,n-zero):
            if A[i][1]==1:
                m=A[i][0]
                break
    else:
        m=A[k][0]
        p=0
        for i in range(k+1,n-zero):
            if A[i][1]==0:
                p=A[i][0]
                break
    #print(m,p)
    if A[k-1][1]==0:
        l=0
        for i in range(k-1):
            if A[k-i-2][1]==1:
                l=A[k-i-2][0]
                Xl=k-i-2
                break
        #print(l,k)
        if m*l>p*A[k-1][0]:
            ans=1
            for i in range(k-1):
                ans=ans*A[i][0]%mod
            ans=ans*m%mod
            print(ans)
        else:
            ans=1
            for i in range(k):
                if i==Xl:
                    continue
                ans=ans*A[i][0]%mod 
            ans=ans*p%mod
            print(ans)
    else:
        l=0
        for i in range(k-1):
            if A[k-i-2][1]==0:
                l=A[k-i-2][0]
                Xl=k-i-2
                break
        #print(l,k)
        if p*l>m*A[k-1][0]:
            ans=1
            for i in range(k-1):
                ans=ans*A[i][0]%mod
            ans=ans*p%mod
            print(ans)
        else:
            ans=1
            for i in range(k):
                if i==Xl:
                    continue
                ans=ans*A[i][0]%mod 
            ans=ans*m%mod
            print(ans)

Submission status: Runtime Error

Solution code:
[N, K] = [int(i) for i in input().split()]
A = sorted([int(i) for i in input().split()], reverse=True)
D = 10**9 + 7

S = 1
i = K
top = 0
tail = N-1

f = 1
if A[0] < 0:
  f = -1

s1 = A[top] * A[top+1]
s2 = A[tail] * A[tail-1]
  
while i > 0:
  if i == 1:
    S *= A[top]
    break
  else:
    if s1 * f > s2 * f:
      S *= s1
      top += 2
      s1 = A[top] * A[top+1]
    else:
      S *= s2
      tail -= 2
      s2 = A[tail] * A[tail-1]
  i -= 2
      
print((S+D)%D)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
ls = list(map(int,input().split()))
mod = 10**9+7
ls = sorted(ls,key=abs,reverse=True)

def mul(l,minp,minn):
  if minn==None:
    minn= -1
  if minp==None:
    minp= -1
  ans = 1
  
  for i in range(len(l)):
    if i==minn or i==minp:
      continue
    ans = ans*l[i]%mod
  return ans

minn=None
minp=None
ncount= 0
for i in range(k):
  if ls[i]<0:
    minn=i
    ncount+=1
  else:
    minp=i

if ncount%2==0:
  print(mul(ls[:k],-1,-1))
  exit()
  
nextn=None
nextp=None
ind = k
while (nextn==None or nextp==None) and ind<n:
  if nextn==None and ls[ind]<0:
    nextn=ind
  if nextp==None and ls[ind]>0:
    nextp=ind
  
  ind+=1
if nextn==None:
  nextn =0
else:
  nextn = ls[nextn]
if nextp==None:
  nextp =0
else:
  nextp = ls[nextp]
  
  
v = max(ls[minn]*nextn,ls[minp]*nextp)%mod
  
print(mul(ls[:k],minn,minp)*v%mod)

Submission status: Runtime Error

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

a.sort(key=abs, reverse=True)
res = 1
idx = k


def is_same(num1, num2):
    if num1 * num2 > 0:
        return True
    else:
        return False


for i in range(k):
    res *= a[i]

if res > 0:
    print(res % mod)
else:
    while idx < n:
        if not is_same(a[k - 1], a[idx]):
            res /= a[k - 1]
            res *= a[idx]
            print(res % mod)
            exit(0)
        idx += 1

    print(0)