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: Wrong Answer

Solution code:
import sys
INF = float('inf')
MOD = 10**9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 1
is_pos = 0
for ai in A:
    if ai > 0:
        is_pos += 1
if is_pos == 0 and K % 2 == 1:
    sortA = sorted(A, key=abs)    
    for ai in sortA[:K]:
        ans = (ans * ai) % MOD
    print(ans)
    sys.exit()
        
sortA = sorted(A, reverse=True, key=abs)
# print(sortA)

pos_list = [0]
neg_list = [0]


for ai in sortA[:K]:
    if ai < 0:
        neg_list += [ai]
    elif ai > 0:
        pos_list += [ai]
    else:
        print(0)
        sys.exit()
# first_pos = 0
# first_neg = 0
first_pos = INF
first_neg = INF
for i in range(K, N):
    if sortA[i] > 0 and first_pos == INF:
        first_pos = sortA[i]
    elif sortA[i] < 0 and first_neg == INF:
        first_neg = sortA[i]
len_pos = len(pos_list)
len_neg = len(neg_list)
if len_pos == 0:
    if len_neg % 2 == 1:
        for i in range(1, len_neg):
            ans = (ans * neg_list[i]) % MOD
    else:
        ans = ans * first_pos
        for i in range(1, len_neg-1):
            ans = (ans * neg_list[i]) % MOD
    print(ans)
    sys.exit()
if len_neg % 2 == 1 or K==N:
    for i in range(1, len_pos):
        ans = (ans * pos_list[i]) % MOD
    for i in range(1, len_neg):
        ans = (ans * neg_list[i]) % MOD
    print(ans)
    sys.exit()
# print(first_neg, first_pos)
if first_neg == INF and first_pos == INF:
    print(0)
    sys.exit()
if first_neg == INF:
    ans = (ans * first_pos) % MOD
    for i in range(1, len_pos):
        ans = (ans * pos_list[i]) % MOD
    for i in range(1, len_neg-1):
        ans = (ans * neg_list[i]) % MOD
    print(ans)
    sys.exit()
if first_pos == INF:
    ans = (ans * first_neg) % MOD
    for i in range(1, len_pos-1):
        ans = (ans * pos_list[i]) % MOD
    for i in range(1, len_neg):
        ans = (ans * neg_list[i]) % MOD
    print(ans)
    sys.exit()
pos2 = abs(pos_list[-1] * first_pos)
neg2 = abs(neg_list[-1] * first_neg)
if pos2 > neg2:
    ans = (ans * first_pos) % MOD
    for i in range(1, len_pos):
        ans = (ans * pos_list[i]) % MOD
    for i in range(1, len_neg-1):
        ans = (ans * neg_list[i]) % MOD
else:
    ans = (ans * first_neg) % MOD
    for i in range(1, len_pos-1):
        ans = (ans * pos_list[i]) % MOD
    for i in range(1, len_neg):
        ans = (ans * neg_list[i]) % MOD
print(ans)

Submission status: Wrong Answer

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

A.sort(reverse=True)
resArray = A[:K]
if N == 1:
    print(resArray[0])
else:
    if(resArray[0] > 0):
        for i in range(1, int(K/2)+1):
            if abs(A[(-2 * i) + 1]) > resArray[-2] and abs(A[(-2 * i)]) > resArray[-1]:
                resArray = resArray[:-2]
                resArray.append(A[(-2 * i) + 1])
                resArray.append(A[(-2 * i) ])
                resArray.sort(reverse=True)
            else:
                break
    res = 1
    for i in resArray:
        res *= i 
        res = res % LIMIT
    print(res)

Submission status: Wrong Answer

Solution code:
from math import ceil
from collections import defaultdict as dd
import sys
input=sys.stdin.readline
#t=int(input())
#while t:
n,k=map(int,input().split())
positive=[]
negative=[]
zero=[]
mod=10**9+7
l=list(map(int,input().split()))
l.sort(reverse=True)
for i in range(n):
    if(l[i]>0):
        positive.append(l[i])
    elif(l[i]==0):
        zero.append(0)
    else:
        negative.append(l[i])
positive.sort()
negative.sort(reverse=True)
com=[]
for i in range(len(negative)-1,0,-2):
    com.append(abs(negative[i]))
    com.append(abs(negative[i-1]))
