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:
from sys import stdin
input = stdin.readline

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

ans = 1
mod = 10 ** 9 + 7

minus_cnt = 0
for a in A:
    if a < 0:
        minus_cnt += 1

if K == 1:
    print(max(A))
elif K == N:
    for a in A:
        ans *= abs(a)
        ans %= mod
    if minus_cnt % 2 == 1:
        ans *= (-1)
    print(ans % mod)
else:
    minus_cnt = 0
    new_A = []
    select_ls = []

    for a in A:
        new_A.append([abs(a), 0 if a >= 0 else -1])
    new_A.sort(reverse=True)

    for i in range(K):
        select_ls.append(new_A[i])
        minus_cnt += new_A[i][1]

    if minus_cnt % 2 == 0:
        for s in select_ls:
            ans *= s[0]
            ans %= mod
        print(ans)
    else:
        ok = False
        for i in range(K, N):
            if new_A[i][1] == 0:
                ok = True
                ans *= new_A[i][0]
                select_ls.sort()
                skip = False
                for j in range(len(select_ls)):
                    if select_ls[j][1] == -1:
                        if skip:
                            ans *= select_ls[j][0]
                        else:
                            skip = True
                            continue
                    else:
                        ans *= select_ls[j][0]
                    ans %= mod
        if not ok:
            if 0 in A:
                print(0)
                exit()
            new_A.sort()
            for i in range(K):
                ans *= new_A[i][0]
                ans %= mod
            ans *= (-1)
        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 = 10**9+7
p = []
m = []
ans = 1
for i in a:
    if i < 0:
        m.append(-i)
    else:
        p.append(i)
cp = len(p)
cm = len(m)
m.append(0)
m.append(0)
p.append(0)
p.append(0)
p.sort()
m.sort()
p = deque(p)
m = deque(m)
if cp>=k or (k-cp)%2 == 0 or ((cm > k) and cp):
    f = 0
else:
    f = 1 
if f == 0:
    while k:
        # print(k,cm,m)
        if k%2 == 1 and cp:
            p1 = deque.pop(p)
            ans *= p1
            k -= 1
            cp -= 1
        elif f == 0 and m[-1] * m[-2] > p[-1] * p[-2] and cm > 1 and k>1:
            m1 = deque.pop(m)
            m2 = deque.pop(m)
            ans *= m1 * m2
            cm -= 2
            k -= 2
        elif cp > 0:
            p1 = deque.pop(p)
            ans *= p1
            k -= 1
            cp -= 1
        else:
            
            ans *= -m[2]
            m1 = deque.popleft(m)
            m2 = deque.popleft(m)
            m3 = deque.popleft(m)
            deque.appendleft(m,m1)
            deque.appendleft(m,m2)
            cm -= 1
            k -= 1
        ans %= mod
else:
    m1 = deque.popleft(m)
    m2 = deque.popleft(m)
    m1 = deque.popleft(p)
    m2 = deque.popleft(p)
    deque.append(m,10**10)
    deque.append(p,10**10)
    while k:
        k-=1
        # print(p,m)
        if p[0] < m[0]:
            ans *= deque.popleft(p)
        else:
            ans *= -deque.popleft(m)
        ans %= mod

print(ans)

Submission status: Wrong Answer

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

l_pos=[]
l_neg=[]
for i in range(n):
  if l[i]<0:
    l_neg.append(l[i])
  else:
    l_pos.append(l[i])

l_neg.sort()
l_pos.sort()
a=len(l_neg)
b=len(l_pos)
a=a-1
b=b-1

if len(l_neg)==0:
  ans=1
  for i in range(k):
    ans*=l_pos[-1-i]
    ans=ans%mod

elif len(l_pos)==0:
  ans=1
  for j in range(k):
    ans*=l_neg[i]
    ans=ans%mod

elif k==n:
  ans=1
  for i in range(n):
    ans*=l[i]
    ans=ans%mod

else:
  ans=1
  cntodd=0
  while a>0 and b>0:
    if l_pos[b]>=abs(l_neg[a]):
      ans*=l_pos[b]
      ans=ans%mod
      b-=1
    
    elif l_pos[b]<abs(l_neg[a]):
      ans*=l_pos[b]
      ans=ans%mod
      a-=1
      cntodd+=1
    k-=1
    if k==1:
      break

  if cntodd%2==0 and k==1:
    ans*=l_pos[b]
    k-=1
  elif cntodd%2!=0 and k==1:
    if a+1<len(l_neg):
      a+=1
    ans=ans//l_neg[a]
    ans*=l_pos[b]
    k-=1
  if k>0:
    while b>0:
      ans*=l_pos[b]
      b-=1
      k-=1
      if k==0:
        break
  
  
 
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n, k = inpl()
a = inpl()
data = [[abs(i), i < 0] for i in a]
all_minus = 0
for t in data:
    if t[1]:
        all_minus += 1
