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:
n,k=map(int,input().split())
l=sorted(list(map(int,input().split())))
t=1
for i in range(n):
    if(l[i]>=0):
       l[i]=l[i]%(1000000007)
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 = (product*A[j])%1000000007 
        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 =(product* left_product)%1000000007 
            i += 2
          
        else : 
            product =(product* right_product)%1000000007 
            j -= 2
  
    # Finally return product 
    return product 
k=maxProductSubarrayOfSizeK(l,n,k)
print(k%1000000007)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
import math
A = list(map(int,input().split()))
flag = 0
if 0 in A:
    flag = 1
A.sort()
plus = list(filter(lambda x:x>0, A))[::-1]
plus = list(map(lambda x:math.log(x),plus ))
from itertools import accumulate
acc_plu = [0] +  list(accumulate(plus))
minu = filter(lambda x:x<0, A)
minu = list(map(lambda x:math.log(-x),minu))
acc_min = [0] +  list(accumulate(minu))


if K % 2 == 0 : num = K // 2 + 1
else: num = (K + 1) // 2 
cand = []
x = K
y = 0
MOD = 10**9 +7
for i in range(num):
    try:
        cand.append((acc_plu[x] +  acc_min[y],x ,y ))
    except: pass
    x -= 2 
    y += 2


ans = 1
if cand == []:
    cnt = 0
    minu = list(filter(lambda x:x<0, A))
    for x in minu[::-1]:
        if cnt == K:break
        ans *= x
        ans %= MOD
        cnt += 1
    if flag:
        print(max(ans,0))
    else:
        print(ans)
else:
    cand = sorted(cand)[::-1]
    plus = list(filter(lambda x:x>0, A))[::-1]
    minu = list(filter(lambda x:x<0, A))
    c = cand[0]
    for i in range(c[1]):
        ans *= plus[i]
        ans %= MOD
    for i in range(c[2]):
        ans *= minu[i]
        ans %= MOD
    if flag:
        print(max(ans,0))
    else:
        print(ans)

Submission status: Wrong Answer

Solution code:
'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineering College