#print(com)
lp=len(positive)
ln=len(negative)
lc=len(com)
#print(com)
lz=len(zero)
mul=1
if(k%2==0):
    i=lp-1
    j=lc-1
    while(k and j>0 and i>0):
        if(com[j]*com[j-1]>positive[i]*positive[i-1]):
            mul=(mul*com[j]*com[j-1])%mod
            j-=2
        else:
            mul=(mul*positive[i]*positive[i-1])%mod
            i-=2
        k-=2
    
    while (k and i>0):
        mul=(mul*positive[i]*positive[i-1])%mod
        i-=2
        k-=2
    #print(k,j)
    while(k and j>0):
        mul=(mul*com[j]*com[j-1])%mod
        j-=2
        k-=2
        #print(j,"lol")
    #print(k)
    #print(k)
    while k and i>=0:
        mul=(mul*positive[i])%mod
        i-=1
        k-=1
    #print(k)
    if(k):
        mul=0
else:
    i=lp-1
    j=lc-1
    if(positive):
        mul=positive.pop()
        i-=1
        k-=1
        while(k and j>0 and i>0):
            if(com[j]*com[j-1]>positive[i]*positive[i-1]):
                mul=(mul*com[j]*com[j-1])%mod
                j-=2
            else:
                mul=(mul*positive[i]*positive[i-1])%mod
                i-=2
            k-=2
        while (k and i>0):
            mul=(mul*positive[i]*positive[i-1])%mod
            i-=2
            k-=2
        while(k and j>0):
            mul=(mul*com[j]*com[j-1])%mod
            j-=2
            k-=2
        while k and i>=0:
            mul=(mul*positive[i])%mod
            i-=1
            k-=1
        #print(k)
        if(k):
            mul=0
    else:
        mul=1
        kk=k
        if(lz):
            mul=0
        else:
            for i in range(min(k,ln)):
                #print(negative[i])
                mul=((mul%mod)*((negative[i]+mod)%mod))%mod
                kk-=1
            if(kk):
                mul=0
print(mul)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
p=10**9+7
a_plus=[]
a_minus=[]
for ai in a:
    if ai<0:
        a_minus.append(ai)
    else:
        a_plus.append(ai)
if k-len(a_plus)>0 and (k-len(a_plus))%2==1: # ans<0
    a_plus.sort()
    a_minus.sort(reverse=True)
else:
    a_plus.sort(reverse=True)
    a_minus.sort()
# print(a_plus,a_minus)
cnt=k
ans=1
while cnt>=2 and len(a_plus)>=2 and len(a_minus)>=2:
    tmp_p=a_plus[0]*a_plus[1]
    tmp_m=a_minus[0]*a_minus[1]
    if tmp_p>tmp_m:
        ans=(ans*tmp_p)%p
        a_plus=a_plus[2:]
    else:
        ans=(ans*tmp_m)%p
        a_minus=a_minus[2:]
    cnt-=2
while cnt>=2 and len(a_plus)>=2:
    tmp_p=a_plus[0]*a_plus[1]
    ans=(ans*tmp_p)%p
    a_plus=a_plus[2:]
    cnt-=2
while cnt%2==1 and len(a_plus)>=1:
    ans=(ans*a_plus[0])%p
    a_plus=a_plus[1:]
    cnt-=1
while cnt>=2 and len(a_minus)>=2:
    tmp_m=a_minus[0]*a_minus[1]
    ans=(ans*tmp_m)%p
    a_minus=a_minus[2:]
    cnt-=2