if all_minus == n:
    ans = 1
    data.sort()
    for i in range(k):
        ans = ans * data[i][0] % mod
    ans=ans*((-1)%mod)
    print(ans % mod)
    exit()
data.sort(reverse=True)
last_minus = 0
last_plus = 0
ans = 1
minus_amount = 0
for i in range(k):
    elem, sign = data[i][0], data[i][1]
    if elem == 0:
        print(0)
        exit()
    ans = ans * elem % mod
    minus_amount += sign
    if sign:
        last_minus = elem
    else:
        last_plus = elem
if minus_amount % 2 == 0:
    print(ans%mod)
    exit()
if n==k:
    print(-ans % mod)
    exit()
tmp_plus = 0
tmp_minus = 0
for i in range(k, n):
    elem, sign = data[i][0], data[i][1]
    if last_plus and sign and not tmp_minus:
        tmp_minus = elem
    elif last_minus and not sign and not tmp_plus:
        tmp_plus = elem
if tmp_plus == 0 and tmp_minus == 0:
    ans = 0
elif last_plus == 0:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
elif last_minus == 0:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
elif tmp_plus * last_plus > tmp_minus * last_minus:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
else:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
print(ans)

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 = 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:
# import time
# t1=time.time()
def LI():return list(map(int,input().split()))
def I(): return int(input())
from collections import deque, Counter, defaultdict
# from heapq import heappop, heappush
# from pprint import pprint
# import numpy as np
# import itertools

MOD=10**9+7

n,k=LI()
a=LI()
if k==1:
    a.sort()
    print(a[-1]%MOD)
    exit()
if n==k:
    ans=1
    for i in range(k):
        ans=ans*a[i]%MOD
    print(ans)
    exit()
    
minus=[]
plus=[]
for q in a:
    if q>=0:
        plus.append(q)
    else:
        minus.append(q)
if len(plus)==n:
    plus.sort(reverse=True)
    ans=1
    for i in range(k):
        ans=ans*plus[i]%MOD
    print(ans)
    exit()
    
if len(minus)==n:
    if k%2==0:
        minus.sort()
        ans=1
        for i in range(k):
            ans=ans*minus[i]%MOD
        print(ans)
        exit()
    else:
        minus.sort(reverse=True)
        ans=1
        for i in range(k):
            ans=ans*minus[i]%MOD
        print(ans)
        exit()
      
if k%2==0:
    if len(minus)==1:
        plus.sort(reverse=True)
        ans=1
        for i in range(k):
            ans=ans*plus[i]%MOD
        print(ans)
        exit()
    if len(minus)>=2:
        minus.sort()
        minus=deque(minus)
        while True:
            if len(minus)<=1:
                break
            if k==1:
                break
            a=minus.popleft()
            b=minus.popleft()
            plus.append(a*b)
            k-=1
            
    plus.sort(reverse=True)
    ans=1
    for i in range(k):
        ans=ans*plus[i]%MOD
    print(ans)
    exit()

if k%2==1:
    if len(minus)==1:
        if k<=len(plus):
            ans=1
            plus.sort(reverse=True)
            for i in range(k):
                ans=ans*plus[i]%MOD
            print(ans)
            exit()
        else:
            ans=1
            ans=ans*minus[0]
            plus.sort()
            for i in range(k-1):
                ans=ans*plus[i]%MOD
            print(ans)
            exit()
    else:
        minus.sort()
        minus=deque(minus)
        while True:
            if len(minus)<=1:
                break
            if k==1:
                break
            a=minus.popleft()
            b=minus.popleft()
            plus.append(a*b)
            k-=1
            
    plus.sort(reverse=True)
    ans=1
    for i in range(k):
        ans=ans*plus[i]%MOD
    print(ans)
    exit()
    
    

#     b.append(q%MOD)
# b.sort(reverse=True)
# print(b)
# ans=1
# for i in range(k):
#     ans=ans*b[i]%MOD
# print(ans)

