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:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
import math
# import networkx as nx
from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n,k=n1()
A=n1()
MOD = 10**9+7

A.sort()

m=bisect_left(A,0)
p=n-bisect_right(A,0)
z=n-m-p

A.sort(key=lambda x:abs(x),reverse=True)

ans=1
if m==n:
    for i in range(k):
        ans = (ans * A[n-i-1]) % MOD
else:
    c=0
    f=False
    i=0
    while c<k:
        a=A[i]
        if a>0:
            ans = (ans * a) % MOD
            c+=1
        elif a<0:
            if f==False:
                m_num = a
                f=True
            else:
                if c<k-1:
                    ans = (ans * a * m_num) % MOD
                    f=False    
                    c+=2
        else:
            ans = 0
            break
        i+=1
        
print(ans % MOD)

Submission status: Runtime Error

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
mod = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 1
a.sort()
if a[0] < 0:
    cnt = 0
    for x in a:
        if x < 0:
            cnt += 1
    if cnt%2 == 1:
        a.pop(cnt - 1)
if k%2 == 1 and a[n - 1] < 0:
    if 0 in a:
        print(0)
        sys.exit()
    for i in range(k):
        ans = (ans * a[n - 1 - i])%mod
    print(ans%mod)
    sys.exit()
for _ in range(k - 1):
    if abs(a[n - 1]) >= abs(a[0]):
        ans = (ans * a[n - 1])
        #print(a[n-1])
        a.pop(n - 1)
    else:
        ans = (ans * a[0])
        #print(a[0])
        a.pop(0)
    if ans > 0: ans %= mod
    n -= 1
if ans < 0:
    ans = (ans * a[0])%mod
    #print('a0', a[0])
else:
    ans = (ans * a[n - 1])%mod
    #print('an', a[n-1])
print(ans%mod)

Submission status: Runtime Error

Solution code:
import itertools


def out(X):
    return list(itertools.accumulate(X, func=lambda x, y: x * y % mod))[-1]


N, K = [int(_) for _ in input().split()]
A = sorted([int(_) for _ in input().split()], key=lambda x: -abs(x))
mod = 10**9 + 7
cnt = 0
ipos = ineg = -1
for i, a in enumerate(A[:K]):
    if a < 0:
        cnt += 1
        ineg = i
    else:
        ipos = i
if cnt % 2 == 0:
    print(out(A[:K]))
else:
    oneg = opos = -10**10
    for i, a in enumerate(A[K:]):
        if a < 0 and ipos != -1:
            X = A[:ipos] + A[ipos + 1:K] + A[K + i]
            oneg = out(X)
            ipos = -1
        elif a > 0 and ineg != -1:
            X = A[:ineg] + A[ineg + 1:K] + A[K + i]
            opos = out(X)
            ineg = -1
    if oneg != -10**10 or opos != -10**10:
        print(max(opos, oneg))
    else:
        C = A[::-1]
        print(out(C[:K]))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
ls = list(map(int, input().split()))

mod = 10**9 + 7

minus = []
plus = []
zero = []
new_ls = []
for i in ls:
    if i > 0:
        plus.append(i)
        new_ls.append(i)
    elif i < 0:
        minus.append(i)
        new_ls.append(-i)
    else:
        zero.append(i)
        new_ls.append(i)

ans = 1
new_ls.sort()
minus.sort()
plus.sort()
if (len(plus) == 0 and len(zero) == 0 and k%2 == 1) or (len(minus)%2 == 1 and k == n):
    if len(zero) != 0:
        print(0)
    else:
        for i in range(k):
            ans *= -new_ls[i]
            ans %= mod
elif k%2 == 0:
    m_ind = 0
    p_ind = 0
    for i in range(k//2):
        if m_ind+1 < len(minus) and p_ind+1 < len(plus):
            if minus[m_ind] * minus[m_ind+1] > plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]:
                ans *= minus[m_ind] * minus[m_ind+1]
                ans %= mod
                m_ind += 2
            else:
                ans *= plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]
                ans %= mod
                p_ind += 2
        elif m_ind+1 < len(minus):
            ans *= minus[m_ind] * minus[m_ind+1]
            ans %= mod
            m_ind += 2
        elif p_ind+1 < len(plus):
            ans *= plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]
            ans %= mod
            p_ind += 2
        #else:
else:
    m_ind = 0
    p_ind = 0
    for i in range(k//2):
        if m_ind+1 < len(minus) and p_ind+1 < len(plus):
            if minus[m_ind] * minus[m_ind+1] > plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]:
                ans *= minus[m_ind] * minus[m_ind+1]
                ans %= mod
                m_ind += 2
            else:
                ans *= plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]
                ans %= mod
                p_ind += 2
        elif m_ind+1 < len(minus):
            ans *= minus[m_ind] * minus[m_ind+1]
            ans %= mod
            m_ind += 2
        elif p_ind+1 < len(plus):
            ans *= plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]
            ans %= mod
            p_ind += 2
        #else:
    ans *= plus[len(plus)-p_ind-1]
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
a = list(map(int, input().split()))
N = int(a[0])
K = int(a[1])
A_i = list(map(int, input().split()))
A_pos = [i for i in A_i if i > 0]
A_neg = [i for i in A_i if i < 0]
A_zer = [i for i in A_i if i == 0]

A_pos = sorted(A_pos)
A_neg = sorted(A_neg)
A_neg.reverse()

ret = 1
flag = 0
if K % 2 == 1:
    if len(A_pos) == 0:
        if len(A_zer) > 0:
            ret = 0
        for i in range(K):
            ret = ret * A_neg[i]
            ret = ret % (10**9+7)
        if ret < 0:
            ret += 10**9+7
    else:
        ret *= A_pos[-1]
        A_pos = A_pos[:-1]

if ret <= 0:
    pass