if cnt>0:
    ans=(ans*a_minus[0])%p
    cnt-=1
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    def solve():
        ret = 1
        for i in range(n):
            if L[i][2]:
                ret *= L[i][0]
                ret %= MOD
        return ret % MOD

    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    MOD = 10 ** 9 + 7
    INF = float('inf')
    L = []
    p, m = 0, 0
    for a in A:
        if a < 0:
            m += 1
            L.append([abs(a), -1, False])
        else:
            L.append([a, 1, False])
    L = sorted(L, key= lambda x: x[0], reverse=True)
    pm = 1
    lp, lm = None, None
    for i in range(k):
        L[i][2] = True
        pm *= L[i][1]
        if L[i][1] >= 0:
            lp = i
        else:
            lm = i
    if pm >= 0:
        ans = solve()
    else:
        ans1, ans2 = -INF, -INF
        flag1, flag2 = 0, 0
        if lp:
            j = k
            while j < n:
                if L[j][1] < 0:
                    ans1 = L[j][0] / L[lp][0]
                    flag1 == 1
                    break
                j += 1
        if lm:
            l = k
            while l < n:
                if L[l][1] >= 0:
                    ans2 = L[l][0] / L[lm][0]
                    flag2 == 1
                    break
                l += 1
        if ans1 >= ans2 and flag1:
            L[lp][2] = False
            L[j][2] = True
        elif ans2 >= ans1 and flag2:
            L[lm][2] = False
            L[l][2] = True
        ans = solve()
        if ans1 == ans2 == -INF:
            L = sorted(L, key=lambda x: x[0])
            ans = 1
            for i in range(k):
                ans *= L[i][0]
                ans %= MOD
            ans = -1 * ans
    print(ans % MOD)
main()

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,K = LI()
A = LI()

plus = []
minus = []
zero = []

for i in range(N):
    if A[i] > 0:
        plus.append(A[i])
    elif A[i] < 0:
        minus.append(-A[i])
    else:
        zero.append(A[i])

plus.sort(reverse=True)
minus.sort(reverse=True)

for i in range(1,len(plus)):
    plus[i] = plus[i-1]*plus[i]

for i in range(1,len(minus)):
    minus[i] = minus[i-1]*minus[i]

"""
plus = [1]+plus
minus = [1]+minus

ans = 0 if len(zero) else -float('inf')
for i in range(K+1):
    if i < len(plus) and K-i < len(minus):
        temp = plus[i]*minus[K-i]*(-1)**((K-i)%2)
        if temp > 0 and temp > ans:
            ans = temp



plus = []
minus = []
zero = []

for i in range(N):
    if A[i] > 0:
        plus.append(A[i])
    elif A[i] < 0:
        minus.append(-A[i])
    else:
        zero.append(A[i])

plus.sort()
minus.sort()

for i in range(1,len(plus)):
    plus[i] = plus[i-1]*plus[i]

for i in range(1,len(minus)):
    minus[i] = minus[i-1]*minus[i]

plus = [1]+plus
minus = [1]+minus

for i in range(K+1):
    if i < len(plus) and K-i < len(minus):
        temp = plus[i]*minus[K-i]*(-1)**((K-i)%2)
        if temp < 0 and temp > ans:
            ans = temp

print(ans%mod)
"""

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7


def mod_mul(arr, mod):
    res = 1
    for elem in arr:
        res *= elem
        res %= mod
    return res


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(key=lambda x: abs(x), reverse=True)

    if all([e <= 0 for e in a]):
        print(mod_mul(a[n - k:], MOD))
        return

    if k == 1:
        print(max(a))
        return

    if k == n:
        print(mod_mul(a, MOD))
        return

    res = 1
    if sum(a[i] < 0 for i in range(k)) % 2 == 1:
        minus_flag = False
        for i in range(k - 1, -1, -1):
            if a[i] < 0:
                if minus_flag:
                    minus_flag = True
                else:
                    res *= a[i]
                    res %= MOD
            else:
                res *= a[i]
                res %= MOD
        for i in range(k, n):
            if a[i] >= 0:
                res *= a[i]
                res %= MOD
                break
    else:
        for i in range(k):
            res *= a[i]
            res %= MOD

    print(res)


main()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
mod = 10**9 + 7
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
a_plus = [int(x) for x in a if x > 0]
a_minus = [int(x) for x in a if x < 0]
a_abs = [abs(x) for x in a]
a_abs = sorted(a_abs, key=lambda x: abs(x))[::-1]
a = sorted(a, key=lambda x: abs(x))[::-1]
a_plus = sorted(a_plus, key=lambda x: abs(x))[::-1]
a_minus = sorted(a_minus, key=lambda x: abs(x))[::-1]

def calc(x):
    res = 1
    for i in x:
        res*=i
        res %= mod 
    return res
max_a = a[:k]
max_a_minus = []
max_a_plus = []
cnt = 0
for i in max_a:
    if i == 0:
        print(0)
        sys.exit()
    if i < 0:
        cnt += 1
        max_a_minus.append(i)
    else:
        max_a_plus.append(i)

