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:
## coding: UTF-8
import sys
N, K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 10**9 + 7

B = []
for i in range(N):
    B.append([abs(A[i]), A[i], A[i]//abs(A[i])])
#print(B)
B = sorted(B, reverse = True)
#print(B)

minus_count = 0
for i in range(K):
    if(B[i][2] == -1):
        minus_count += 1


all_minus = True
for i in range(N):
    if(B[i][2] == 1):
        all_minus = False

if(minus_count % 2 == 0):
    ans = 1
    for i in range(K):
        ans *= B[i][0]
        ans %= MOD
    print(ans)
elif(all_minus):
    C = sorted(B)
    #print(C)
    ans = 1
    for i in range(K):
        ans *= C[i][1]
        ans %= MOD
    print(ans)
else:
    #last plus -> minus
    C = B[:K]
    #print(C)
    for i in range(K-1, -1,-1):
        if(C[i][2] == 1):
            last_plus = C[i]
            del C[i]
            break
    search_minus = True
    index = K
    while search_minus:
        #print(B, index)
        if(index >= len(B)):
            break
        if(B[index][2] == -1):
            search_minus = False
            first_minus = B[index]
            C.append(first_minus)
        index += 1

    #print(first_minus, last_plus, C)
    if(search_minus):
        A_ans = -1
        A_kiroku = sys.maxsize
    else:
        A_ans = 1
        A_kiroku = last_plus[0] / first_minus[0] #割った数（これが小さい方が積が大きいはず）
        for i in range(K):
            A_ans *= C[i][1]
            A_ans %= MOD

    C = B[:K]    
    for i in range(K-1, -1,-1):
        if(C[i][2] == -1):
            last_minus = C[i]
            del C[i]
            break
    search_plus = True
    index = K
    while search_plus:
        #print(B, index)
        if(index >= len(B)):
            break        
        if(B[index][2] == 1):
            search_plus = False
            first_plus = B[index]
            C.append(first_plus)
        index += 1

    #print(first_minus, last_plus, C)
    if(search_plus):
        B_ans = -1
        B_kiroku = sys.maxsize
    else:
        B_ans = 1
        B_kiroku = last_minus[0] / first_plus[0]
        for i in range(K):
            B_ans *= C[i][1]
            B_ans %= MOD
    if(search_minus and search_plus):
        C = sorted(B)
        #print(C)
        ans = 1
        for i in range(K):
            ans *= C[i][1]
            ans %= MOD
        print(ans)
    #print(A_ans, B_ans)
    #print(last_plus, first_minus, A_kiroku)
    #print(last_minus, first_plus, B_kiroku)
    else:
        if(A_kiroku > B_kiroku):
            print(B_ans)
        else:
            print(A_ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
li_a = list(map(int, input().split()))
mod = 10**9+7
li = []
lll = 0
for i in li_a:
    if i < 0:
        li.append((abs(i), -1))
        lll += 1
    else:
        li.append((i, 1))
li.sort()
if lll == n:
    ans = 1
    if k %=1:
        for i in range(k):
            ans *= -li[i][0]
            ans %= mod
        print(ans)
        exit()
    else:
        for i in range(k):
            ans *= li[i][0]
            ans %0 mod
        print(ans)
        exit()
ans = 1
guki = 1
for i in range(n-1, n-k-1, -1):
    ans *= li[i][0]
    ans %= mod
    guki *= li[i][1]
if guki > 0:
    print(ans)
else:
    P, M, p, m = 10**6, 1000000, 1000000, 1000000
    P1, M1, p1, m1 = True, True, True, True
    for i in range(n-k, n):
        if li[i][1] > 0:
            Plus = li[i][0]
            P = i
            P1 = False
            break
    for i in range(n-k, n):
        if li[i][1] < 0:
            Mini = li[i][0]
            M = i
            M1 = False
            break
    if n-k-1 >= 0:
        for i in range(n-k-1, -1, -1):
            if li[i][1] > 0:
                plus = li[i][0]
                p = i
                p1 = False
                break
        for i in range(n-k-1, -1, -1):
            if li[i][1] < 0:
                mini = li[i][0]
                m = i
                m1 = False
                break
    ans1 = 1
    ans2 = 1
    if (not P1) and (not m1):
        for i in range(n-1, n-k-1, -1):
            if i == P:
                continue
            ans1 *= li[i][0]
            ans1 %= mod
        ans1 *= li[m][0]
        ans1 %= mod
    if (not p1) and (not M1):
        for i in range(n-1, n-k-1, -1):
            if i == M:
                continue
            ans2 *= li[i][0]
            ans2 %= mod
        ans2 *= li[p][0]
        ans2 %= mod
    if (not p1) and (not P1) and (not M1) and (not m1):
        if mini/Plus >= plus/Mini:
            print(ans1)
        else:
            print(ans2)
    elif (not p1) and (not M1):
        print(ans2)
    elif (not m1) and (not P1):
        print(ans1)
    else:
        ans = 1
        for i in range(k):
            ans *= -li[i][0]
            ans %= mod
        print(ans)

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip() # input string
ni = lambda: int(readline().rstrip()) # input int
nm = lambda: map(int, readline().split()) # input multiple int 
nl = lambda: list(map(int, readline().split())) # input multiple int to list

n, k = nm()
pos = []
neg = []
zero = 0
ans = 1
MOD = 10**9 + 7

for a in nl():
    if a == 0:
        zero += 1
    elif a > 0:
        pos.append(a)
    else:
        neg.append(a)

if zero >= (n-k+1) or ( ( len(pos) + len(neg) == k ) and ( len(neg) % 2 == 1 ) ):
    ans = 0
elif len(pos) == 0 and k % 2 == 1:
    neg.sort()
    for _ in range(k):
        ans *= neg.pop()
        ans %= MOD
else:
    pos = [0,0] + sorted(pos)
    neg = [0,0] + sorted(neg, reverse=True) #absが大きい順にpopで取れるようにする
    c_pos = []
    c_neg = []
    for _ in range(k):
        if pos[-1] <= - neg[-1]: #negのabsの方が大きい
            c_neg.append(neg.pop())
        else:
            c_pos.append(pos.pop())
    if len(c_neg) % 2 == 1:
        p = pos.pop()
        n = neg.pop()
        if abs(n/c_pos[-1]) > abs(p/c_neg[-1]):
            c_pos.pop()
            c_neg.append(n)
        else:
            c_neg.pop()
            c_pos.append(p)
    for c in c_neg:
        ans *= -c
        ans %= MOD
    for c in c_pos:
        ans *= c
        ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
li_a = list(map(int, input().split()))
mod = 10**9+7
li = []
lll = 0
for i in li_a:
    if i < 0:
        li.append((abs(i), -1))
        lll += 1
    else:
        li.append((i, 1))
li.sort()
if lll == n:
    ans = 1
    if k %=1:
        for i in range(k):
            ans *= -li[i][0]
            ans %= mod
        print(ans)
        exit()
    else:
        for i in range(k):
            ans *= li[i][0]
            ans %0 mod
        print(ans)
        exit()
ans = 1
guki = 1
for i in range(n-1, n-k-1, -1):
    ans *= li[i][0]
    ans %= mod
    guki *= li[i][1]
if guki > 0:
    print(ans)
else:
    P, M, p, m = 10**6, 1000000, 1000000, 1000000
    P1, M1, p1, m1 = True, True, True, True
    for i in range(n-k, n):
        if li[i][1] > 0:
            Plus = li[i][0]
            P = i
            P1 = False
            break
    for i in range(n-k, n):
        if li[i][1] < 0:
            Mini = li[i][0]
            M = i
            M1 = False
            break
    if n-k-1 >= 0:
        for i in range(n-k-1, -1, -1):
            if li[i][1] > 0:
                plus = li[i][0]
                p = i
                p1 = False
                break
        for i in range(n-k-1, -1, -1):
            if li[i][1] < 0:
                mini = li[i][0]
                m = i
                m1 = False
                break
    ans1 = 1
    ans2 = 1
    if (not P1) and (not m1):
        for i in range(n-1, n-k-1, -1):
            if i == P:
                continue
            ans1 *= li[i][0]
            ans1 %= mod
        ans1 *= li[m][0]
        ans1 %= mod
    if (not p1) and (not M1):
        for i in range(n-1, n-k-1, -1):
            if i == M:
                continue
            ans2 *= li[i][0]
            ans2 %= mod
        ans2 *= li[p][0]
        ans2 %= mod
    if (not p1) and (not P1) and (not M1) and (not m1):
        if mini/Plus > plus/Mini:
            print(ans1)
            print(kahf)
        else:
            print(ans2)
    elif (not p1) and (not M1):
        print(ans2)
    elif (not m1) and (not P1):
        print(ans1)
    else:
        ans = 1
        for i in range(k):
            ans *= -li[i][0]
            ans %= mod
        print(ans)

Submission status: Runtime Error

Solution code:
# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    MOD = 10**9 + 7
    As = [(abs(a), a<0) for a in A]
    As.sort()
    As = As[::-1]


    # 大きい順
    last_plus = None
    last_minus = None
    is_minus = False
    ans = 1
    for a, m in As[:K]:
        ans = (ans * a) % MOD
        is_minus ^= m
        if m:
            last_minus = a
        else:
            last_plus = a
    
    if last_plus == 0:
        print(0)
        return
    # print(As)
    # print(ans, is_minus)
    # print(last_minus, last_plus)
    # 絶対値の大きい順に選択して、答えが負のとき
    if is_minus:
        # 答えが負の場合はK番目以降の最も絶対値の大きい正負の数を探す
        next_plus = None
        next_minus = None
        has0 = False
        for a, m in As[K:]:
            if a == 0:
                has0 = True
            if m and next_minus == None:
                next_minus = a
            elif not m and next_plus == None and a != 0:
                next_plus = a
        # print(next_minus, next_plus)
        # Aが負の数だけの場合
        if next_plus == None and next_plus == None:
            if has0:
                print(0)
                return
            ans = 1
            for a, m in As[-K:]:
                ans = (ans * a) % MOD
            ans = MOD - ans
        elif next_plus == None:
            if last_plus == None:
                ans = 1
                for a, m in As[-K:]:
                    ans = (ans * a) % MOD
                ans = MOD - ans
            else:
                ans = (ans * modinv(last_plus)) % MOD
                ans = (ans * next_minus) % MOD
        elif next_minus == None:
            ans = (ans * modinv(last_minus)) % MOD
            ans = (ans * next_plus) % MOD
        else:
            a = last_plus * next_plus
            b = last_minus * next_minus
            if a > b:
                ans = (ans * modinv(last_minus)) % MOD
                ans = (ans * next_plus) % MOD
            else:
                ans = (ans * modinv(last_plus)) % MOD
                ans = (ans * next_minus) % MOD

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N,K = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype='int64')
    plus = A[np.where(A > 0)]
    minus = A[np.where(A < 0)] * -1
    
    count_p = np.count_nonzero(A > 0)
    count_m = np.count_nonzero(A < 0)
    count_zero = np.count_nonzero(A == 0)

    def p(plus, minus, K):
        plus = np.sort(plus)[::-1]
        minus = np.sort(minus)[::-1]

        if K % 2 == 0:
            r = 1
        else:
            r = plus[0]
            plus = plus[1:]
            K -= 1
        
        p = 0
        m = 0
        while K > 0:
            #print(len(plus), p, len(minus), m)
            if len(plus) <= p:
                r *= int(minus[m]*minus[m+1])
                m+=2
                K -= 2
            elif len(minus) <= m+1:
                r *= int(plus[p])
                p+=1
                K -= 1
            elif plus[p]*plus[p+1] > minus[m]*minus[m+1]:
                r *= int(plus[p])
                p+=1
                K -= 1
            else:
                r *= int(minus[m]*minus[m+1])
                m+=2
                K -= 2
        return (r+(10**9+7))%(10**9+7)
            
    def m(plus, minus, K):
        plus = np.sort(plus)
        minus = np.sort(minus)

        if K % 2 == 0:
            r = 1
        else:
            r = minus[0]
            minus = minus[1:]
            K -= 1

        p = 0
        m = 0
        while K > 0:
            if len(plus) <= p:
                r *= int(minus[m]*minus[m+1])
                m+=2
                K -= 2
            elif len(minus) <= m+1:
                r *= int(plus[p])
                p+=1
                K -= 1
            elif plus[p]*plus[p+1] < minus[m]*minus[m+1]:
                r *= int(plus[p])
                p+=1
                K -= 1
            else:
                r *= int(minus[m]*minus[m+1])
                m+=2
                K -= 2
        return (-r+(10**9+7))%(10**9+7)
            
    
    if N-K == 0:
        if count_zero > 0:
            print(0)
            return
        else:
            if count_m % 2 == 1:
                #minus
                print(m(plus, minus, K))
                return
            else:
                #plus
                print(p(plus,minus,K))
                return
    else:
        if count_p > 0:
            if count_zero <= N-K:
                #plus
                print(p(plus,minus,K))
                return
            else:
                print(0)
                return
        else:
            if count_zero > 0:
                print(0)
                return
            else:
                #minus
                print(m(plus, minus, K))
                return

main()

Submission status: Runtime Error

Solution code:
## coding: UTF-8
import sys
N, K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 10**9 + 7

B = []
for i in range(N):
    B.append([abs(A[i]), A[i], A[i]//abs(A[i])])
#print(B)
B = sorted(B, reverse = True)
#print(B)

minus_count = 0
for i in range(K):
    if(B[i][2] == -1):
        minus_count += 1


all_minus = True
for i in range(N):
    if(B[i][2] == 1):
        all_minus = False

if(minus_count % 2 == 0):
    ans = 1
    for i in range(K):
        ans *= B[i][0]
        ans %= MOD
    print(ans)
elif(all_minus):
    C = sorted(B)
    #print(C)
    ans = 1
    for i in range(K):
        ans *= C[i][1]
        ans %= MOD
    print(ans)
else:
    #last plus -> minus
    C = B[:K]
    #print(C)
    for i in range(K-1, -1,-1):
        if(C[i][2] == 1):
            last_plus = C[i]
            del C[i]
            break
    search_minus = True
    index = K
    while search_minus:
        if(B[index][2] == -1):
            search_minus = False
            first_minus = B[index]
            C.append(first_minus)
        index += 1
        if(index > len(B)):
            break
    #print(first_minus, last_plus, C)
    if(search_minus):
        A_ans = -1
        A_kiroku = sys.maxsize
    else:
        A_ans = 1
        A_kiroku = last_plus[0] / first_minus[0] #割った数（これが小さい方が積が大きいはず）
        for i in range(K):
            A_ans *= C[i][1]
            A_ans %= MOD

    C = B[:K]    
    for i in range(K-1, -1,-1):
        if(C[i][2] == -1):
            last_minus = C[i]
            del C[i]
            break
    search_plus = True
    index = K
    while search_plus:
        if(B[index][2] == 1):
            search_plus = False
            first_plus = B[index]
            C.append(first_plus)
        index += 1
        if(index > len(B)):
            break
    #print(first_minus, last_plus, C)
    if(search_plus):
        B_ans = -1
        B_kiroku = sys.maxsize
    else:
        B_ans = 1
        B_kiroku = last_minus[0] / first_plus[0]
        for i in range(K):
            B_ans *= C[i][1]
            B_ans %= MOD
    if(search_minus and search_plus):
        C = sorted(B)
        #print(C)
        ans = 1
        for i in range(K):
            ans *= C[i][1]
            ans %= MOD
        print(ans)
    #print(A_ans, B_ans)
    #print(last_plus, first_minus, A_kiroku)
    #print(last_minus, first_plus, B_kiroku)
    else:
        if(A_kiroku > B_kiroku):
            print(B_ans)
        else:
            print(A_ans)

Submission status: Runtime Error

Solution code:
from heapq import heapify,heappush,heappop
N, K = map(int,input().split())
A = list(map(int, input().split()))
MOD =1_000_000_007

B = [a for a in A if a > 0]
C = [a for a in A if a<= 0]
B.sort()
C.sort(reverse = True)
ans = 1
if N == K:
  for a in A:
    ans *= a
    ans %= MOD
elif len(B) == 0 and K % 2 == 1:
  for i in range(K):
    ans *= C[i]
    ans %= MOD
else:
  if K % 2 == 1:
    ans *= B[-1]
    B.pop()
    K -= 1
  i = 0 
  j = 0
  k = 0
  while k < K:
    #print(B,C)
    flag = 0 #Bから二つとる時に0,Cから二つとる時に1,それ以外2
    if len(B) > 2 and len(C) >2 and B[-1]*B[-2] < C[-1]*C[-2]:
      flag = 1
    elif len(B) <= 1 and len(C) > 2:
      flag = 1
    elif len(B) == 1 and len(C) == 1:
      flag = 2
      
    if flag == 0:   
      flag = True
      ans *= B[-1]*B[-2]
      ans %= MOD
      B.pop()
      B.pop()
    
    elif flag == 1:
      ans *= C[-1]*C[-2]
      ans %= MOD
      C.pop()
      C.pop()
      
    elif flag == 2:
      ans *= C[-1]*B[-1]
      ans %= MOD
      B.pop()
      C.pop()
    
    k += 2

print(ans)

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip() # input string
ni = lambda: int(readline().rstrip()) # input int
nm = lambda: map(int, readline().split()) # input multiple int 
nl = lambda: list(map(int, readline().split())) # input multiple int to list

n, k = nm()
pos = []
neg = []
zero = 0
ans = 1
MOD = 10**9 + 7

for a in nl():
    if a == 0:
        zero += 1
    elif a > 0:
        pos.append(a)
    else:
        neg.append(a)

if zero >= (n-k+1) or ( ( len(pos) + len(neg) == k ) and ( len(neg) % 2 == 1 ) ):
    ans = 0
elif len(pos) == 0 and k % 2 == 1:
    neg.sort()
    for _ in range(k):
        ans *= neg.pop()
        ans %= MOD
else:
    pos = [0] + sorted(pos)
    neg = [0] + sorted(neg, reverse=True) #absが大きい順にpopで取れるようにする
    c_pos = []
    c_neg = []
    for _ in range(k):
        if pos[-1] <= - neg[-1]: #negのabsの方が大きい
            c_neg.append(neg.pop())
        else:
            c_pos.append(pos.pop())
    if len(c_neg) % 2 == 1:
        p = pos.pop()
        n = neg.pop()
        if abs(n/c_pos[-1]) > abs(p/c_neg[-1]):
            c_pos.pop()
            c_neg.append(n)
        else:
            c_neg.pop()
            c_pos.append(p)
    for c in c_neg:
        ans *= -c
        ans %= MOD
    for c in c_pos:
        ans *= c
        ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.read
from collections import deque
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    plus = False
    for a in A:
        if a>0:
            plus = True
            break


    if K%2==1 and plus==False:
        A.sort(reverse=True)
        ans = 1
        for i in minus[:K]:
            ans *= i % MOD
        ans %= MOD
    else:
        A.sort(reverse=True)
        A = deque(A)
        ans = 1
        if K%2==1:
            ans *= A.popleft()
        for _ in range(K//2):
            if A[0]*A[1]>=A[-1]*A[-2]:
                ans *= A.popleft()*A.popleft()%MOD
            else:
                ans *= A.pop() * A.pop() % MOD
        ans %= MOD

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

mod = 10**9+7

pl = 0
zr = 0
mn = 0

a.sort()

for i in range(n):
    if a[i] == 0:
        zr += 1
    elif a[i] > 0:
        pl += 1
    elif a[i] < 0:
        mn += 1

hugo = 0

tmp = k-pl
        
if zr == 0 and pl == 0 and k % 2 == 1:
    hugo = 3#mn
elif zr == 1 and pl == 0 and k % 2 == 1:
    hugo = 2#zr
else:
    hugo = 1#pl

ans = 1
tmp_ans = 1
    
if hugo == 3:
    for i in range(k):
        ans *= a[mn-1-i]
        ans %= mod
    print(ans%mod)
elif hugo == 2:
    print(0)
else:
    if mn == 0:
        for i in range(k):
            tmp_ans *= a[n-1-i]
            tmp_ans %= mod
        print(tmp_ans)
    else:
        tmp = k
        pl_num = 0
        mn_num = 0
        while tmp > 0:
            if tmp >= 2:
                tmp -= 2
                tmp_p_seki = 1
                tmp_m_seki = 1
                if pl_num+1+1 <= n:
                    tmp_p_seki = a[pl_num+0]*a[pl_num+1]
                if mn-mn_num-1 >= 0:
                    tmp_m_seki = a[mn-mn_num-0]*a[mn-mn_num-1]
                if tmp_p_seki > tmp_m_seki:
                    tmp_seki = tmp_p_seki
                    pl_num += 2
                else:
                    tmp_seki = tmp_m_seki
                    mn_num += 2
            elif tmp == 1:
                tmp_seki = pl[pl_num]
                tmp -= 1
            tmp_ans *= tmp_seki
            tmp_ans %= mod
                    
            
        print(tmp_ans%mod)

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip() # input string
ni = lambda: int(readline().rstrip()) # input int
nm = lambda: map(int, readline().split()) # input multiple int 
nl = lambda: list(map(int, readline().split())) # input multiple int to list

n, k = nm()
pos = []
neg = []
zero = 0
ans = 1
MOD = 10**9 + 7

for a in nl():
    if a == 0:
        zero += 1
    elif a > 0:
        pos.append(a)
    else:
        neg.append(a)

if zero >= (n-k+1) or ( ( len(pos) + len(neg) == k ) and ( len(neg) % 2 == 1 ) ):
    ans = 0
elif len(pos) == 0 and k % 2 == 1:
    neg.sort()
    for _ in range(k):
        ans *= neg.pop()
        ans %= MOD
else:
    pos = [0] + sorted(pos)
    neg = [0] + sorted(neg, reverse=True) #absが大きい順にpopで取れるようにする
    c_pos = []
    c_neg = []
    for _ in range(k):
        if pos[-1] <= - neg[-1]: #negのabsの方が大きい
            c_neg.append(neg.pop())
        else:
            c_pos.append(pos.pop())
    if len(c_neg) % 2 == 1:
        p = pos.pop()
        n = neg.pop()
        if abs(n/c_pos[-1]) < abs(p/c_neg[-1]):
            c_pos.pop()
            c_neg.append(n)
        else:
            c_neg.pop()
            c_pos.append(p)
    for c in c_neg:
        ans *= -c
        ans %= MOD
    for c in c_pos:
        ans *= c
        ans %= MOD
print(ans)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip() # input string
ni = lambda: int(readline().rstrip()) # input int
nm = lambda: map(int, readline().split()) # input multiple int 
nl = lambda: list(map(int, readline().split())) # input multiple int to list

n, k = nm()
pos = []
neg = []
zero = 0
ans = 1
MOD = 10**9 + 7

for a in nl():
    if a == 0:
        zero += 1
    elif a > 0:
        pos.append(a)
    else:
        neg.append(a)

if zero >= (n-k+1) or ( ( len(pos) + len(neg) == k ) and ( len(neg) % 2 == 1 ) ):
    ans = 0
elif len(pos) == 0 and k % 2 == 1:
    neg.sort()
    for _ in range(k):
        ans *= neg.pop()
        ans %= MOD
else:
    pos = [0] + sorted(pos)
    neg = [0] + sorted(neg, reverse=True) #absが大きい順にpopで取れるようにする
    c_pos = []
    c_neg = []
    for _ in range(k):
        if pos[-1] <= - neg[-1]: #negのabsの方が大きい
            c_neg.append(neg.pop())
        else:
            c_pos.append(pos.pop())
    if len(c_neg) % 2 == 1:
        p = pos.pop()
        n = neg.pop()
        if n/c_pos[-1] < p/c_neg[-1]:
            c_pos.pop()
            c_neg.append(n)
        else:
            c_neg.pop()
            c_pos.append(p)
    for c in c_neg:
        ans *= -c
        ans %= MOD
    for c in c_pos:
        ans *= c
        ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
 
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
q=[]
cnt_plus=0
for i in range(n):
  if arr[i]>0:
    cnt_plus+=1
    heapq.heappush(q,(-arr[i],1))
  elif arr[i]<0:
    heapq.heappush(q,(arr[i],-1))
  else:
    heapq.heappush(q,(0,0))
pick=[]
prev_plus=0
prev_minus=0
cnt=0
for i in range(k):
  tmp,flag=heapq.heappop(q)
  tmp*=-1
  if flag==0:
    print(0)
    exit()
  if flag==1:
    pick.append(tmp)
    prev_plus=tmp
  if flag==-1:
    if cnt==0:
      prev_minus=tmp
      cnt+=1
    else:
      cnt=0
      pick.append(prev_minus)
      pick.append(tmp)
if cnt==0:
  ans=1
  for i in range(k):
    ans*=pick[i]
    ans%=mod
  print(ans%mod)
else:
  cand_plus=0
  cand_minus=0
  while len(q)!=0:
    tmp,flag=heapq.heappop(q)
    tmp*=-1
    if flag==1 and cand_plus==0:
      cand_plus=tmp
    if flag==-1 and cand_minus==0:
      cand_minus=tmp
  if (k%2==1 and cnt_plus==0) or (cand_plus==0 and cand_minus==0):
    if arr.count(0)!=0:
      print(0)
      exit()
    else:
      q=[]
      for i in range(n):
        heapq.heappush(q,abs(arr[i]))
      ans=1
      for _ in range(k):
        ans*=heapq.heappop(q)
        ans%=mod
      print((-ans)%mod)
  else:
    if prev_plus*cand_plus>=prev_minus*cand_minus:
      pick.append(cand_plus)
    else:
      pick.remove(prev_plus)
      pick.append(prev_minus)
      pick.append(cand_minus)
    ans=1
    for i in range(k):
      ans*=pick[i]
      ans%=mod
    print(ans%mod)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    A = sorted([int(x) for x in input().strip().split()])
    zeros = A.count(0)
    minus = len([a for a in A if a < 0])
    plus = N - zeros - minus
    max_A = max(A)
    mod = 10 ** 9 + 7
    ans = 1
    if N == K:
        ans = 1
        for k in range(K):
            ans = (ans * A[k]) % mod
        print(ans)
        return
    if max_A < 0:
        if K % 2:
            for k in range(K):
                ans = (ans * A[-1-k]) % mod
            print(ans)
            return
        else:
            for k in range(K):
                ans = (ans * A[k]) % mod
            print(ans)
            return
    elif max_A == 0:
        if A[K-1] == 0:
            print(0)
            return
        else:
            if len([a for a in A if a < 0]) % 2:
                print(0)
                return
            else:
                ind = A.index(0)
                for k in range(K):
                    ans = (ans * A[ind-k-1]) % mod
                print(ans)
                return
    else:
        if N - zeros < K:
            print(0)
            return
        if N - zeros == K:
            if minus % 2:
                print(0)
                return
            else:
                for a in A:
                    if a != 0:
                        ans = (ans * a) % mod
                print(ans)
                return
        A.sort(key=lambda x: abs(x), reverse=True)
        minus = 0
        for k in range(K):
            if A[k] < 0:
                minus += 1
                minus_last_index = k
            ans = (ans * A[k]) % mod
        if minus % 2:
            for k in range(minus_last_index):
                ans = (ans * A[k]) % mod
            cnt = minus_last_index
            k = cnt + 1
            while cnt < K:
                if A[k] >= 0:
                    ans = (ans * A[k]) % mod
                    k += 1
                    cnt += 1
                else:
                    k += 1

        print(ans)

if __name__ == '__main__':
    main()