Submission status: Wrong Answer

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:
        c_neg.pop()
        c_pos.append(pos.pop())
    for c in c_neg:
        ans *= -c
        ans %= MOD
    for c in c_pos:
        ans *= c
        ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy
mod=10**9+7
n,k=map(int,input().split())
K=copy.deepcopy(k)
A=list(map(int,input().split()))

plus,negative=[],[]
for i in A:
    if i>0:plus.append(i)
    else:negative.append(i)

plus.sort()
negative.sort()

B,C=[],[]
N,M=len(plus),len(negative)
for i in range(0,N,2):
    if i+1==N:B.append([plus[i],plus[i]])
    else:B.append([plus[i]*plus[i+1],plus[i],plus[i+1]])
for i in range(0,M,2):
    if i+1==M:C.append([negative[i],negative[i]])
    else:C.append([negative[i]*negative[i+1],negative[i],negative[i+1]])

B.sort(reverse=True)
C.sort(reverse=True)
D=copy.deepcopy(B)
E=copy.deepcopy(C)

B=deque(B)
C=deque(C)

ans,flag=1,0
while k!=0:
    if k==1:
        if ans>0:
            if len(B)>0:ans *=B.popleft()[-1]
            else:ans *=sorted(C.popleft())[0]
        else:
            if len(C)>0:ans *=sorted(C.popleft())[0]
            else:ans *=sorted(B.popleft())[-1]
        if ans<0:flag=1
        ans %=mod
        break
    else:
        if 0<len(B) and 0<len(C):
            if B[0][0]<C[0][0]:num=C.popleft()
            else:num=B.popleft()
            k -=len(num)-1
        elif len(B)==0:
            num=C.popleft()
            k -=len(num)-1
        else:
            num=B.popleft()
            k -=len(num)-1
        if ans<0:flag=1
        ans *=num[0]
        ans %=mod

if flag:
    k=K
    ans=1
    D.sort()
    E.sort()
    D=deque(D)
    E=deque(E)

    while k!=0:
        if k==1:
            if ans>0:
                if len(E)>0:ans *=sorted(E.popleft())[-2]
                else:ans *=sorted(D.popleft())[0]
            else:
                if len(D)>0:ans *=sorted(D.popleft())[0]
                else:ans *=sorted(E.popleft())[-2]
            ans %=mod
            break
        else:
            if 0<len(D) and 0<len(E):
                if D[0][0]<E[0][0]:
                    num=D.popleft()
                else:
                    num=E.popleft()
                k -=len(num)-1
            elif len(D)==0:
                num=E.popleft()
                k -=len(num)-1
            else:
                num=D.popleft()
                k -=len(num)-1
            ans *=num[0]
            ans %=mod
    print(ans%mod)