if cnt % 2 ==0:
    print(calc(max_a))
    sys.exit()

minus_cnt = cnt
plus_cnt = k - cnt
from copy import deepcopy
if len(a_minus) <= cnt and len(a_plus) <= plus_cnt:
    ans = -float('inf')
elif len(a_minus) <= cnt:
    if len(max_a_minus) == 0:
        ans = -float("inf")
    else:
        max_a_minus.pop()
        max_a_plus.append(a_plus[plus_cnt])
        ans = calc(max_a_plus + max_a_minus)
elif len(a_plus) <= plus_cnt:
    if len(max_a_plus) == 0:
        ans = -float("inf")
    else:
        max_a_plus.pop()
        max_a_minus.append(a_minus[cnt])
        ans = calc(max_a_minus + max_a_plus)
else:
    flag1 = 1
    flag2 = 1
    if len(max_a_minus) == 0:
        ans1 = -float("inf")
        flag1 = 0
    if len(max_a_plus) == 0:
        ans2 = -float("inf")
        flag2 = 0
    if flag1:
        c1 = deepcopy(max_a_minus)
        c2 = deepcopy(max_a_plus)
        c1.pop()
        c2.append(a_plus[plus_cnt])
        ans1 = calc(c1 + c2)
    if flag2:
        c3 = deepcopy(max_a_minus)
        c4 = deepcopy(max_a_plus)
        c4.pop()
        c3.append(a_minus[cnt])
        ans2 = calc(c3 + c4)
    ans = max(ans1, ans2)
a_abs = a_abs[::-1]
ans2 = -calc(a_abs[:k])
if ans > ans2:
    print(ans%mod)
else:
    print(ans2%mod)

Submission status: Wrong Answer

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

zeros = []
pluss = []
minuss = []

for i in range(N):
    if A[i]>0:
        pluss.append(A[i])
    elif A[i]==0:
        zeros.append(A[i])
    else:
        minuss.append(A[i])

pluss = sorted(pluss, reverse = True)
minuss = sorted(minuss)