else:
    for i in range(K//2):
        if len(A_pos) == 0 and len(A_neg) == 2:
            ret = ret * A_neg[0] * A_neg[1]
            break
        if len(A_pos) == 1 and len(A_neg) == 1:
            ret = ret * A_neg[0] * A_pos[0]
            break
        if len(A_pos) == 2 and len(A_pos) == 0:
            ret = ret * A_pos[0] * A_pos[1]
            break

        c1 = A_pos[-1] * A_pos[-2]
        if len(A_neg) >= 2:
            c2 = A_neg[-1] * A_neg[-2]
        else:
            c2 = 0
        if c1 > c2:
            ret = ret * A_pos[-1] * A_pos[-2]
            A_pos = A_pos[:-2]
        else:
            ret = ret * A_neg[-1] * A_neg[-2]
            A_neg = A_neg[:-2]
        ret = ret % (10**9+7)
        if ret < 0:
            ret += 10**9+7
print(ret)

Submission status: Runtime Error

Solution code:
from collections import deque
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
d=deque(A)


l=[]
if K%2==0 or (K%2==1 and A[0]>0):
  for i in range(K//2):
    if d[0]*d[1]>=d[-1]*d[-2] and d[2]>0:
      l.append(d.popleft())
      l.append(d.popleft())
    else:
      l.append(d.pop())
      l.append(d.pop())
  if K%2==1:
    l.append(d[0])
else:
  for i in range(K):
    l.append(d.popleft())
      
ans=1
for i in l:
  ans*=i
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
import bisect
from collections import deque
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
minus = deque(a[:bisect.bisect_left(a, 0)])
plus = deque(a[bisect.bisect_left(a, 0):])
nm = len(minus)
np = len(plus)
mod = 10**9+7
ans = -float("inf")
repeat = min(nm//2, k//2)

if k == n:
  ans = 1
  for i in range(n):
    ans *= a[i]
    ans %= mod
  print(ans)
  quit()

flg=False
must1 = k-np
must2 = min(k, nm)
if must1 % 2 == 1 and must2 - must1 ==0:
  flg = True

if flg:
  ans = 1
  for i in range(k):
    ans *= minus.pop()
    ans %= mod
  print(ans)
  quit()
    
for i in range(repeat+1):
  temp = 1
  kuri = 0
  for j in range(i*2):
    temp*=minus.popleft()  
    temp%=mod
  for j in range(k-i*2):
    temp*=plus.pop()
    temp%=mod
  #print(i)
  #print(temp)
  ans=max(ans, temp)

print(ans)

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7

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

alst.sort()

if k == 1:
    print(alst[-1] % MOD)
    exit()

if alst[0] >= 0:
    ans = 1
    alst.sort(reverse = True)
    for i in range(k):
        ans *= alst[i]
        ans %= MOD
    print(ans)
    exit()

if alst[-1] <= 0:
    ans = 1
    if k % 2 == 1:
        alst.sort(reverse = True)
    for i in range(k):
        ans *= alst[i]
        ans %= MOD
    print(ans)
    exit()

blst = []
for num in alst:
    try:
        blst.append([abs(num), abs(num) // num])
    except ZeroDivisionError:
        blst.append([abs(num), 0])
blst.sort(reverse = True)
if blst[k - 1] == 0:
    print(0)
    exit()
    
minus = 0
last_minus = 0
last_plus = 0
ans_lst = []
for i in range(k):
    if blst[i][1] == -1:
        minus += 1
        last_minus = blst[i][0]
    else:
        last_plus = blst[i][0]
    ans_lst.append(blst[i][0])

next_minus = 0
next_plus = 0
flg_minus = False
flg_plus = False

for i in range(k, n):
    if blst[i][1] == -1 and (not flg_minus):
        next_minus = blst[i][0]
        flg_minus = True
    if blst[i][1] == 1 and (not flg_plus):
        next_plus = blst[i][0]
        flg_plus = True
    if (flg_plus and flg_minus) or blst[i][1] == 0:
        break

if minus % 2 == 0:
    ans = 1
    for num in ans_lst:
        ans *= num
        ans %= MOD
    print(ans)

else:
    minus_s = last_minus * next_minus
    plus_s = last_plus * next_plus
    ans = 1
    if minus_s == plus_s == 0:
        if last_minus == 0:
            ans_lst.remove(last_plus)
            ans_lst.append(next_minus)
        else:
            ans_lst.remove(last_minus)
            ans_lst.append(next_plus)
        
    elif minus_s > plus_s:
        ans_lst.remove(last_plus)
        ans_lst.append(next_minus)
    else:
        ans_lst.remove(last_minus)
        ans_lst.append(next_plus)
    for num in ans_lst:
        ans *= num
        ans %= MOD
    print(ans)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
MOD=10**9+7
p=[]
n=[]
for i in range(N):
    if A[i]<0:
        n.append(A[i])
    else:
        p.append(A[i])
p.sort(reverse=True)
n.sort()
numplus=len(p)
if numplus==0:
    ans=1
    for i in range(1,K+1):
        ans=(ans*n[i*(-1)])%MOD
elif N==K:
    ans=1
    for i in range(N):
        ans=(ans*A[i])%MOD
else:
    if numplus>=K:
        x=numplus
    else:
        if (K-numplus)%2==1:
            x=numplus-1
        else:
            x=numplus
    ans=1
    for i in range(x):
        ans=(ans*p[i])%MOD
    for i in range(K-x):
        ans=(ans*n[i])%MOD
    temp=ans
    bai=1
    while x>1:
        if len(n)<(K-x+2):
            break
        bai*=(n[K-x]*n[K-x+1])/(p[x-1]*p[x-2])
        temp=(temp*n[K-x]*n[K-x+1])%MOD
        temp=(temp*pow(p[x-1]*p[x-2],MOD-2,MOD))%MOD
        if bai>1:
            ans=temp
            bai=1
        x-=2
print(ans)

Submission status: Runtime Error

Solution code:
from numba import jit
@jit(cache = True)
def resolve():
    from bisect import bisect_left
    n,k=map(int,input().split())
    a=sorted(list(map(int,input().split())))
    m=bisect_left(a,0)
    MOD=10**9+7
    if m==0 or m==n:
        ans=1
        for i in a[-k:]:
            ans=(ans*i)%MOD
    else:
        for i in range((m//2)*2,-2,-2):
            ans=0
            cal=1
            if k-i>n-m:
                break
            for j in a[:i]:
                cal=(cal*j)%MOD
            if k-i>0:
                for j in a[-(k-i):]:
                    cal=(cal*j)%MOD
            ans=max(ans,cal)
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
S = []
for i in range(N):
    if A[i] > 0:
        p = i
        break
D = A[:p]
B = []
for i in D:
    B.append(i)
B.sort()
C = A[p:]
for i in range(p):
    S.append(-A[i])
for i in range(p,N):
    S.append(A[i])
S.sort()
i = 0
while B:
    if S[i] == B[0]:
        S[i] = -S[i]
        B.pop(0)
    i += 1

Submission status: Runtime Error

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    MOD = 10 ** 9 + 7
    B = []
    minus = [False] * N
    flag = False
    for i in range(N):
        if A[i] == 0:
            continue
        if A[i] < 0:
            minus[i] = True
        if A[i] > 0:
            flag = True
        B.append([abs(A[i]),i])

    if not flag:
        if N - len(B) != 0:
            print(0)
            exit()
        B.sort()
        ans = 1
        for i in range(K):
            ans *= A[B[i][1]]
            ans %= MOD
            
        print(ans)
        exit()

    if K >= len(B):
        if len(B) == N:
            ans = 1
            for i in range(N):
                ans *= A[i]
                ans %= MOD
            print(ans)
            exit()
        else:
            print(0)
            exit()

    B.sort(reverse=True)
    cnt = 0
    cand = []
    min_minus = -1
    min_plus = -1
    for i in range(K):
        if minus[B[i][1]]:
            cnt += 1
            min_minus = B[i][1]
        else:
            min_plus = B[i][1]
        cand.append(B[i][1])
    ans = 1

    if cnt % 2 == 0:
        for i in cand:
            ans *= A[i]
            ans %= MOD
    else:
        if cnt == minus.count(True):
            cand.pop(min_minus)
            for i in range(K,len(B)):
                if B[i][0] > 0:
                    cand.append(B[i][1])
                    break
            else:
                cand.append(min_minus)
            for i in cand:
                ans *= A[i]
                ans %= MOD
        else:
            if A[min_plus] > A[min_minus]:
                cand.pop(min_minus)
                for i in range(K,len(B)):
                    if B[i][0] > 0:
                        cand.append(B[i][1])
                        break
                else:
                    cand.append(min_minus)
            elif A[min_plus] < A[min_minus]:
                cand.pop(min_plus)
                for i in range(K,len(B)):
                    if B[i][0] < 0:
                        cand.append(B[i][1])
                        break
            else:
                cand.pop(max(min_plus,min_minus))
                cand.append(max(min_plus,min_minus) + 1)

            for i in cand:
                ans *= A[i]
                ans %= MOD

            
    print(ans)

    


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
lis = list(map(int,input().split()))
def shinchan(before,after):
    ans = 1
    key = 1
    for i in range(k):
        if key and abs(lis[i]) == before:
            ans *= after
            key = 0
        else:
            ans *= abs(lis[i])
        ans %= 10 ** 9 + 7
    return ans
plus = 0
minus = 0
zero = 0
p,m = [],[]
for num in lis:
    if num > 0:
        plus += 1
        p.append(num)
    elif num < 0:
        minus += 1
        m.append(num)
    else:
        zero += 1
p.sort(reverse=True)
m.sort(key = lambda x:abs(x),reverse=True)
lis.sort(key=lambda x:abs(x),reverse=True)
zissaiplus = 0
zissaiminus = 0
zissaizero = 0
for i in range(k):
    if lis[i] > 0:
        zissaiplus += 1
    elif lis[i] < 0:
        zissaiminus += 1
    else:
        zissaizero += 1
if zissaizero > 0:
    print(0)
    exit()
if zissaiminus % 2 == 0:
    ans = shinchan(-1,-1)
    print(ans)
    exit()
else:
    key1,key2 = 0,0
    if zissaiminus > 0 and plus-zissaiplus > 0:
        be1 = -m[zissaiminus-1]
        af1 = p[zissaiplus]
        key1 = 1
    if zissaiplus > 0 and minus-zissaiminus > 0:
        be2 = p[zissaiplus-1]
        af2 = -m[zissaiplus]
        key2 = 1
    if key1 == 1 and key2 == 1:
        if be2 * af1 >= be1 * af2:
            ans = shinchan(be1,af1)
        else:
            ans = shinchan(be2,af2)
    elif key1 or key2:
        if key1:
            ans = shinchan(be1,af1)
        else:
            ans = shinchan(be2,af2)
    else:
        lis.sort(key=lambda x:abs(x))
        ans = -shinchan(0,0)+10 ** 9 + 7
    print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))

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

ans = []
negidx = 0
posidx = 0
neg = False
for i in range(K):
  a = A[i]
  ans.append(a)
  if a<0:
    negidx = i
    neg = not neg
  else:
    posidx = i
#print(ans, neg, negidx)
answer = 1
if neg:
  poppos = list(ans)
  pg = poppos.pop(posidx)
  popneg = list(ans)
  ng = popneg.pop(negidx)
  pgratio = None
  ngratio = None
  found = 0
  for i in range(K+1, N):
    if A[i]>=0 and ngratio is None:
      found = 1
      popneg.append(A[i])
      ngratio = -A[i]/ng
    if A[i]<0 and pgratio is None:
      found = 2
      poppos.append(A[i])
      pgratio = -A[i]/pg
    if pgratio is not None and npratio is not None:
      found = 3
      break
  if found == 1:
    for a in popnep:
      answer *= abs(a)%1000000007
    print(answer%1000000007)
  elif found == 2:
    for a in poppos:
      answer *= abs(a)%1000000007
    print(answer%1000000007)
  elif found == 3:
    if pgratio > ngratio:
      for a in poppos:
        answer *= abs(a)%1000000007
      print(answer%1000000007)
    else:
      for a in popneg:
        answer *= abs(a)%1000000007
      print(answer%1000000007)
  else:
    for i in range(K):
      answer *= A[-(i+1)]%1000000007
    print(answer%1000000007)
else:
  for a in ans:
    answer *= abs(a)%1000000007
  print(answer%1000000007)

Submission status: Runtime Error

Solution code:
from numba import jit
@jit
def resolve():
    from bisect import bisect_left
    n,k=map(int,input().split())
    a=sorted(list(map(int,input().split())))
    m=bisect_left(a,0)
    MOD=10**9+7
    if m==0 or m==n:
        ans=1
        for i in a[-k:]:
            ans=(ans*i)%MOD
    else:
        for i in range((m//2)*2,-2,-2):
            ans=0
            cal=1
            if k-i>n-m:
                break
            for j in a[:i]:
                cal=(cal*j)%MOD
            if k-i>0:
                for j in a[-(k-i):]:
                    cal=(cal*j)%MOD
            ans=max(ans,cal)
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
from sys import stdin
n,k = map(int,stdin.readline().split())
arr = sorted(list(map(int,stdin.readline().split())),key=lambda x:abs(x))
mod = 10**9+7
pos,neg = [],[]
for i in arr:
    if i>=0:
        pos.append(i)
    else:
        neg.append(i)
if not len(pos):
    ans = 1
    if k%2:
        for i in range(k):
            ans *= neg[i]
            ans %= mod
    else:
        for i in range(k):
            ans *= neg[-1-i]
            ans %= mod
else:
    ans = 1
    i=len(pos)-1
    j=len(neg)-1
    val = 0
    if n==k:
        for x in arr:
            ans *= x
            ans %= mod
    elif k==1:
        ans = pos[i]%mod
    else:
        while val != k-2:
            if i == 0:
                ans *= neg[j]
                j -= 1
            elif j == 0:
                ans *= pos[i]
                i -= 1
            else:
                if pos[i]>neg[j]:
                    ans *= pos[i]
                    i -= 1
                else:
                    ans *= neg[j]
                    j -= 1
            ans %= mod
            val += 1
        if (j-len(neg)+1)%2:
            ans *= pos[i]*neg[j]
        else:
            if i==0:
                ans *= neg[j]*neg[j-1]
            elif j==0:
                ans *= pos[i]*pos[i-1]
            else:
                ans *= max(pos[i]*pos[i-1],neg[j]*neg[j-1])
        ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
S = []
for i in range(N):
    if A[i] > 0:
        p = i
        break
D = A[:p]
B = []
for i in D:
    B.append(i)
B.sort()
C = A[p:]
for i in range(p):
    S.append(-A[i])
for i in range(p,N):
    S.append(A[i])

Submission status: Runtime Error

Solution code:
import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
s=1
c=0
l=0
r=-1
while True:
    if k-c>=2:
        if a[r]*a[r-1]>=a[l]*a[l+1]:
            s*=a[r]*a[r-1]
            r-=2
            c+=2
        else:
            s*=a[l]*a[l+1]
            l+=2
            c+=2
    else:
        if a[r]<0:
            s=1
            a=np.absolute(a)
            a=list(a)
            a.sort()
            while True:
                s*=a[c1]
                c1+=1
                s%=10**9+7
                if c1==k:
                    s=-s
                    print(s%10**9+7)
                    exit()
        else:s*=a[r]
        c+=1
    s%=10**9+7
    if k==c:break
print(s)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    N,K=list(map(int,sys.stdin.readline().split()))
    A=list(map(int,sys.stdin.readline().split()))

    Ap=[x for x in A if x>=0 ]
    Am=[abs(x) for x in A if x<0]

    if K==N:
        k
        out=1
        for a in A:
            out*=a
            out%=10**9+7
        
        return


    if K%2==1 and len(Ap)==0:
        Am.sort()
        out=1
        for i in range(K):
            out*=Am[i]
            out%=10**7+1
        print((-out)%(10**9+7))
        return

    Ap.sort(reverse=True)
    Am.sort(reverse=True)
    
    ap_idx=0
    am_idx=0
    result=1
    for _ in range(0,K,2):
        if K%2==0 and ap_idx+1<len(Ap):
            pmax=Ap[ap_idx]*Ap[ap_idx+1]
        elif K%2==1 and ap_idx+2<len(Ap):
            pmax=Ap[ap_idx]*Ap[ap_idx+1]
        else:
            pmax=-1

        if am_idx+1<len(Am):
            mmax=Am[am_idx]*Am[am_idx+1]
        else:
            mmax=-1

        if pmax==-1 and mmax==-1:
            break

        if pmax>mmax:
            result*=pmax
            ap_idx+=2
        else:
            result*=mmax
            am_idx+=2

        result%=(10**9+7)
    
    if K%2==1:
        result*=Ap[ap_idx]

    print(result%(10**9+7))

main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

from fractions import Fraction

MODULUS = 10**9+7

def all_negative(arr):
    for _, s in arr:
        if s != -1: return False
    return True

def has_negative(arr):
    for _, s in arr:
        if s == -1: return True
    return False

def has_positive(arr):
    for _, s in arr:
        if s == 1: return True
    return False

def largest_negative(arr):
    candidates = []
    for a, s in arr:
        if s == -1: candidates += [a]
    return max(candidates)

def largest_positive(arr):
    candidates = []
    for a, s in arr:
        if s == 1: candidates += [a]
    return max(candidates)

def smallest_negative(arr):
    candidates = []
    for a, s in arr:
        if s == -1: candidates += [a]
    return min(candidates)

def smallest_positive(arr):
    candidates = []
    for a, s in arr:
        if s == 1: candidates += [a]
    return min(candidates)

def prod(arr, MODULUS=None):
    ret = 1
    for a in arr:
        ret *= a
        if MODULUS is not None:
            ret = ret % MODULUS
    return ret

def sgn(x):
    if x == 0: return 0
    if x > 0: return 1
    if x < 0: return -1
    assert(False)

N, K = input().split(' ')
K = int(K)

A = input().split(' ')
A = list(map(int, A))
old_A = A
A = [(abs(a), sgn(a)) for a in A]
A = sorted(A)[::-1]

# print(f"A={A}")

if prod(s for (_, s) in A[0:K]) in [0, 1]:
    print(prod([a for (a, _) in A[0:K]], MODULUS))
    exit(0)

chosen, not_chosen = A[0:K], A[K:]

penalty_one = float("-inf")
if has_positive(not_chosen):
    penalty_one = Fraction(largest_positive(not_chosen), smallest_negative(chosen))

penalty_two = float("-inf")
if has_positive(chosen) and has_negative(not_chosen):
    penalty_two = Fraction(largest_negative(not_chosen), smallest_positive(chosen))

if penalty_one == float("-inf") and penalty_two == float("-inf"):
    if all_negative(chosen) and all_negative(not_chosen):
        A = A[::-1]
        print(prod([a*s for (a, s) in A[0:K]], MODULUS))
    else:
        assert(0 in old_A)
        print(0)
    exit(0)

start = prod([a for (a, _) in chosen], MODULUS)

# print(penalty_one, penalty_two)

penalty = max(penalty_one, penalty_two)

start *= penalty.numerator
start *= pow(penalty.denominator, MODULUS-2, MODULUS)

start = ((start % MODULUS) + MODULUS) % MODULUS

print(start)

Submission status: Runtime Error

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

chkp,chkm=1,1
for i in range(n):
    if ax[i]>0: a.append([abs(ax[i]),1]);chkm=0
    elif ax[i]<0: a.append([abs(ax[i]),-1]);chkp=0
    else: a.append([0,0])
a=sorted(a,reverse=True)

if chkp==1:
    ans=1
    for i in range(k):
        ans=ans*a[i][0]%mod
    print(ans)
    sys.exit()

if chkm==1:
    ans=1
    for i in range(n-1,n-k-1,-1):
        ans=ans*a[i][0]%mod
    print(mod-ans)
    sys.exit()


lastp,lastm=-1,-1
cntm=0
ans=1
for i in range(k):
    [p,sgn]=a[i]
    ans=ans*p%mod
    if sgn==1: lastp=p
    elif sgn==-1:
        lastm=p
        cntm=cntm^1
        
if cntm==0 or ans==0: print(ans)
else:
    newp,newm=-1,-1
    for i in range(k+1,n):
        if a[i][1]==-1: newm=a[i][0];break
    for i in range(k+1,n):
        if a[i][1]>=0: newp=a[i][0];break

    x=1 if (lastp!=-1 and newm!=-1) else 0
    y=1 if (lastm!=-1 and newp!=-1) else 0
    if x==1 and y==1:
        if newp*lastp>=newm*lastm: ans=ans*inv(lastm,mod)*newp
        else: ans=ans*inv(lastp,mod)*newm
    elif x==-1 and y==1: ans=ans*inv(lastm,mod)*newp
    elif x==1 and y==-1: ans=ans*inv(lastp,mod)*newm
    print(ans)



def inv(a,m):
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9+7
a1 = []
a2 = []
cnt = 0
for i in a:
    if (i >= 0):
        a1.append(i)
    else:
        a2.append(-i)
a1.sort()
a2.sort()
#print(a1,a2)
if (len(a1)==0):
    if (k%2==0):
        ans = 1
        for i in range(k):
            ans *= a2.pop()
            ans %= mod
        print(ans)
        exit()
    else:
        ans = 1
        for i in range(k):
            ans *= -a2[i]
            ans %= mod
        print(ans)
        exit()
elif (len(a2)==0):
    ans = 1
    for i in range(k):
        ans *= a1.pop()
        ans %= mod
    print(ans)
    exit()
bef1 = 0
bef2 = 0
ans = 1
for i in range(k):
    if (len(a1)==0):
        x = a2.pop()
        ans *= x
        ans %= mod
        cnt += 1
        continue
    if (len(a2)==0 or a1[-1]>=a2[-1]):
        x = a1.pop()
        ans *= x
        ans %= mod
        bef1 = x
    else:
        x = a2.pop()
        ans *= x
        ans %= mod
        cnt += 1
        bef2 = x
if (cnt%2==1):
    if len(a1)>0 and len(a2)>0:
        A = a1[-1]/bef2
        B = a2[-1]/bef1
        if (A>=B):
            ans *= a1[-1]
            ans *= pow(bef2,mod-2,mod)
            ans %= mod
        else:
            ans *= a2[-1]
            ans *= pow(bef1,mod-2,mod)
            ans %= mod
    elif (len(a1)==0):
        ans *= a2[-1]
        ans *= pow(bef1,mod-2,mod)
        ans %= mod
    else:
        ans *= a1[-1]
        ans *= pow(bef2,mod-2,mod)
        ans %= mod
    
print(ans)

Submission status: Runtime Error

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

if sum(v == 0 for v in A) > N - K:
    print(0)
    exit()


if all(v <= 0 for v in A):
    x = sorted([v for v in A if v < 0])
    ans = 1
    if K % 2 == 0:
        for i in range(K):
            ans = ans * x[i] % MOD
    else:
        for i in range(N - K, N):
            ans = ans * x[i] % MOD
            
    print(ans)
    exit()


x = sorted([(abs(v), v // abs(v)) for v in A if v != 0])
plus = []
minus = []
for i in range(K):
    v, s = x.pop()
    if s == 1:
        plus.append(v)
    else:
        minus.append(v)


if len(minus) % 2 != 0:
    p_cand = MOD
    m_cand = MOD
    while x:
        v, s = x.pop()
        if s == 1 and p_cand == MOD:
            p_cand = v
        elif s == -1 and m_cand == MOD:
            m_cand = v
    
    if p_cand == MOD and m_cand != MOD and plus:
        plus.pop()
        minus.append(m_cand)
    elif m_cand == MOD and p_cand != MOD and minus:
        minus.pop()
        plus.append(p_cand)
    elif p_cand != MOD and m_cand != MOD and plus and minus:
        p_val = plus.pop() * p_cand
        m_val = minus.pop() * m_cand
        
        if p_val > m_val:
            plus.append(p_val)
        else:
            minus.append(m_val)
            
ans = 1
for v in plus:
    ans = ans * v % MOD
for v in minus:
    ans = ans * (-v) % MOD
print(ans)