else:print(ans%mod)

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()
    
    neg = list(reversed(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:
n,k = map(int,input().split())
a=list(map(int,input().split()))
mod = 10**9+7

abs_a =sorted(a,key=lambda x:abs(x))
abs_ak = abs_a[-k:]

if 0 in abs_ak:
    ans=0
    
elif all( aa<0 for aa in a ):
    ans=1
    for aa in a[:k]:
        ans= ans*aa%mod
    
else:
    n_nega = sum(aa<0 for aa in abs_ak )   
    if n_nega%2==0:
        ans=1
        for c in abs_ak:
            ans = ans*c%mod
    else:    
        nokori = abs_a[:-k]
        
        maxposi=0
        maxnega=0
        found_posi=False
        found_nega=False
        for i in nokori[::-1]:
            if i<0 and not found_nega:
                    maxnega=i
                    found_nega=True
            if i>0 and not found_posi:
                    maxposi=i
                    found_posi=True
            if found_posi and found_nega:
                break

        minposi=float("inf")
        minnega=-float("inf")
        found_posi_inabsak=False
        found_nega_inabsak=False
        for i in abs_ak:
            if i<0 and not found_nega_inabsak:
                    minnega=i
                    found_nega_inabsak = True
            if i>0 and not found_posi_inabsak:
                    minposi=i
                    found_posi_inabsak = True
            if found_posi_inabsak and found_nega_inabsak:
                break
        
#         (found_nega and found_posi and found_posi_inabsak and found_nega_inabsak
        
        if abs(maxnega/minposi) <= abs(maxposi/minnega
                                      ) or not found_nega or not found_posi_inabsak:
            ans=1
            swap=False
            for c in abs_ak:
                if c==minnega and not swap:
                    ans = ans*maxposi%mod
                    swap=True
                else:
                    ans = ans*c%mod
        else:
            ans=1
            swap=False
            for c in abs_ak:
                if c==minposi and not swap:
                    ans = ans*maxnega%mod
                    swap=True
                else:
                    ans = ans*c%mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
def mult(lis):
  ret=1
  for i in lis:
    ret*=i
    ret%=1000000007
  return ret
n,k=map(int,input().split())
a=list(map(int,input().split()))
minus=[]
plus=[]
ch=[]
for i in a:
  if i<0:
    minus.append(i)
  else:
    plus.append(i)
if len(plus)==0 and k%2:
  minus.sort(reverse=True)
  ch.extend(minus[:k])
else:
  pls=True
  a.sort(key=lambda x: abs(x), reverse=True)
  while k>0:
    inp=a.pop(0)
    if inp<0:
      if k==1 and pls:
        continue
      pls^=1
    ch.append(inp)
    k-=1
print(mult(ch))

Submission status: Wrong Answer

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

m=[]
p=[]
z=0
for i in range(n):
    if a[i]<0:
        m.append(-a[i])
    elif a[i]>0:
        p.append(a[i])
    else:
        z+=1
m=sorted(m,reverse=True)
p=sorted(p,reverse=True)

if k>len(m)+len(p):
    print(0)
    sys.exit()

if len(p)==0:
    ans=1
    if k%2==0:
        for i in range(k):
            ans*=m[i]
            ans%=mod
        print(ans)
        sys.exit()
    else:
        for i in range(k):
            if i==k-1:
                ans*=-m[-i-1]
                ans%=mod
            else:
                ans*=m[-i-1]
                ans%=mod
        print(ans)
        sys.exit()

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



q=[]
if len(m)%2==0:
    for i in range(len(m)//2):
        q.append(m[2*i]*m[2*i+1])
else:
    for i in range(len(m)//2):
        q.append(m[2*i]*m[2*i+1])
    q.append(m[-1])

pp=0
qq=0
c=0
ans=1
if k%2==1:
    ans*=p[pp]
    pp+=1
    c+=1
while c<k:
    if pp<len(p)-1 and qq<len(q):
        if p[pp]*p[pp+1]>q[qq]:
            ans*=p[pp]
            ans%=mod
            ans*=p[pp+1]
            ans%=mod
            pp+=2
        else:
            ans*=q[qq]
            ans%=mod
            qq+=1
        
        c+=2

    elif pp>=len(p)-1:
        ans*=q[qq]
        ans%=mod
    else:
        ans*=p[pp]*p[pp+1]
        ans%=mod

print(ans)

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 = list(map(int,input().split()))
a = list(map(int,input().split()))
a.sort()
large = 10**9 + 7
num_minus = 0
for k in range(N):
    if a[k] <= 0:
        num_minus += 1

if num_minus == N and K%2 == 1:
    ans = 1
    for i in range(K):
        #print(a[K-1-i],K-1-i)
        ans *= a[N-1-i]
        ans = ans % large
    print(ans)
    exit()

large = 10**9 + 7

i_left = 0
i_right = N-1

if K == 1:
    print(a[i_right])
    exit()
ans = 1


if N - num_minus < K and K%2 == 1:
    ans = 1
    for i in range(K):
        #print(a[K-1-i],K-1-i)
        ans *= a[N-1-i]
        ans = ans % large
    print(ans)
    exit()


while K > 1:
    #print(i_right,i_left)
    if a[i_right]*a[i_right-1] >= a[i_left]*a[i_left+1]:
        ans = ans * a[i_right]
        ans = ans % large
        ans = ans * a[i_right-1]
        ans = ans % large
        i_right -= 2
    else:
        ans = ans * a[i_left]
        ans = ans % large
        ans = ans * a[i_left+1]
        ans = ans % large
        i_left += 2

    K -= 2

if K == 0:
    print(ans)
else:
    ans = ans * a[i_right]
    ans = ans % large
    print(ans)

Submission status: Wrong Answer

Solution code:
n, k = (int(x) for x in input().split())
A = list(int(x) for x in input().split())
MOD = 10**9 + 7
P = []
M = []
Z = []
for a in A:
    if a < 0:
        M.append(a)
    elif a > 0:
        P.append(a)
    else:
        Z.append(a)
P.sort()
M.sort(reverse=True)
lp = len(P)
lm = len(M)
lz = len(Z)

# どうしてもマイナスになるとき
if (lp + lm <= k and lm % 2 == 1) or (lp == 0 and k % 2 == 1):
    if lz > 0:
        print(0)
        exit()
    else:
        P += [-m for m in M]
        P.sort()
        tmp = 1
        for i in range(k):
            tmp *= P[i]
            tmp %= MOD
        print(-tmp % MOD)
        exit()

# プラスにできそうなとき
ans = 1
pindex = lp-1
mindex = lm-1
for _ in range(k // 2):
    if pindex > 0 and mindex > 0:
        p = P[pindex] * P[pindex - 1]
        m = M[mindex] * M[mindex - 1]
        if p > m:
            p %= MOD
            ans *= p
            ans %= MOD
            pindex -= 2
        else:
            m %= MOD
            ans *= m
            ans %= MOD
            mindex -= 2
    else:
        if pindex > 0:
            ans *= (P[pindex] * P[pindex - 1]) % MOD
            ans %= MOD
            pindex -= 2
        elif mindex > 0:
            ans *= (M[mindex] * M[mindex - 1]) % MOD
            ans %= MOD
            mindex -= 2
        else:
            print("ERROR!!!!")

if k % 2 == 0:
    print(ans)
    exit()
else:
    if pindex >= 0:
        ans *= P[pindex]
        ans %= MOD
        print(ans)
    else:
        print(0)

Submission status: Wrong Answer

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

mod = 10**9 + 7
p = []
m = []
z_cnt = 0

for i in range(N):
    if A[i] < 0:
        m.append(-A[i])
    elif A[i] > 0:
        p.append(A[i])
    else:
        z_cnt += 1

p.sort(reverse=True)
m.sort(reverse=True)

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

tmp = K
while(tmp > len(p)):
    tmp -= 2

ans = None
flg = True
while(tmp >= 0 and K - tmp <= len(m)):
    if flg:
        ans = 1
        tmp_list = p[:tmp] + m[:K-tmp]
        for i in tmp_list:
            ans = (ans * i) % mod
        flg = False

    elif p[tmp] * p[tmp+1] < m[K-tmp-2] * m[K-tmp-1]:
        tmp_list = p[:tmp] + m[:K-tmp]
        ans = 1
        for i in tmp_list:
            ans = (ans * i) % mod
    
    tmp -= 2

if ans != None:
    print(ans)
else:
    tmp = K - 1
    while(tmp > len(p)):
        tmp -= 2

    flg = True
    while(tmp >= 0 and K - tmp <= len(m)):
        if flg:
            ans = 1
            tmp_list = p[len(p)-tmp:] + m[len(m)-K-tmp:]
            for i in tmp_list:
                ans = (ans * i) % mod
            flg = False

        elif p[len(p)-tmp-2] * p[len(p)-tmp-1] < m[K-tmp] * m[K-tmp+1]:
            tmp_list = p[len(p)-tmp:] + m[len(m)-K-tmp:]
            ans = 1
            for i in tmp_list:
                ans = (ans * i) % mod

        tmp -= 2

    if ans != None:
        print(-ans%mod)
    else:
        print(0)

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)
            exit(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&1:
        
        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]==1 and f3==0:
                f*=ans[i][0]
                f%=mod
                f3=1
            if ans[i][1]==0 and f4==0:
                if f1==-1:
                    f1=ans[i][0]
                else:
                    f1*=ans[i][0]
                    f1%=mod
                    f4=1
        
        if(f3==0 and f4==0):
            print(0)
            exit(0)
        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)
        exit(0)

    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:
import numpy

n, kk = map(int, input().split())
a = list(map(int, input().split()))

plus = []
minus = []

for k in a:
    if k >= 0:
        plus.append(k)
    if k <= 0:
        minus.append(k)

if len(plus) == 0:
    if kk % 2 == 0:
        mi = sorted(minus)
        ans = numpy.prod(numpy.array(mi[:kk]))
    else:
        mi = sorted(minus, reverse=True)
        ans = numpy.prod(numpy.array(mi[:kk]))

    print(int(ans) % (10**9+7))

else:
    ans = 0
    for m in range(kk % 2, len(plus)+1, 2):
        mi = sorted(minus, reverse=True)
        pl = sorted(plus)
        ans = max(ans, numpy.prod(numpy.array(
            pl[:m]))*numpy.prod(numpy.array(mi[:kk-m])))

    print(int(ans) % (10**9+7))