if len(pluss) + (min(len(minuss), K)//2)*2 >= K:
    answer_type = 1
elif len(zeros) > 0:
    answer_type = 2
else:
    answer_type = 3

rest = K
if answer_type == 1:
    plus_now = 0
    minus_now = 0
    minus_counter = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = -1000000000000
        
        if minus_now < len(minuss):
            minus_target = minuss[minus_now]
        else:
            minus_target = 1000000000000
        
        if plus_target >= -minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
            minus_counter += 1
    
    if minus_counter%2 == 1:
        if minus_now >= len(minuss):
            answer = answer * pow(minuss[minus_now-1],mod-2,mod)
            answer = answer * pluss[plus_now]
        elif plus_now >= len(pluss):
            answer = answer * pow(pluss[plus_now-1],mod-2,mod)
            answer = answer * minuss[minus_now]
        elif pluss[plus_now]/(-1*minuss[minus_now-1]) > -1*minuss[minus_now]/(pluss[plus_now-1]):
            answer = answer * pow(minuss[minus_now-1],mod-2,mod)
            answer = answer * pluss[plus_now]

elif answer_type == 2:
    answer = 0
elif answer_type == 3:
    minuss = sorted(minuss, reverse = True)
    pluss = sorted(pluss, reverse = True)
    plus_now = 0
    minus_now = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = 10000000000000
        
        if minus_now < len(minuss):
            minus_target = minuss[minus_now]
        else:
            minus_target = -1000000000000  
        
        if plus_target <= -minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
print(answer%mod)

Submission status: Wrong Answer

Solution code:
# Required function 
def maxProductSubarrayOfSizeK(A, n, k): 
  
    # sorting given input array 
    A.sort() 
  
    # variable to store final product of  
    # all element of sub-sequence of size k 
    product = 1
  
    # CASE I 
    # If max element is 0 and 
    # k is odd then max product will be 0 
    if (A[n - 1] == 0 and (k & 1)): 
        return 0
  
    # CASE II 
    # If all elements are negative and 
    # k is odd then max product will be 
    # product of rightmost-subarray of size k 
    if (A[n - 1] <= 0 and (k & 1)) : 
        for i in range(n - 1, n - k + 1, -1): 
            product *= A[i] 
        return product 
  
    # else 
    # i is current left pointer index 
    i = 0
  
    # j is current right pointer index 
    j = n - 1
  
    # CASE III 
    # if k is odd and rightmost element in 
    # sorted array is positive then it 
    # must come in subsequence 
    # Multiplying A[j] with product and 
    # correspondingly changing j 
    if (k & 1): 
        product *= A[j] 
        j-= 1
        k-=1
  
    # CASE IV 
    # Now k is even. So, Now we deal with pairs 
    # Each time a pair is multiplied to product 
    # ie.. two elements are added to subsequence  
    # each time. Effectively k becomes half 
    # Hence, k >>= 1 means k /= 2 
    k >>= 1
  
    # Now finding k corresponding pairs to get 
    # maximum possible value of product 
    for itr in range( k) : 
  
        # product from left pointers 
        left_product = A[i] * A[i + 1] 
  
        # product from right pointers 
        right_product = A[j] * A[j - 1] 
  
        # Taking the max product from two  
        # choices. Correspondingly changing 
        # the pointer's position 
        if (left_product > right_product) : 
            product *= left_product 
            i += 2
          
        else : 
            product *= right_product 
            j -= 2
  
    # Finally return product 
    return product

N, K = map(int, input().split())
A = list(map(int, input().split()))
print(maxProductSubarrayOfSizeK(A, N, K))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
A = list(map(int,input().split()))
B  =[0]*n
C = [0]*n
ff = 0
an = 1
t=0
u=0
for i in range(n):
  if(A[i]>=0):
    B[i]=A[i]
    C[i]= 0
    t +=1 
  else:
    B[i]=0
    C[i]=-A[i]
    u +=1
D = sorted(B,reverse=True)
E = sorted(C,reverse=True)
if(n>=2):
  if(t==0 and k%2==1):
    for i in range(k):
      an = (an*E[n-1-i])%(10**9+7)
    an = (-an)%(10**9+7)
  else:    
    for j in range(k-2):
      if(D[0]>=E[0]):
        an = (an*D[0])%(10**9+7)
        D.pop(0)
        print(an)
      else:
        an = an*E[0]%(10**9+7)
        E.pop(0)
        ff +=1
    if(ff%2==1):
      an = (an*D[0]*E[0])%(10**9+7)
    else:
      an = (an*max(D[0]*D[1],E[0]*E[1]))%(10**9+7)
else:
  an = D[0]%(10**9+7)
print(an)

Submission status: Wrong Answer

Solution code:
import sys
INF = float('inf')
MOD = 10**9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 1
is_pos = 0
for ai in A:
    if ai > 0:
        is_pos += 1
if is_pos == 0 and K % 2 == 1:
    sortA = sorted(A, key=abs)    
    for ai in sortA[:K]:
        ans = (ans * ai) % MOD
    print(ans)
    sys.exit()
        
sortA = sorted(A, reverse=True, key=abs)
# print(sortA)

pos_list = [0]
neg_list = [0]


for ai in sortA[:K]:
    if ai < 0:
        neg_list += [ai]
    elif ai > 0:
        pos_list += [ai]
    else:
        print(0)
        sys.exit()
# first_pos = 0
# first_neg = 0
first_pos = INF
first_neg = INF
for i in range(K, N):
    if sortA[i] > 0 and first_pos == INF:
        first_pos = sortA[i]
    elif sortA[i] < 0 and first_neg == INF:
        first_neg = sortA[i]
len_pos = len(pos_list)
len_neg = len(neg_list)
if len_pos == 0:
    if len_neg % 2 == 1:
        for i in range(1, len_neg):
            ans = (ans * neg_list[i]) % MOD
    else:
        ans = ans * first_pos
        for i in range(1, len_neg-1):
            ans = (ans * neg_list[i]) % MOD
    print(ans)
    sys.exit()
if len_neg % 2 == 1 or K==N:
    for i in range(1, len_pos):
        ans = (ans * pos_list[i]) % MOD
    for i in range(1, len_neg):
        ans = (ans * neg_list[i]) % MOD
    print(ans)
    sys.exit()
# print(first_neg, first_pos)
if first_neg == INF:
    ans = (ans * first_pos) % MOD
    for i in range(1, len_pos):
        ans = (ans * pos_list[i]) % MOD
    for i in range(1, len_neg-1):
        ans = (ans * neg_list[i]) % MOD
    print(ans)
    sys.exit()
if first_pos == INF:
    ans = (ans * first_neg) % MOD
    for i in range(1, len_pos-1):
        ans = (ans * pos_list[i]) % MOD
    for i in range(1, len_neg):
        ans = (ans * neg_list[i]) % MOD
    print(ans)
    sys.exit()
pos2 = abs(pos_list[-1] * first_pos)
neg2 = abs(neg_list[-1] * first_neg)
if pos2 > neg2:
    ans = (ans * first_pos) % MOD
    for i in range(1, len_pos):
        ans = (ans * pos_list[i]) % MOD
    for i in range(1, len_neg-1):
        ans = (ans * neg_list[i]) % MOD
else:
    ans = (ans * first_neg) % MOD
    for i in range(1, len_pos-1):
        ans = (ans * pos_list[i]) % MOD
    for i in range(1, len_neg):
        ans = (ans * neg_list[i]) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
mod = 10**9 + 7
plus = []
minus = []
zlen = 0
for i in map(int, input().split()):
    if i >= 0:
        plus.append(i)
    elif i < 0:
        minus.append(i)
    else:
        zlen += 1
plen = len(plus)
mlen = len(minus)
if K > plen + mlen:
    print(0)
    import sys
    sys.exit()
plus.sort(reverse=True)
minus.sort()
pp = [1]
mp = [1]
for p in plus:
    pp.append((pp[-1]*p))
for m in minus:
    mp.append((mp[-1]*(-m)))
ppm = [1]
mpm = [1]
for p in plus[::-1]:
    ppm.append((ppm[-1]*p))
for m in minus[::-1]:
    mpm.append((mpm[-1]*(-m)))
ans = -float("inf")
ans_m = float("inf")
# kこマイナスから選ぶ
for k in range(K+1):
    if mlen < k:
        continue
    if plen < K-k:
        continue
    # 最大を目指す
    if k % 2 == 0:
        tmp = mp[k] * pp[K-k]
        ans = max(ans, tmp)
    # 絶対値最小を目指す
    else:
        tmp = mpm[k] * ppm[K-k]
        ans = min(ans, tmp)
if ans == -float("inf"):
    ans = -ans_m
if ans < 0 and zlen > 0:
    print(0)
    import sys
    sys.exit()
print(ans%mod)

Submission status: Wrong Answer

Solution code:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s); sys.stdout.write('\n')
def wi(n): sys.stdout.write(str(n)); sys.stdout.write('\n')
def wia(a, sep=' '): sys.stdout.write(sep.join([str(x) for x in a])); sys.stdout.write('\n')


