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:
# E - Multiplication 4
import heapq
N, K = map(int, input().split())
A = list(int(a) for a in input().split())
MOD = 10**9 + 7

# N = K の時
if N == K:
    ans = 1
    for a in A:
        ans = (ans * a) % MOD

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

    # 必ずマイナスになる時＝全てがマイナスの値であり、
    # かつKが奇数の時
    if len(neg) == N and K&1 == 1:
        neg.sort(reverse=True)
        ans = 1
        for i in range(K):
            ans = (ans * neg[i]) % MOD

    # それ以外のプラスになるケース
    # プラスの要素とマイナスの要素を絶対値の大きい順にソートし、
    # Kが奇数であれば、プラスのリストから1つ選び、
    # 残りの偶数個のKに対して、２つずつを選んだ時の
    # 大きい方から取得していく
    else:
        pos.sort(reverse=True)
        pos2 = []
        ans = 1
        ini = 0
        rem = K
        if K&1 == 1:
            ans = (ans * pos[0]) % MOD
            ini = 1
            rem -= 1
        for i in range(ini, len(pos)//2, 2):
            heapq.heappush(pos2, (pos[i] * pos[i+1])*-1)
        neg.sort()
        neg2 = []
        for i in range(0, len(neg)//2, 2):
            heapq.heappush(neg2, (neg[i] * neg[i+1]) * -1)
        while rem > 0:
            if (pos2 != [] and neg2 != [] and pos2[0] <= neg2[0]) or (pos2 != [] and neg2 == []):
                tmp = heapq.heappop(pos2) * -1
            else:
                tmp = heapq.heappop(neg2) * -1
            ans = (ans * tmp) % MOD
            rem -= 2

print(ans)

Submission status: Runtime Error

Solution code:
# E - Multiplication 4
import heapq
N, K = map(int, input().split())
A = list(int(a) for a in input().split())
MOD = 10**9 + 7

# N = K の時
if N == K:
    ans = 1
    for a in A:
        ans = (ans * a) % MOD

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

    # 必ずマイナスになる時＝全てがマイナスの値であり、
    # かつKが奇数の時
    if len(neg) == N and K&1 == 1:
        neg.sort(reverse=True)
        ans = 1
        for i in range(K):
            ans = (ans * neg[i]) % MOD

    # それ以外のプラスになるケース
    # プラスの要素とマイナスの要素を絶対値の大きい順にソートし、
    # Kが奇数であれば、プラスのリストから1つ選び、
    # 残りの偶数個のKに対して、２つずつを選んだ時の
    # 大きい方から取得していく
    else:
        pos.sort(reverse=True)
        pos2 = []
        ans = 1
        ini = 0
        if K&1 == 1:
            ans = (ans * pos[0]) % MOD
            ini = 1
        for i in range(ini, len(pos)//2, 2):
            heapq.heappush(pos2, (pos[i] * pos[i+1])*-1)
        neg.sort()
        neg2 = []
        for i in range(0, len(neg)//2, 2):
            heapq.heappush(neg2, (neg[i] * neg[i+1]) * -1)
        rem = K-1
        while rem > 0:
            if (pos2 != [] and neg2 != [] and pos2[0] <= neg2[0]) or (pos2 != [] and neg2 == []):
                tmp = heapq.heappop(pos2) * -1
            else:
                tmp = heapq.heappop(neg2) * -1
            ans = (ans * tmp) % MOD
            rem -= 2

print(ans)

Submission status: Runtime Error

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

ze = []
pl,mi = [],[]
for i in range(n):
    if a[i] < 0:
        ze.append((-a[i],1))
        mi.append(a[i])
    else:
        ze.append((a[i],0))
        pl.append(a[i])
        
ze.sort(reverse = True)
pl.sort(reverse = True)
mi.sort()

one = 0
for i in range(k):
    one += ze[i][1]
    
ans = 1
zero = k-one

if one % 2 == 0:
    for i in range(k):
        ans = ans * ze[i][0] % MOD
    print(ans)
        
elif len(pl) == 0:
    for i in range(k):
        ans = ans * mi[n-1-i] % MOD
    print(ans)
        
else:
    if (zero == len(pl) and one == len(mi)):
        ak = [zero,one]
    elif (zero != len(pl) and one == len(mi)):
        ak = [zero+1,one-1]
    elif zero == len(pl) and one != len(mi):
        ak = [zero-1,one+1]
    else:
        if abs(mi[zero])/pl[one-1] >= pl[one]/abs(mi[zero-1]):
            ak = [zero+1,one-1]
        else:
            ak = [zero-1,one+1]
            
    ans = 1
    for i in range(ak[0]):
        ans = ans * pl[i] % MOD
    for i in range(ak[1]):
        ans = ans * mi[i] % MOD
        
    print(ans)

Submission status: Runtime Error

Solution code:
# E - Multiplication 4
import heapq
N, K = map(int, input().split())
A = list(int(a) for a in input().split())
MOD = 10**9 + 7

# N = K の時
if N == K:
    ans = 1
    for a in A:
        ans = (ans * a) % MOD

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

    # 必ずマイナスになる時＝全てがマイナスの値であり、
    # かつKが奇数の時
    if len(neg) == N and K&1 == 1:
        neg.sort(reverse=True)
        ans = 1
        for i in range(K):
            ans = (ans * neg[i]) % MOD

    # それ以外のプラスになるケース
    # プラスの要素とマイナスの要素を絶対値の大きい順にソートし、
    # Kが奇数であれば、プラスのリストから1つ選び、
    # 残りの偶数個のKに対して、２つずつを選んだ時の
    # 大きい方から取得していく
    else:
        pos.sort(reverse=True)
        pos2 = []
        ans = 1
        ini = 0
        if K&1 == 1:
            ans = (ans * pos[0]) % MOD
            ini = 1
        for i in range(ini, len(pos)//2, 2):
            heapq.heappush(pos2, (pos[i] * pos[i+1])*-1)
        neg.sort()
        neg2 = []
        for i in range(0, len(neg)//2, 2):
            heapq.heappush(neg2, (neg[i] * neg[i+1]) * -1)
        rem = K-1
        while rem > 0:
            if pos2[0] <= neg2[0]:
                tmp = heapq.heappop(pos2) * -1
            else:
                tmp = heapq.heappop(neg2) * -1
            ans = (ans * tmp) % MOD
            rem -= 2

print(ans)

Submission status: Runtime Error

Solution code:
import sys
from operator import mul
from functools import reduce
from collections import deque

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


MOD = 10**9 + 7

# negを奇数個選ばないといけないシチュエーションかどうか
neg = [x < 0 for x in arr]

if all(neg) and k % 2 == 1:
    arr.sort(reverse=True)
    print(reduce(mul, arr[:k]) % MOD)
    sys.exit()

arr_p = [x for x in arr if x >= 0]
arr_n = [x for x in arr if x < 0]

arr_p.sort(reverse=True)
arr_n.sort()

# 最低でもnegを何個選ばないといけないか
init_neg = (k - len(arr_p) + 1) // 2 * 2

# その時のposの個数
init_pos = k - init_neg

neg = 1
if init_neg > 0:
    neg *= reduce(mul, arr_n[:init_neg])

pos = 1
if init_pos > 0:
    pos *= reduce(mul, arr_p[:init_pos])

ans = neg * pos
arr_p = deque(arr_p)
arr_n = deque(arr_n)

while len(arr_p) >= 2 and len(arr_n) >= 2:
    a = arr_p.popleft()
    b = arr_p.popleft()
    c = arr_n.popleft()
    d = arr_n.popleft()
    tmp = ans // a // b * c * d
    ans = max(ans, tmp)

print(ans % MOD)

Submission status: Runtime Error

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

ze = []
pl,mi = [],[]
for i in range(n):
    if a[i] < 0:
        ze.append((-a[i],1))
        mi.append(a[i])
    else:
        ze.append((a[i],0))
        pl.append(a[i])
        
ze.sort(reverse = True)
pl.sort(reverse = True)
mi.sort()

one = 0
for i in range(k):
    one += ze[i][1]
    
ans = 1
zero = k-one

if one % 2 == 0:
    for i in range(k):
        ans = ans * ze[i][0] % MOD
    print(ans)
        
elif zero == 0:
    for i in range(k):
        ans = ans * mi[n-1-i] % MOD
        print(ans)
        
else:
    if (zero == len(pl) and one == len(mi)) or len(pl) == 0:
        ak = [zero,one]
    elif (zero != len(pl) and one == len(mi)):
        ak = [zero+1,one-1]
    elif zero == len(pl) and one != len(mi):
        ak = [zero-1,one+1]
    else:
        if abs(mi[zero])/pl[one-1] >= pl[one]/abs(mi[zero-1]):
            ak = [zero+1,one-1]
        else:
            ak = [zero-1,one+1]
            
    ans = 1
    for i in range(ak[0]):
        ans = ans * pl[i] % MOD
    for i in range(ak[1]):
        ans = ans * mi[i] % MOD
        
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
from operator import mul
from functools import reduce
import deque

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


MOD = 10**9 + 7

# negを奇数個選ばないといけないシチュエーションかどうか
neg = [x < 0 for x in arr]

if all(neg) and k % 2 == 1:
    arr.sort(reverse=True)
    print(reduce(mul, arr[:k]) % MOD)
    sys.exit()

arr_p = [x for x in arr if x >= 0]
arr_n = [x for x in arr if x < 0]

arr_p.sort(reverse=True)
arr_n.sort()

# 最低でもnegを何個選ばないといけないか
init_neg = (k - len(arr_p) + 1) // 2 * 2

# その時のposの個数
init_pos = k - init_neg

neg = 1
if init_neg > 0:
    neg *= reduce(mul, arr_n[:init_neg])

pos = 1
if init_pos > 0:
    pos *= reduce(mul, arr_p[:init_pos])

ans = neg * pos
arr_p = deque(arr_p)
arr_n = deque(arr_n)

while len(arr_p) >= 2 and len(arr_n) >= 2:
    a = arr_p.popleft()
    b = arr_p.popleft()
    c = arr_n.popleft()
    d = arr_n.popleft()
    tmp = ans // a // b * c * d
    ans = max(ans, tmp)

print(ans % MOD)

Submission status: Runtime Error

Solution code:
n,k=map(int, input().split())
a = list(map(int, input().split()))
mod=10**9+7
if n==k:
    ans=1
    for i in range(k):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()
minus=[i for i in a if i<0]
plus=[i for i in a if i>=0]
from collections import deque
minus=deque(sorted(minus))
plus=deque(sorted(plus,reverse=True))

n_minus=len(minus)
n_plus=len(plus)

if n_minus==n:
    ans=1
    if k%2==0:
        for i in range(k):
            ans*=minus.popleft()
            ans%=mod
        print(ans)
        exit()
    else:
        for i in range(k):
            ans*=minus.pop()
            ans%=mod
        print(ans)
        exit()

cnt_minus=0
cand=deque([])
for i in range(k):
    if not plus or abs(minus[0])>abs(plus[0]):
        cand.append(minus.popleft())
        cnt_minus+=1
    elif not minus or abs(minus[0])<abs(plus[0]):
        cand.append(plus.popleft())
    else:
        if cnt_minus%2==1:
            cand.append(minus.popleft())
            cnt_minus+=1
        else:
            cand.append(plus.popleft())

if cnt_minus%2==0:
    ans=1
    for i in range(k):
        ans*=cand[i]
        ans%=mod
    print(ans)
    exit()

tmpm,tmpp=None,None

for i in range(k-1,-1,-1):
    if cand[i]<0 and tmpm==None:
        tmpm=cand[i]
    elif cand[i]>=0 and tmpp==None:
        tmpp=cand[i]

cand1,cand2=None,None
if tmpm!=None and plus:
    cand1=plus[0]/abs(tmpm)
if tmpp!=None and minus:
    if tmpp!=0:
        cand2=abs(minus[0])/abs(tmpp)
    else:
        cand2=0


if (cand1!=None and cand2==None) or ((cand1!=None and cand2!=None) and cand1>=cand2):
    ans=1
    flg=True
    for i in range(k):
        if flg and cand[i]==tmpm:
            flg=False
            continue
        ans*=cand[i]
        ans%=mod
    print((ans*plus[0])%mod)
    exit()
elif (cand1==None and cand2!=None) or ((cand1!=None and cand2!=None) and cand1<cand2):
    ans=1
    flg=True
    for i in range(k):
        if flg and cand[i]==tmpp:
            flg=False
            continue
        ans*=cand[i]
        ans%=mod
    print((ans*minus[0])%mod)
    exit()

Submission status: Runtime Error

Solution code:
n, k = [int(x) for x in input().split()]
l = [int(x) for x in input().split()]
p = list(filter(lambda x: x>=0, l))
n = list(filter(lambda x: x<0, l))
p.sort()
n.sort()
pIndex = max(len(p)-1,0)
nIndex = max(len(n)-1,0)
ans = 1

while(k>0):
    if pIndex>0 and nIndex>0:
        pp = p[pIndex]*p[pIndex-1]
        np = n[nIndex]*n[nIndex-1]
        if k>1:
            k-=2
            if pp>np:
                ans*=pp%1000000007
                pIndex-=2
            else:
                ans*=np%1000000007
                nIndex-=2
        else:
            ans*=p[pIndex]%1000000007
            pIndex-=1
            k-=1
    elif pIndex==-1:
        ans*=n[nIndex]%1000000007
        nIndex-=1
        k-=1
    else:
        ans*=p[pIndex]%1000000007
        pIndex-=1
        k-=1
        
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
n,k=map(int, input().split())
a = list(map(int, input().split()))
mod=10**9+7
if n==k:
    ans=1
    for i in range(k):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()
minus=[i for i in a if i<0]
plus=[i for i in a if i>=0]
from collections import deque
minus=deque(sorted(minus))
plus=deque(sorted(plus,reverse=True))

n_minus=len(minus)
n_plus=len(plus)

if n_minus==n:
    ans=1
    if k%2==0:
        for i in range(k):
            ans*=minus.popleft()
            ans%=mod
        print(ans)
        exit()
    else:
        for i in range(k):
            ans*=minus.pop()
            ans%=mod
        print(ans)
        exit()

cnt_minus=0
cand=deque([])
for i in range(k):
    if not plus or abs(minus[0])>abs(plus[0]):
        cand.append(minus.popleft())
        cnt_minus+=1
    elif not minus or abs(minus[0])<abs(plus[0]):
        cand.append(plus.popleft())
    else:
        if cnt_minus%2==1:
            cand.append(minus.popleft())
            cnt_minus+=1
        else:
            cand.append(plus.popleft())

if cnt_minus%2==0:
    ans=1
    for i in range(k):
        ans*=cand[i]
        ans%=mod
    print(ans)
    exit()

tmpm,tmpp=None,None

for i in range(k-1,-1,-1):
    if cand[i]<0 and tmpm==None:
        tmpm=cand[i]
    elif cand[i]>=0 and tmpp==None:
        tmpp=cand[i]

cand1,cand2=None,None
if tmpm!=None and plus:
    cand1=plus[0]/abs(tmpm)
if tmpp!=None and minus:
    cand2=minus[0]/abs(tmpp)

if (cand1!=None and cand2==None) or cand1>=cand2:
    ans=1
    flg=True
    for i in range(k):
        if flg and cand[i]==tmpm:
            flg=False
            continue
        ans*=cand[i]
        ans%=mod
    print(ans*plus[0]%mod)
    exit()
elif (cand1==None and cand2!=None) or cand1<cand2:
    ans=1
    flg=True
    for i in range(k):
        if flg and cand[i]==tmpp:
            flg=False
            continue
        ans*=cand[i]
        ans%=mod
    print(ans*minus[0]%mod)
    exit()

Submission status: Runtime Error

Solution code:
n, k = [int(x) for x in input().split()]
l = [int(x) for x in input().split()]
p = list(filter(lambda x: x>=0, l))
n = list(filter(lambda x: x<0, l))
p.sort()
n.sort()
pIndex = max(len(p)-1,0)
nIndex = max(len(n)-1,0)
ans = 1

while(k>0):
    if pIndex>0 and nIndex>0:
        pp = p[pIndex]*p[pIndex-1]
        np = n[nIndex]*n[nIndex-1]
        if k>1:
            k-=2
            if pp>np:
                ans*=pp%1000000007
                pIndex-=2
            else:
                ans*=np%1000000007
                nIndex-=2
        else:
            ans*=p[pIndex]
            pIndex-=1
            k-=1
    elif pIndex==-1:
        ans*=n[nIndex]%1000000007
        nIndex-=1
        k-=1
    else:
        ans*=p[pIndex]%1000000007
        pIndex-=1
        k-=1
        
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
n, k = [int(x) for x in input().split()]
l = [int(x) for x in input().split()]
p = list(filter(lambda x: x>=0, l))
n = list(filter(lambda x: x<0, l))
p.sort()
n.sort()
pIndex = max(len(p)-1,0)
nIndex = max(len(n)-1,0)
ans = 1

while(k>0):
    if pIndex>0 and nIndex>0:
        pp = p[pIndex]*p[pIndex-1]
        np = n[nIndex]*n[nIndex-1]
        if k>1:
            k-=2
            if pp>np:
                ans*=pp
                pIndex-=2
            else:
                ans*=np
                nIndex-=2
        else:
            ans*=p[pIndex]
            pIndex-=1
            k-=1
    elif pIndex==-1:
        ans*=n[nIndex]
        nIndex-=1
        k-=1
    else:
        ans*=p[pIndex]
        pIndex-=1
        k-=1
        
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    N, K = in_nn()
    A = in_nl()

    #import random
    #N, K = 100, 99
    #A = [random.randint(-10**9, 10**9) for _ in range(N)]

    mod = 10 ** 9 + 7

    Am = []
    Ap = []

    for i in range(N):
        if A[i] < 0:
            Am.append(A[i])
        elif A[i] >= 0:
            Ap.append(A[i])

    Ap = list(sorted(Ap, reverse=True))
    Am = list(sorted(Am))

    Nm = len(Am)
    Np = len(Ap)

    if Nm + Np == K:
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= mod
    elif Np == 0:
        if K % 2 == 0:
            ans = 1
            for i in range(K):
                ans *= Am[i]
                ans %= mod
        else:
            ans = 1
            for i in range(K):
                ans *= Am[Nm - 1 - i]
                ans %= mod
    else:
        t = A[N + 1]
        count = 0
        nums = []

        Am = deque(Am)
        Ap = deque(Ap)

        while True:
            if count == K:
                break
            elif count == K - 1:
                nums.append(Ap.popleft())
                count += 1
            else:
                if len(Ap) >= 2 and len(Am) >= 2:
                    tp = Ap[0] * A[1]
                    tm = Am[0] * Am[1]
                    if tp > tm:
                        nums.append(Ap.popleft())
                        nums.append(Ap.popleft())
                    else:
                        nums.append(Am.popleft())
                        nums.append(Am.popleft())
                elif len(Ap) >= 2:
                    nums.append(Ap.popleft())
                    nums.append(Ap.popleft())
                elif len(Am) >= 2:
                    nums.append(Am.popleft())
                    nums.append(Am.popleft())
                count += 2

        ans = 1
        for n in nums:
            ans *= n
            ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
li_a = list(map(int, input().split()))
sum_ = 0
li_a.sort()
for i in range(1, n):
  sum_ += li_a[n-1-(i)//2]
print(sum_)

Submission status: Runtime Error

Solution code:
import sys
import heapq

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    MOD = 10 ** 9 + 7

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

    flag = False  # 積を正にできるか

    if N == K:
        ans = 1
        for a in A:
            ans *= a % MOD
        print(ans % MOD)
        exit()

    if len(pos) > 0:
        flag = True
    else:
        if K % 2 == 0:
            flag = True

    ans = 1
    if not flag:
        # 積を正にできないとき
        # 絶対値の小さい方からK個とる
        h = [abs(x) for x in A]
        heapq.heapify(h)

        for i in range(K):
            ans *= heapq.heappop(h)
        ans *= -1
    else:
        hpos = [-x for x in pos]
        heapq.heapify(hpos)
        hneg = neg[:]
        heapq.heapify(hneg)
        if K % 2 == 1:
            # Kが奇数の時
            # 一番大きい偶数を1つとる。
            ans *= -heapq.heappop(hpos) % MOD

        # pos, neg sort -> 2個ずつペア -> 降順sort -> 上から K//2 個とる
        pairs = []
        while len(hpos) >= 2:
            x = -heapq.heappop(hpos)
            x *= -heapq.heappop(hpos)
            heapq.heappush(pairs, -x)
        while len(hneg) >= 2:
            x = heapq.heappop(hneg)
            x *= heapq.heappop(hneg)
            heapq.heappush(pairs, -x)
        for i in range(K):
            ans *= -heapq.heappop(pairs) % MOD

    print(ans % MOD)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
mod = 10**9 + 7

def sgn(v):
    return (v > 0) - (v < 0)

def compute_answer():
    v.sort(key=abs, reverse=True)
    prod = 1
    sg = 1
    for a in xrange(k):
        prod *= v[a]
        prod %= mod
        sg *= sgn(v[a])

    if sg >= 0:
        return prod

    if max(v) <= 0:
        prod = 1
        for a in xrange(-k,0):
            prod *= v[a]
            prod %= mod
        return prod

    def find_pair(comp):
        i = k-1
        while i >= 0 and comp(v[i]): i -= 1
        j = k
        while j < n and not comp(v[j]): j += 1
        if j == n: j = i
        return i, j
    i, j = find_pair(lambda w: w >= 0)
    I, J = find_pair(lambda w: w <= 0)
    if I >= 0 and v[j] * v[I] < v[i] * v[J]:
        i = I
        j = J

    prod = v[j]
    for a in xrange(k):
        if a != i:
            prod *= v[a]
            prod %= mod
    return prod

for cas in xrange(input()):
    n, k = map(int, raw_input().strip().split())
    v = map(int, raw_input().strip().split())
    print compute_answer()

Submission status: Runtime Error

Solution code:
import sys
from decimal import Decimal


read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    N, K = in_nn()
    A = in_nl()

    #import random
    #N, K = 100, 99
    #A = [random.randint(-10**9, 10**9) for _ in range(N)]
    mod = 10 ** 9 + 7

    Am = []
    Ap = []

    for i in range(N):
        if A[i] < 0:
            Am.append(A[i])
        elif A[i] >= 0:
            Ap.append(A[i])

    Ap = list(sorted(Ap, reverse=True))
    Am = list(sorted(Am))

    Nm = len(Am)
    Np = len(Ap)

    if Nm == 0:
        ans = 1
        for i in range(K):
            ans *= Ap[i]
            ans %= mod
    elif Nm == 1:
        if Nm + Np == K:
            ans = Am[0]
            for i in range(K - 1):
                ans *= Ap[i]
                ans %= mod
        else:
            ans = 1
            for i in range(K):
                ans *= Ap[i]
                ans %= mod
    elif Np == 0:
        if K % 2 == 0:
            ans = 1
            for i in range(K):
                ans *= Am[i]
                ans %= mod
        else:
            ans = 1
            for i in range(K):
                ans *= Am[Nm - 1 - i]
                ans %= mod
    else:
        if K % 2 == 0:
            if Np % 2 == 0:
                pi = Np
                mi = K - pi
            else:
                pi = Np - 1
                mi = K - pi
        else:
            if Np % 2 == 0:
                pi = Np - 1
                mi = K - pi
            else:
                pi = Np
                mi = K - pi
        rate = Decimal(1)
        max_rate = Decimal(1)
        max_i = (pi, mi)
        while True:
            pi -= 2
            mi += 2
            if pi >= 0 and mi <= Nm:
                tm = Decimal(Am[mi - 2] * Am[mi - 1])
                tp = Decimal(Ap[pi - 1] * Ap[pi])
                if tp == 0:
                    break
                rate *= tm / tp
                if max_rate < rate:
                    max_rate = rate
                    max_i = (pi, mi)
            else:
                break
        pi, mi = max_i
        ans = 1
        for i in range(pi):
            ans *= Ap[i]
            ans %= mod
        for i in range(mi):
            ans *= Am[i]
            ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
arr = [int(x) for x in input().split()]

MOD = int(1e9) + 7

if k == n:
    res = 1
    for i in range(len(arr)):
        res = ((res % MOD) * (arr[i] % MOD)) % MOD
    print(res % MOD)
    exit(1)

pos = []
neg = []

zero = 0
for ele in arr:
    if ele < 0:
        neg.append(ele)
    elif ele > 0:
        pos.append(ele)
    else:
        zero += 1
max_prod = 1

#agar result mei negative sign ayega hi toh phir sabse chhote element lene pdhenge
contains_neg = False
required_neg = k - len(pos)
if required_neg <= len(neg):
    if required_neg % 2 != 0:
        contains_neg = True
else:
    print(0) #there will be one zero element atleast
    exit(1)

if contains_neg:
    abs_arr = [abs(x) for x in arr]
    abs_arr.sort()
    for i in range(k):
        ele = abs_arr[i]
        max_prod = ((max_prod % MOD) * (ele % MOD)) % MOD
    max_prod *= -1
    print(max_prod % MOD)
else:
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    positive_pairs = []
    negative_pairs = []
    for i in range(0, len(pos), 2):
        if i + 1 >= len(pos):
            break
        positive_pairs.append(pos[i] * pos[i+1])
    for i in range(0, len(neg), 2):
        if i + 1 >= len(neg):
            break
        negative_pairs.append(neg[i] * neg[i+1])
    i, j = 0, 0
    cnt = 0
    for _ in range(k//2):
        if j == len(negative_pairs) and i == len(positive_pairs):
            break
        if j == len(negative_pairs) and i < len(positive_pairs):
            best = positive_pairs[i] % MOD
            i += 1
        elif i == len(positive_pairs) and j < len(negative_pairs):
            best = negative_pairs[j] % MOD
            j += 1
        elif positive_pairs[i] > negative_pairs[j]:
            best = positive_pairs[i] % MOD
            i += 1
        else:
            best = negative_pairs[j] % MOD
            j += 1
        cnt += 2
        max_prod = ((max_prod % MOD) * (best % MOD)) % MOD
    if cnt < k:
        if k - cnt == 1:
            if len(pos) % 2 == 1:
                max_prod = ((max_prod % MOD) * (pos[-1] % MOD)) % MOD
        else:
            if zero >= 1:
                max_prod = 0
    print(max_prod % MOD)

Submission status: Runtime Error

Solution code:
import sys
from decimal import Decimal

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    N, K = in_nn()
    A = in_nl()
    mod = 10 ** 9 + 7

    Am = []
    Ap = []

    for i in range(N):
        if A[i] < 0:
            Am.append(A[i])
        elif A[i] >= 0:
            Ap.append(A[i])

    Ap = list(sorted(Ap, reverse=True))
    Am = list(sorted(Am))

    Nm = len(Am)
    Np = len(Ap)

    if Nm == 0:
        ans = 1
        for i in range(K):
            ans *= Ap[i]
            ans %= mod
    elif Nm == 1:
        if Nm + Np == K:
            ans = Am[0]
            for i in range(K - 1):
                ans *= Ap[i]
                ans %= mod
        else:
            ans = 1
            for i in range(K):
                ans *= Ap[i]
                ans %= mod
    elif Np == 0:
        if K % 2 == 0:
            ans = 1
            for i in range(K):
                ans *= Am[i]
                ans %= mod
        else:
            ans = 1
            for i in range(K):
                ans *= Am[Nm - 1 - i]
                ans %= mod
    else:
        if K % 2 == 0:
            if Np % 2 == 0:
                pi = Np
                mi = 0
            else:
                pi = Np - 1
                mi = 2
        else:
            if Np % 2 == 0:
                pi = Np - 1
                mi = 2
            else:
                pi = Np
                mi = 0
        rate = Decimal(1)
        max_rate = Decimal(1)
        max_i = (pi, mi)
        while True:
            pi -= 2
            mi += 2
            if pi >= 0 and mi <= Nm:
                tm = Decimal(Am[mi - 2] * Am[mi - 1])
                tp = Decimal(Ap[pi - 1] * Ap[pi])
                rate *= tm / tp
                if max_rate < rate:
                    max_rate = rate
                    max_i = (pi, mi)
            else:
                break
        pi, mi = max_i
        ans = 1
        for i in range(pi):
            ans *= Ap[i]
            ans %= mod
        for i in range(mi):
            ans *= Am[i]
            ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, K = map(int, input().split())
    A = np.array(list(map(int, input().split())), np.int64)
    A = np.sort(A)

    MOD = 10 ** 9 + 7

    pos = A[A >= 0]
    neg = A[A < 0]

    flag = False  # 積を正にできるか

    if N == K:
        ans = 1
        for a in A.tolist():
            ans *= a % MOD
        print(ans % MOD)
        exit()

    if len(pos) > 0:
        flag = True
    else:
        if K % 2 == 0:
            flag = True

    ans = 1
    if not flag:
        # 積を正にできないとき
        # 絶対値の小さい方からK個とる
        A = np.sort(np.abs(A))
        for i in range(K):
            ans *= A[i] % MOD
        ans *= -1
    else:
        # pos = np.sort(pos)
        neg = neg[::-1]
        if K % 2 == 1:
            # Kが奇数の時
            # 一番大きい偶数を1つとる。
            ans *= pos[-1]
            pos = pos[:-1]

        # pos, neg sort -> 2個ずつペア -> 降順sort -> 上から K//2 個とる
        newpos = pos[::-1][::2] * pos[::-1][1::2]
        newneg = neg[::2] * neg[1::2]
        pairs = np.concatenate([newpos, newneg])

        pairs = np.sort(pairs)[::-1]
        for i in range(K // 2):
            ans *= pairs[i] % MOD

    print(ans % MOD)


if __name__ == "__main__":
    main()