'''
from os import path
import sys
from functools import cmp_to_key as ctk
from collections import deque,defaultdict as dd 
from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
from itertools import permutations
from datetime import datetime
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input()
def mi():return map(int,input().split())
def li():return list(mi())
abc='abcdefghijklmnopqrstuvwxyz'
mod=1000000007
#mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]

def bo(i):
    return ord(i)-ord('a')

file = 0

def solve():
    



    # for _ in range(ii()):

    n,k=mi()
    a=li()
    pos,neg=[],[]
    zero=0
    for i in a:
        if i<0:
            neg.append(i)
        if i>0:
            pos.append(i)
        if i==0:
            zero+=1
    if n==k:
        ans1=1
        for i in a:
            ans1*=i
            ans1%=mod
        print(ans1)
        exit(0)

    if k>(len(pos)+len(neg)):
        print(0)
        exit(0)
    
    if len(pos)==0 and k%2:
        if zero:
            print(0)
        else:
            neg.sort(reverse=True)
            ans1=1
            for i in range(k):
                ans1*=neg[i]
                ans1%=mod
            print(ans1)
        exit(0)
    ans=[]

    for i in pos:
        ans.append([i,0])
    for i in neg:
        ans.append([abs(i),1])
    ans.sort(reverse=True)
    f=-1
    f1=-1
    c=0
    for i in range(k):
        if ans[i][1]:
            c+=1
            f=i
        else:
            f1=i
    if c%2:
        if len(ans)==k:
            print(0)


        else:
            ans1=1
            for i in range(k):
                if i==f or i==f1:
                    continue
                ans1*=ans[i][0]
                ans1%=mod

            if(f1!=-1):
                f1=ans[f1][0]
            f=ans[f][0]
            f3=0
            f4=0
            for i in range(k,len(ans)):
                if ans[i][1] and f3==0:
                    f*=ans[i][0]
                    f3=1
                if ans[i][1]==0 and f4==0:
                    if f1==-1:
                        f1=ans[i][0]
                    else:
                        f1*=ans[i][0]
                        f4=1
                
            if f3==0:
                ans1*=f1
                ans1%=mod
            elif(f4==0):
                ans1*=f
                ans1%=mod
            elif(f>f1):
                ans1*=f
                ans1%=mod
            else:
                ans1*=f1
                ans1%=mod
            print(ans1)

    else:
        ans1=1
        for i in range(k):
            ans1*=ans[i][0]
            ans1%=mod
        print(ans1)

























  
















if __name__ =="__main__":

    if(file):

        if path.exists('input1.txt'):
            sys.stdin=open('input1.txt', 'r')
            sys.stdout=open('output1.txt','w')
        else:
            input=sys.stdin.readline
    solve()

Submission status: Wrong Answer

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
    for i in range(k):
        ans *= -li[i][0]
        ans %= 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: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
minus_count=0
i=0
j=n-1
ans=1
count=0
MOD=(10**9)+7
#print(a)

if(a[j]<0 and k%2==1):
    for l in range(k):
        ans=((ans%MOD)*(a[j]%MOD))%MOD
        j-=1
else:
    while(count<k):
        if(count==k-1 and a[j]>0 and (abs(a[i]) > abs(a[j])) and minus_count%2==0 ):
            ans=((ans%MOD)*(a[j]%MOD))%MOD
            j-=1
        elif(a[i]==0 and a[j]==0):
            ans=0
            minus_count=0
            break
        elif(abs(a[i]) <= abs(a[j])):
            ans=((ans%MOD)*(a[j]%MOD))%MOD
            if(a[j]<0):
                minus_count+=1
            j-=1
        else:
            ans=((ans%MOD)*(a[i]%MOD))%MOD
            if(a[i]<0):
                minus_count+=1
            i+=1
#        print(i,j,ans)
        count+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split(' '))
A = sorted(list(map(int, input().split(' '))))
mod = 10 ** 9 + 7
p = 0
for i in range(N):
    if A[i] >= 0:
        break
p = i
if (p == N - 1 and K % 2 != 0):
    ans = 1
    for i in range(K):
        ans *= A[-1 - i]
        ans %= mod
    print(ans%mod)
    exit()
minus = A[:p]
plus = sorted(A[p:],reverse=True)
print(minus)
print(plus)
len_m = len(minus)
len_p = len(plus)
m = 0
p = 0
ans = 1
while K > 0:
    if K >= 2 and m <= len_m - 2 and p <= len_p - 2:
        if minus[m] * minus[m+1] >= plus[p] * plus[p + 1]:
            ans *= minus[m] * minus[m + 1]
            ans %= mod
            m += 2
        else:
            ans *= plus[p] * plus[p + 1]
            ans %= mod
            p += 2
        K -= 2
    elif K >= 2 and m <= len_m - 2:
        ans *= minus[m] * minus[m + 1]
        ans %= mod
        m += 2
        K -= 2
    elif K >= 2 and p <= len_p - 2:
        ans *= plus[p] * plus[p + 1]
        ans %= mod
        p += 2
        K -= 2
    elif p <= len_p - 1:
        ans *= plus[p]
        ans %= mod
        p += 1
        K -= 1
    else:
        ans *= minus[m]
        ans %= mod
        m += 1
        K -= 1
print(ans%mod)

Submission status: Wrong Answer

Solution code:
N , K = map(int, input().split())
A =list(map(int, input().split()))
mod = 10**9 + 7
count =0
for k in range(len(A)):
    if A[k] == 0:
        count +=1
        A[k] = float("inf")
if N-count < K:
    print(0)
    exit()
A.sort()
A = A[:N-count]
A.sort(reverse=True)
#print(A)
ans = 1
plus = 0
minus = -1
countp = 0
countm = 0
if A[0] >0:
    for k in range(K):
        if abs(A[plus]) >= abs(A[minus]):
            ans = ans*A[plus]%mod
            plus+=1
        else:
            ans = ans*A[minus]%mod
            if A[minus] <0:
                lasm = 0+minus
            minus-=1
            
    if minus%2 == 1:
        print(ans%mod)
    else:
        print(ans//A[lasm]*A[plus]%mod)
else:
    for k in range(K):
        ans = ans*A[k]%mod
    print(ans%mod)

Submission status: Wrong Answer

Solution code:
from collections import deque

N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = pow(10,9)+7

A.sort(reverse=True)

deque = deque()
for a in A:
    deque.append(a)

ans = 1
cnt = 0
if K%2 == 1:
    ans *= deque.popleft()
    cnt += 1
    
if ans <= 0:
    for i in range(K-1):
        ans *= deque.popleft()
        ans %= mod
else:
    while cnt < K:
        x1 = deque.popleft()
        x2 = deque.popleft()
        if deque:
            y1 = deque.pop()
        else:
            pop = -pow(10,9)-1
        if deque:
            y2 = deque.pop()
        else:
            pop = -pow(10,9)-1
        if x1*x2 < y1*y2:
            ans *= y1*y2
            ans %= mod
            deque.appendleft(x2)
            deque.appendleft(x1)
            cnt += 2
        else:
            ans *= x1*x2
            ans %= mod
            deque.append(y2)
            deque.append(y1)
            cnt += 2
            
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter, deque

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

MOD = 10 ** 9 + 7

c = Counter()
for a in A:
    if a == 0:
        c['0'] += 1
    elif a < 0:
        c['-'] += 1
    else:
        c['+'] += 1

if c['-'] + c['+'] < K:
    print(0)
elif (c['-'] == N and K % 2 == 1) or (N == K and c['-'] % 2 == 1):
    def f(x):
        if x == 0:
            return 10 ** 9
        else:
            return abs(x)


    A = sorted(A, key=f)
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD

    print(ans)
else:
    A = sorted(A, key=lambda x: abs(x), reverse=True)
    plus = deque()
    minus = deque()

    for i in range(K):
        if A[i] >= 0:
            plus.append(A[i])
        else:
            minus.append(A[i])

    is_minus = False
    if len(minus) % 2 == 1:
        p = None
        m = None
        last_i = 0
        for i in range(K, N):
            if A[i] >= 0 and p is None:
                p = A[i]
            if A[i] < 0 and m is None:
                m = A[i]
            last_i = i
            if p is not None and m is not None:
                break
        if len(plus) == 0:
            is_minus = True
            for i in range(last_i, N):
                if A[i] >= 0:
                    plus.append(A[i])
        if m is None and p is None:
            pass
        elif m is None and p is not None:
            minus.pop()
            plus.append(p)
        elif m is not None and p is None:
            plus.pop()
            minus.append(m)
        elif minus[-1] * m > plus[-1] * p:
            plus.pop()
            minus.append(m)
        else:
            minus.pop()
            plus.append(p)

    ans = 1
    while plus:
        ans *= plus.popleft()
        ans %= MOD
    while minus:
        ans *= minus.popleft()
        ans %= MOD

    if not is_minus:
        print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), key=abs, reverse=True)

mod = 10**9+7
res = 1
last_plus_index = -1
last_minus_index = -1
p_c = 0
m_c = 0

from collections import deque
# d = deque(A)

for i in range(K):
    t = A[i]
    if t < 0:
        last_minus_index = i
        m_c += 1
    if t > 0:
        last_plus_index = i
        p_c += 1

if m_c % 2 == 0:
    for i in range(K):
        t = A[i]
        res *= t
        res = res % mod
    print(res)
    exit()

if K-1 == last_minus_index:
    for i in range(K, N):
        if A[i] > 0:
            res = res // A[last_minus_index] * A[i]
            print(res % mod)
            exit()
        if i == N-1:
            if last_plus_index != -1:
                res = res // A[last_plus_index] * A[K]
                print(res % mod)
                exit()
            else:
                # 解が0以下
                A = sorted(A, reverse=True)
                res = 1
                for i in range(K):
                    res *= A[i]
                    res = res % mod
                print(res)
                exit()

else:
    for i in range(K, N):
        if A[i] < 0:
            res = res // A[K-1] * A[i]
            print(res % mod)
            exit()
        if i == N-1:
            res = res // A[last_minus_index] * A[K]
            print(res % mod)
            exit()

Submission status: Wrong Answer

Solution code:
#coding: UTF-8
import itertools
from scipy.special import comb

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

maxList,minList = [],[]

list.sort(inList)
for i in range(k):
    minList.append(inList[i])
list.sort(inList, reverse=True)
for i in range(k):
    maxList.append(inList[i])
inList2 = minList+maxList

out = 0
for v in itertools.combinations(inList2, k):
    tmp = 1
    for i in range(len(v)):
        tmp = tmp*v[i]
    if tmp > out: out = tmp
print(out%1000000007)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
md = 10 ** 9 + 7
c = 0
T = []
for i in range(n-1):
    T.append(A[i] * A[i+1])
ans = 1

if k == n:
    for i in A:
        ans *= i % md
    print(ans % md)
    exit()

if k % 2 == 0:
    k = k//2
    T.sort()
    for i in range(k):
        ans *= T[-(i)*2-1] % md
else:
    s = k//2
    for i in range(s):
        ans *= T[-(i)*2-1] % md
    ans *= A[-k]
print(ans % md)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
M = 10**9+7
# A.sort(reverse=True)

pos = []
neg = []

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


ans = 1

# print(K, K-len(pos)%2)
if ((K - len(pos)) % 2) != 0:
    #答えマイナスになる
    # pos.sort(reverse=True)
    neg.sort()
    # print(neg)
    neg = list(reversed(neg))
    # print("neg2:", neg)

    for p in pos:
        ans *= p % M
        # ans *= p
    
    for n in neg[:K-len(pos)]:
        ans *= n % M
        # ans *= n
    # print("neg: ", ans)

    # while K > 0:
    #     if K >= 2 and len(neg) >= 2 and len(pos) >= 2:
    #         if neg[-1] * neg[-2] >= pos[-1] * pos[-2]:
    #             ans *= neg[-1] * neg[-2] % M
    #             neg.pop()
    #             neg.pop()
    #             K -= 2
    #         else:
    #             ans *= pos[-1] * pos[-2] % M
    #             pos.pop()
    #             pos.pop()
    #             K -= 2
    #     else:
    #         if K == 1:
    #             if len(pos) > 0:
    #                 ans *= pos[-1] %M               
    #             else:
    #                 ans *= neg[0] %M
    #             break
    #         else:
    #             #K<=2 or len(neg) < 2 or len(pos) < 2
    #             if len(pos) == 1 and len(neg) == 1:
    #                 ans *= pos[-1] %M
    #                 if K == 2:
    #                     ans *= neg[-1] %M
    #                     break
    #                 K -= 1
    #             elif len(pos) < 2:
    #                 ans *= neg[-1] * neg[-2] % M
    #                 neg.pop()
    #                 neg.pop()
    #                 K-= 2
    #             else:
    #                 #len(neg)が1
    #                 ans *= pos[-1] %M
    #                 pos.pop()
    #                 K -= 1

else:    
    pos.sort()
    neg.sort(reverse=True)

    while K > 0:
        if K >= 2 and len(neg) >= 2 and len(pos) >= 2:
            if neg[-1] * neg[-2] >= pos[-1] * pos[-2]:
                ans *= neg[-1] * neg[-2] % M
                neg.pop()
                neg.pop()
                K -= 2
            else:
                ans *= pos[-1] * pos[-2] % M
                pos.pop()
                pos.pop()
                K -= 2
        else:
            if K == 1:
                if len(pos) > 0:
                    ans *= pos[-1] %M               
                else:
                    ans *= neg[0] %M
                break
            else:
                #K<=2 or len(neg) < 2 or len(pos) < 2
                if len(pos) == 1 and len(neg) == 1:
                    ans *= pos[-1] %M
                    if K == 2:
                        ans *= neg[-1] %M
                        break
                    K -= 1
                elif len(pos) <= 1:
                    ans *= neg[-1] * neg[-2] % M
                    neg.pop()
                    neg.pop()
                    K-= 2
                else:
                    #len(neg)が1
                    ans *= pos[-1] %M
                    pos.pop()
                    K -= 1
                
print(ans%M)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

mod = int(10e8+7)

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

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

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

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

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

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

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

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

maxN = 0
maxP = 0

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

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

minN = n
minP = n

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

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

ans_1 = 1

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

    ans_1 *= a[i]
    ans_1 %= mod

ans_2 = 1

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

    ans_2 *= a[i]
    ans_2 %= mod

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

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
from functools import reduce
N, K = map(int, input().split())
num = np.array(list(map(int, input().split())), dtype=int)
DIVZ = 10**9 + 7

ans = -DIVZ
num.sort()
for ii in range(K//2+1):
    #s1 = reduce((lambda x, y: x * y), num[:ii*2])
    #s2 = reduce((lambda x, y: x * y), num[-ii * 2:])
    s1 = np.prod(num[:ii*2])
    s2 = np.prod(num[N - (K-ii*2):])
    if ans < float(s1)*float(s2):
        ans = float(s1)*float(s2)

print(int((ans % DIVZ)))

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
all_minus = True
for i in range(n):
  if a[i] >= 0:
    all_minus = False
    break
if all_minus:
  a.sort(key = lambda x: abs(x))
  ans = 1
  for i in range(k):
    ans *= a[i]
  ans %= mod
  print(ans)
  exit()
a.sort(key = lambda x: abs(x))
a.reverse()
ans = 1
mcnt = 0
zcnt = 0
for i in range(n):
  if a[i] == 0:
    zcnt += 1
if zcnt > n - k:
  print(0)
  exit()
b = []
for i in range(n):
  if a[i] == 0:
    continue
  b.append(a[i])
m = len(b)
for i in range(k):
  ans *= b[i]
  ans %= mod
  if b[i] < 0:
    mcnt += 1
if mcnt % 2 == 0:
  if zcnt > 0:
    ans = max(0, ans) % mod
  print(ans)
  exit()
lp = 0
lpi = -1
lm = 0
lmi = -1
for i in reversed(range(k)):
  if b[i] > 0:
    lp = b[i]
    lpi = i
    break
for i in reversed(range(k)):
  if b[i] < 0:
    lm = b[i]
    lmi = i
    break
base = ans
rm = 0
rp = 0
for i in range(k, m):
  if b[i] < 0:
    rm = b[i]
    rmi = i
    break
for i in range(k, m):
  if b[i] > 0:
    rp = b[i]
    rpi = i
    break
if lpi < 0:
  temp = 1
  for i in range(k):
    if i == lmi:
      continue
    temp *= b[i]
    temp %= mod
  temp *= rp
  temp %= mod
  ans = temp
else:
  tempA = 1
  for i in range(k):
    if i == lmi:
      continue
    tempA *= b[i]
    tempA %= mod
  tempA *= rp
  tempA %= mod
  
  tempB = 1
  for i in range(k):
    if i == lpi:
      continue
    tempB *= b[i]
    tempB %= mod
  tempB *= rm
  tempB %= mod
  
  if lp * rp > lm * rm:
    ans = tempA
  else:
    ans = tempB
if zcnt > 0:
  ans = max(0, ans) % mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 10**9+7
sei = []
hu = []
zero = []
for i in range(N):
    a = A[i]
    if a > 0:
        sei.append(a)
    elif a < 0:
        hu.append(a)
    else:
        zero.append(0)
sei.sort(reverse = True)
if len(zero) > N - K:
    print(0)
else:
    ans = 1
    p = len(sei)
    q = len(hu)
    if p == 0:
        hu.sort(reverse = True)
        for i in range(K):
            ans *= hu[i]
            ans %= MOD
        if K % 2 == 1 and len(zero) != 0:
            print(0)
        else:
            print(ans)
    elif p + q == K :
        if q %2 == 1 and len(zero) != 0:
            print(0)
        else:
            hu.sort()
            for i in range(p):
                ans *= sei[i]
                ans %= MOD
            for j in range(q):
                ans *= hu[j]
                ans %= MOD
            print(ans%MOD)
    elif q == 0:
        for i in range(K):
            ans *= sei[i]
            ans %= MOD
        print(ans)
    else:
        hu.sort()
        flag = 0
        pin = 0
        qin = 0
        r = K
        while r > 0:
            if pin == -1 and qin == -1:
                break
            elif pin == -1:
                qin += 1
                if qin == q:
                    qin = -1
                if flag == 1:
                    flag = 0
                else:
                    flag = 1
            elif qin == -1:
                pin += 1
                if pin == p:
                    pin = -1
            else:
                if abs(sei[pin])>abs(hu[qin]):
                    pin += 1
                    if pin == p:
                        pin = -1
                else:
                    qin += 1
                    if qin == q:
                        qin = -1
                    if flag == 0:
                        flag = 1
                    else:
                        flag = 0
            r -= 1
        if pin == -1:
            pin = p
        if qin == -1:
            qin = q
        if p+q == K:
            for i in range(p):
                ans *= sei[i]
                ans %= MOD
            for j in range(q):
                ans *= hu[j]
                ans %= MOD
            print(ans%MOD)
        else:
            if flag == 0:
                for i in range(pin):
                    ans *= sei[i]
                    ans %= MOD
                for j in range(qin):
                    ans *= hu[j]
                    ans %= MOD
                print(ans%MOD)
            else:
                if pin == p:
                    for i in range(pin-1):
                        ans *= sei[i]
                        ans %= MOD
                    for j in range(qin+1):
                        ans *= hu[j]
                        ans %= MOD
                    print(ans%MOD)
                else:
                    for i in range(pin+1):
                        ans *= sei[i]
                        ans %= MOD
                    for j in range(qin-1):
                        ans *= hu[j]
                        ans %= MOD
                    print(ans%MOD)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,k = map(int,readline().split())
a = list(map(int,readline().split()))
mod = 10**9+7
if n == k:
  ans = 1
  for i in a:
    ans *= i
    ans %= mod
  print(ans)
  exit()
  
p = []
P = 0
z = False
t = 0
for i in a:
  if i > 0:
    p.append((i,1))
    P += 1
  elif i == 0:
    p.append((0,0))
    z = True
  else:
    p.append((-i,-1))
    
chk = 1
p.sort()
for i in range(k):
  chk *= p[i][0]*p[i][1]
  chk %= mod
  
if P == 0 and k%2 == 1:
  if z:
    print(0)
  else:
    print(chk)
  exit()

p.sort(reverse=True)
mi_p = 0
ma_m = 0
c = 0

for i in range(k):
  if p[i][1] > 0:
    mi_p = i
  elif p[i][1] == 0:
    print(0)
    exit()
  else:
    ma_m = i
    c += 1
    
if c%2 == 0:
  ans = 1
  for i in range(k):
    ans *= p[i][0]
    ans %= mod
  print(ans)
else:
  ma_p = 0
  mi_m = 0
  for i in range(n-k):
    L = p[k+i]
    if L[1] > 0 and ma_p == 0:
      ma_p = p[k+i][0]
    if L[1] < 0 and mi_m == 0:
      mi_m = p[k+i][0]
    if ma_p*mi_m != 0:
      break
  ans_p = 1
  ans_m = 1
  for i in range(k):
    if i == ma_m:
      ans_p *= p[i][0]
    elif i == mi_p:
      ans_m *= p[i][0]
    else:
      ans_p *= p[i][0]
      ans_m *= p[i][0]
    ans_p %= mod
    ans_m %= mod
  vv = ans_p*mi_m%mod
  ww = ans_m*ma_p%mod
  print(max(chk,(vv if mi_m > 0 else chk),(ww if mi_m > 0 else chk)))

Submission status: Wrong Answer

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

mod = 10**9 + 7

Am, Ap = [], []
pm = [0, 0, 0]
Flag = True

for x in A:
  if x < 0:
    Am.append(-x)
    pm[0] += 1
  elif x == 0:
    pm[1] += 1
  else:
    Ap.append(x)
    pm[2] += 1

Am.sort()
Ap.sort()
ans = 1

if N-K < pm[1]:
  print(0)
  exit()

if pm[0] == N:
  for i in range(K):
    ans *= Am[i]
    ans %= mod
  ans = (-1)**K
  print(ans%mod)
  exit()

if K == 1:
  print(Ap[-1])
  exit()

Bm = sorted(zip(Am, [1]*pm[0]))
Bp = sorted(zip(Ap, [0]*pm[2]))

B = Bm + Bp
B.sort(reverse = True)
cnt = 0

for i in range(K):
  if i == K-1:
    cnt %= 2
    if cnt != B[i][1]:
      break
    else:
      ans *= B[i][0]
      ans %= mod
      print(ans)
      exit()
  else:
    ans *= B[i][0]
    ans %= mod
    cnt += B[i][1]

ans1 = ans
ans2 = ans * B[K-1][0] % mod

mcnt1 = 0
for i in range(K, N-pm[1]):
  if B[i][1] == cnt:
    mcnt1 += 1
    ans1 *= B[i][0]
    ans1 %= mod
    break

mcnt2 = 0
for i in range(K-2, -1, -1):
  if B[i][1] == cnt:
    mcnt2 += 1
    r = pow(B[i][0], mod-2, mod)
    ans1 *= r
    ans1 %= mod
    break

if mcnt1 == 1 and mcnt2 == 1:
  print(max(ans1, ans2))
elif mcnt1 == 1:
  print(ans1)
elif mcnt2 == 1:
  print(ans2)
else:
  ans *= B[K][0]
  ans %= mod
  print(ans)