MOD = 10**9 + 7


def solve(n, k, a):
    a = sorted(a, reverse=True, key=lambda x: (abs(x), 1 if x >= 0 else -1))
    sign = 1
    for i in range(k):
        if a[i] < 0:
            sign = -sign
        if a[i] == 0:
            sign = 0

    if sign == 0:
        return 0

    if sign == 1:
        ans = 1
        for i in range(k):
            ans = (ans * abs(a[i])) % MOD
        return ans

    if sign == -1:
        cc = []

        more_neg = -1
        for i in range(k, n):
            if a[i] < 0:
                more_neg = i
                break

        more_pos = -1
        for i in range(k, n):
            if a[i] > 0:
                more_pos = i
                break

        taken_neg = -1
        for i in range(k-1, -1, -1):
            if a[i] < 0:
                taken_neg = i
                break

        taken_pos = -1
        for i in range(k - 1, -1, -1):
            if a[i] > 0:
                taken_pos = i
                break

        if more_neg >= 0 and taken_pos >= 0:
            cc.append((taken_pos, more_neg))
        if more_pos >= 0 and taken_neg >= 0:
            cc.append((taken_neg, more_pos))
        if len(cc) == 2 and cc[0][1] * cc[1][0] < cc[1][1] * cc[0][0]:
            cc[0], cc[1] = cc[1], cc[0]

        # cc = sorted(cc, key=lambda x: abs(a[x[1]] / a[x[0]]), reverse=True)

        if len(cc) > 0:
            ans = 1
            for i in range(k):
                if i != cc[0][0]:
                    ans = (ans * a[i]) % MOD
            ans = (ans * a[cc[0][1]]) % MOD
            return ans
        else:
            # product is negative, taking smallest
            ans = 1
            for i in range(k):
                ans = (ans * a[n-i-1]) % MOD
            return ans


import random


def gen():
    for n in range(2, 100):
        for k in range(2, n):
            for t in range(100):
                a = [random.randrange(100) - 100 for _ in range(n)]
                solve(n, k, a)
        wi(n)


def main():
    # gen()
    # return
    n, k = ria()
    a = ria()
    wi(solve(n, k, a))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys, bisect


if(__name__ == "__main__"):

    N, K = map( int, input().strip().split() )
    divisor = 10**9+7

    list_a = list( map(int, input().strip().split()) )

    """
    left, right側の2項の積で大きい方を選択
    選べるのが残り1項ならright側を選択
    """
    multiplies = 1

    if(N==K):
        for i in range(N):
            multiplies = multiplies * list_a[i] % divisor
        print(multiplies)
    else:
        list_a.sort()
        N_negative_numbers = bisect.bisect_left(list_a, 0)
        N_select_negatives = K + N_negative_numbers -N
        flag_overzero = True
        if(N_select_negatives > 0 and N_select_negatives % 2 != 0):
            flag_overzero = False
        if(flag_overzero == True):
            left = 0
            right = N-1

            multiply_right = list_a[right] * list_a[right-1]
            flag_left = True
            while(K>0):
                if(K>1):
                    K -= 2
                    if(flag_left==True):
                        multiply_left = list_a[left] * list_a[left+1]
                    else:
                        multiply_right = list_a[right] * list_a[right-1]

                    if(multiply_left > multiply_right):

                        multiply_left %= divisor
                        multiplies = multiplies * multiply_left % divisor
                        left += 2
                        flag_left=True

                    else:
                        multiply_right %= divisor
                        multiplies = multiplies * multiply_right % divisor
                        right -= 2
                        flag_left=False

                else:
                    multiplies = multiplies * list_a[right] % divisor
                    K =0
            print(multiplies)
        else:
            list_a = [ abs(list_a[i]) for i in range(N)]
            list_a.sort()
            for i in range(K):
                multiplies = multiplies * list_a[i] % divisor
            multiplies = -multiplies %divisor

            print(multiplies)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

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

    B = []
    n_plus = 0
    for a in A:
        if a >= 0:
            B.append((a, True))
            n_plus += 1
        else:
            B.append((-a, False))

    if n_plus == 0:
        A.sort(reverse=True)
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= MOD
        print(ans)
        return

    B.sort(key=lambda x: x[0], reverse=True)
    cnt = 0
    prev_minus = None
    prev_plus = None
    for i in range(K):
        b, flag = B[i]

        if flag:
            prev_plus = b
        else:
            cnt += 1
            prev_minus = b

    if prev_plus == 0:
        print(0)
        return

    if cnt % 2 == 0:
        ans = 1
        for i in range(K):
            b, flag = B[i]
            ans *= b
            ans %= MOD
        print(ans)
        return

    next_minus = None
    next_plus = None
    for i in range(K, N):
        b, flag = B[i]
        if flag:
            if next_plus is None:
                next_plus = b
        else:
            if next_minus is None:
                next_minus = b

        if b == 0:
            if next_minus is None:
                next_minus = 0

    if next_plus is not None and prev_minus is not None:
        ans1 = 1
        ignored = False
        for i in range(K):
            b, flag = B[i]

            if ignored or prev_minus != b:
                ans1 *= b
                ans1 %= MOD
                continue

            if prev_minus == b:
                ignored = True

        ans1 *= next_plus
        ans1 %= MOD
    else:
        ans1 = -INF

    if next_minus is not None and prev_plus is not None:
        ans2 = 1
        ignored = False
        for i in range(K):
            b, flag = B[i]

            if ignored or prev_plus != b:
                ans2 *= b
                ans2 %= MOD
                continue

            if prev_plus == b:
                ignored = True

        ans2 *= next_minus
        ans2 %= MOD
    else:
        ans2 = -INF

    if ans1 == -INF:
        print(ans2)
    elif ans2 == -INF:
        print(ans1)
    else:
        if prev_minus * next_minus > prev_plus * next_plus:
            print(ans2)
        else:
            print(ans1)


if __name__ == "__main__":
    main()