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:
MOD = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
am = []
ap = []
for ai in a:
    if ai > 0:
        ap.append(ai)
    elif ai < 0:
        am.append(-ai)
am.sort(reverse=True)
ap.sort(reverse=True)

nm = len(am)
np = len(ap)
nz = n - np - nm
# print(am)
# print(ap)

if np + nm < k:
    ans = 0
elif np == 0:
    if k % 2 == 1:
        if nz > 0:
            ans = 0
        else:
            am.sort()
            ans = -1 + MOD
            for i in range(k):
                ans *= am[i]
                ans %= MOD
    else:
        ans = 1
        for i in range(k):
            ans *= am[i]
            ans %= MOD
elif nm == 0:
    ans = 1
    for i in range(k):
        ans *= ap[i]
        ans %= MOD
elif nm == 1 and np + nm == k:
    if nz > 0:
        ans = 0
    else:
        ans = -1 + MOD
        for i in range(np):
            ans *= ap[i]
            ans %= MOD
        for i in range(nm):
            ans *= am[i]
            ans %= MOD
elif np < k:
    if (k - np) % 2 == 1:
        idx1 = np - 1
        idx2 = k - np + 1
        if k - np + 1 > nm:
            if nz > 0:
                ans = 0
            else:
                if nm % 2 == 1:
                    ans = -1 + MOD
                else:
                    ans = 1
                for i in range(np):
                    ans *= ap[i]
                    ans %= MOD
                for i in range(nm):
                    ans *= am[i]
                    ans %= MOD
        else:
            print(idx1, idx2)
            while idx1 >= 2 and idx2 + 1 < nm and \
                ap[idx1 - 1] * ap[idx1 - 2] < am[idx2] * am[idx2 + 1]:
                idx1 -= 2
                idx2 += 2
            print(idx1, idx2)
            ans = 1
            for i in range(idx1):
                ans *= ap[i]
                ans %= MOD
            for i in range(idx2):
                ans *= am[i]
                ans %= MOD
    else:
        idx1 = np
        idx2 = k - np
        while idx1 >= 2 and idx2 + 1 < nm and \
            ap[idx1 - 1] * ap[idx1 - 2] < am[idx2] * am[idx2 + 1]:
            idx1 -= 2
            idx2 += 2
        ans = 1
        for i in range(idx1):
            ans *= ap[i]
            ans %= MOD
        for i in range(idx2):
            ans *= am[i]
            ans %= MOD
else:
    idx1 = k
    idx2 = 0
    while idx1 >= 2 and idx2 + 1 < nm and \
        ap[idx1 - 1] * ap[idx1 - 2] < am[idx2] * am[idx2 + 1]:
        idx1 -= 2
        idx2 += 2
    ans = 1
    for i in range(idx1):
        ans *= ap[i]
        ans %= MOD
    for i in range(idx2):
        ans *= am[i]
        ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
n,k=map(int,input().split())
a=list(map(int,input().split()))

b=[]
c=[]
for i in range(n):
    b.append(abs(a[i]))
    if a[i]>0:
        c.append(1)
    else:
        c.append(-1)
d=zip(b,c)
e=sorted(d)

ans=1
for i in range(n-1,n-k-1,-1):
    ans*=b[i]*c[i]
    ans%=(10**9+7)
    if i==n-k-1 and ans*a[i-1]<0:
        while(c[i]==1):
            i-=1
        if i==0 and c[i]<0:
            i=n-k-1
        ans*=b[i-1]*c[i-1]
        ans%=(10**9+7)
        
temp=1
for i in range(k):
    temp*=b[i]*c[i]
ans=max(ans,temp)

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

Submission status: Wrong Answer

Solution code:
MOD=10**9+7
import sys
N,K=map(int,input().split())
alist=list(map(int,input().split()))

num_neg=0
num_pos=0
num_zero=0
aalist=[]
for a in alist:
  if a>0:
    num_pos+=1
  elif a<0:
    num_neg+=1
  else:
    num_zero+=1
  aalist.append((abs(a),a))
aalist.sort(reverse=True)
    
if num_zero>N-K:
  print(0)
  sys.exit(0)
  
if N==K:
  answer=1
  for a in alist:
    answer*=a
    answer%=MOD
  print(answer)
  sys.exit(0)
  
pos_possible=True
if num_neg==N and K%2==1:
  pos_possible=False
    
if not pos_possible:
  aalist.sort()
  answer=1
  for i in range(K):
    aa,a=aalist[i]
    answer*=a
    answer%=MOD
  print(answer)
  sys.exit(0)
    
aalist.sort(reverse=True)
#print(aalist)
answer=1
sgn=1
for i in range(K-1):
  aa,a=aalist[i]
  answer*=a
  answer%=MOD
  if a<0:
    sgn*=-1
for i in range(K-1,N):
  aa,a=aalist[i]
  if sgn>0 and a>=0:
    answer*=a
    answer%=MOD
    break
  elif sgn<0 and a<=0:
    answer*=a
    answer%=MOD
    break
    
print(answer)

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    MOD=10**9+7
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    Q=[]
    q=[]
    flag=True
    minus=0
    plus=0
    for i in range(n):
        if A[i]<0:
            minus+=1
        elif A[i]>0:
            plus+=1

    if plus>=k:
        pass
    else:
        num=k-plus
        if num%2==0 and minus//2>=num:
            pass
        else:
            flag=False

    if flag:
        for i in A:
            if i>=0:
                heappush(Q,-i)
            else:
                heappush(q,i)
        

        while len(q)>=1:
            pv=heappop(q)
            heappush(Q,pv)
        ans=1
        for i in range(k):
            pv=-heappop(Q)
            ans=(ans*pv)%MOD

    else:
        for i in A:
            if i>=0:
                heappush(Q,i)
            else:
                heappush(q,i)
        

        while len(q)>=1:
            pv=heappop(q)
            heappush(Q,-pv)
        ans=1
        for i in range(k):
            pv=heappop(Q)
            ans=(ans*pv)%MOD
        ans=-ans
        


    
    print(ans%MOD)
    
resolve()

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,k=LI()
  l=LI()

  zero_contain=False
  if l.count(1):
    zero_contain=True

  al=[]
  for x in l:
    al.append((abs(x),x))

  al=sorted(al,key=lambda x:x[0],reverse=True)

  zero=False
  minus=0

  ansl=[]
  for ax,x in al[:k]:
    if x==0:
      zero=True
    if x<0:
      minus+=1
    ansl.append(x)

  ans=1
  for x in ansl:
    if x==0:
      ans=0
      break
    elif x>0:
      pass
    else:
      ans*=-1

  if ans>0:
    ans=1
    for x in ansl:
      ans*=x
      ans%=mod
    return ans
  elif ans<0:
    for x in ansl[::-1]:
      if x<0:
        t=x
        ansl2=copy.deepcopy(ansl)
        ansl2.remove(t)
        break
    ff=False
    for ax,x in al[k:]:
      if x>=0:
        ansl2.append(x)
        ff=True
        break
    if not ff:
      ansl2=[]
      for ax,x in al[::-1][:k]:
        ansl2.append(x)

    ans2=1
    for x in ansl2:
      ans2*=x
      ans2%=mod

    return ans2

  else:
    return 0

# main()
print(main())

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
MOD = 10**9+7
M = []
P = []
Z = []
for i in a:
    if i < 0:
        M.append(i)
    elif i > 0:
        P.append(i)
    else:
        Z.append(i)
P.sort(reverse=True)
M.sort()
lenZ = len(Z)
lenM = len(M)
lenP = len(P)
if n - k < lenZ:
    print(0)
    exit()
elif lenZ != 0 and n - k == lenZ and lenM % 2 == 1:
    print(0)
    exit()
elif n - k == lenZ:
    ans = 1
    for i in P:
        ans*=i
        ans%=MOD
    for i in M:
        ans*=i
        ans%=MOD
    if lenZ != 0 and lenM % 2 == 1: #必要ないと思うけど頭の中がこんがらがって居るので一応
        print(0)
        exit()
    print(ans)
    exit()
elif lenP == 0:
    M = M[::-1]
    ans = 1
    for i in range(k):
        ans*=M[i]
        ans%=MOD
    print(ans)
    exit()
count = 0
ans = []
i = 0
j = 0
if k % 2 == 1:
    ans.append(P[0])
    i+=1
    k-=1
    if k == 0:
        print(P[0])
        exit()
k //= 2
while count < k:
    if i+2>lenP:
        ans.append(M[j]*M[j+1])
        j+=2
        count+=1
        continue
    if j+2>lenM:
        ans.append(P[i]*P[i+1])
        i+=2
        count+=1
        continue
    p = P[i]*P[i+1]
    m = M[j]*M[j+1]
    if p > m:
        ans.append(p)
        i+=2
        count+=1
    else:
        ans.append(m)
        j+=2
        count+=1
intans = 1
for i in range(len(ans)):
    intans*=ans[i]
    intans%=MOD
print(intans)

Submission status: Wrong Answer

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

plus = []
minus = []

for a in Alist:
    if a >= 0:
        plus.append(a)
    else:
        minus.append(a)

mflg = False

if K%2!=0:
    tmp1 = K-1
else:
    tmp1 = K

if len(minus)%2!=0:
    tmp2 = len(minus)-1
else:
    tmp2 = len(minus)

tmp = min(tmp1, tmp2)
if K - tmp > len(plus):
    mflg = True


if mflg:
    minus = [-m for m in minus]
    nums = minus + plus
    nums.sort()
    ans = 1
    for k in range(K):
        ans = ans * nums[k]
        ans %= (1000000007)
    
    ans = (-ans % 1000000007)
    print(ans)

else:
    plus.sort()
    minus.sort()
    plus = plus[::-1]
    minus = [-m for m in minus]

    for k in range(0, len(minus)+1, 2):
        if K - k > len(plus):
            continue
        km = k
        kp = K - k
        break

    m = plus[:km]
    p = plus[:kp]
    ans = 1
    for i in p+m:
        ans *= i
    
    for k in range(km+2, len(minus)+1, 2):
        kp = K - k
        if kp < 0:
            break
        if plus[kp] == 0:
            break
        tmp = tmp * minus[k-2] * minus[k-1] / plus[kp] / plus[kp+1]
        ans = max(ans, tmp)
    
    ans %= 1000000007
    print(ans)

Submission status: Wrong Answer

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

A = sorted(A, reverse=True)

temp = A.copy()

B = []

count = 0
while count < K:
    if A[-1] < 0:
        if A[0] < abs(A[-1]):
            B.append(A.pop(-1))
        else:
            B.append(A.pop(0))
        count += 1
    else:
        count = K

A = temp[:K]

print(A)
print(B)

a = 1
b = 1

for num in A:
    a *= num

for num in B:
    b *= num

if a > b:
    print(a % (10**9 + 7))
else:
    print(b % (10**9 + 7))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
P=[]
Z=[]
N=[]
for i in range(n):
  if a[i]>0:
    P.append(a[i])
  elif a[i]==0:
    Z.append(a[i])
  else:
    N.append(-a[i])
P.sort()
P3=[1]
for i in range(len(P)):
  P3.append(P3[-1]*P[i]%mod)
P.reverse()
P2=[1]
for i in range(len(P)):
  P2.append(P2[-1]*P[i]%mod)
N.sort()
N3=[1]
for i in range(len(N)):
  N3.append(N3[-1]*N[i]%mod)
N.reverse()
N2=[1]
for i in range(len(N)):
  N2.append(N2[-1]*N[i]%mod)

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

if k==1:
  print(max(a)%mod)
  exit()

if len(P)+len(N)<k:
  print(0)
  exit()

if len(N)==0:
  print(P2[k]%mod)
  exit()

if len(P)+len(N)==k:
  if len(N)%2==0:
    print(P2[-1]*N2[-1]%mod)
    exit()
  else:
    if len(Z)!=0:
      print(0)
    else:
      print(-P2[-1]*N2[-1]%mod)
    exit()

if k%2==0:
  ans=1
  xp=0
  xn=0
  for i in range(k//2):
    if xp+1<len(P):
      xa=P[xp]*P[xp+1]
    else:
      xa=1
    if xn+1<len(N):
      xb=N[xn]*N[xn+1]
    else:
      xb=1
    if xa<xb:
      xn+=2
      ans*=xb
      ans%=mod
    else:
      xp+=2
      ans*=xa
      ans%=mod
  print(ans%mod)

else:
  ans=1
  xp=0
  xn=0
  ctP=0
  ctN=0
  for i in range(k//2):
    if xp+1<len(P):
      xa=P[xp]*P[xp+1]
    else:
      xa=1
    if xn+1<len(N):
      xb=N[xn]*N[xn+1]
    else:
      xb=1
    if xa<xb:
      xn+=2
      ans*=xb
      ans%=mod
      ctN+=1
    else:
      xp+=2
      ans*=xa
      ans%=mod
      ctP+=1
  if ctP*2+1<=len(P):
    ans*=P[ctP*2]
    ans%=mod
    print(ans%mod)
  else:
    N.reverse()
    P.reverse()
    ans=1
    xp=0
    xn=0
    ctP=0
    ctN=0
    for i in range(k//2):
      if xp+1<len(P):
        xa=P[xp]*P[xp+1]
      else:
        xa=0
      if xn+1<len(N):
        xb=N[xn]*N[xn+1]
      else:
        xb=0
      if xa<xb:
        xn+=2
        ans*=xb
        ans%=mod
        ctN+=1
      else:
        xp+=2
        ans*=xa
        ans%=mod
        ctP+=1
    ans*=N[ctN*2]
    ans%=mod
    if len(Z)!=0:
      print(0)
    else:
      print(-ans%mod)

Submission status: Wrong Answer

Solution code:

from collections import deque



# for #!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase


# # region fastio

# BUFSIZE = 8192


# class FastIO(IOBase):
#     newlines = 0

#     def __init__(self, file):
#         self._fd = file.fileno()
#         self.buffer = BytesIO()
#         self.writable = "x" in file.mode or "r" not in file.mode
#         self.write = self.buffer.write if self.writable else None

#     def read(self):
#         while True:
#             b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
#             if not b:
#                 break
#             ptr = self.buffer.tell()
#             self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
#         self.newlines = 0
#         return self.buffer.read()

#     def readline(self):
#         while self.newlines == 0:
#             b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
#             self.newlines = b.count(b"\n") + (not b)
#             ptr = self.buffer.tell()
#             self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
#         self.newlines -= 1
#         return self.buffer.readline()

#     def flush(self):
#         if self.writable:
#             os.write(self._fd, self.buffer.getvalue())
#             self.buffer.truncate(0), self.buffer.seek(0)


# class IOWrapper(IOBase):
#     def __init__(self, file):
#         self.buffer = FastIO(file)
#         self.flush = self.buffer.flush
#         self.writable = self.buffer.writable
#         self.write = lambda s: self.buffer.write(s.encode("ascii"))
#         self.read = lambda: self.buffer.read().decode("ascii")
#         self.readline = lambda: self.buffer.readline().decode("ascii")


# sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
# input = lambda: sys.stdin.readline().rstrip("\r\n")
from bisect import bisect_left as bl
from math import log2,ceil
from heapq import heappush, heappop
from itertools import permutations
# from copy import deepcopy 
M = 1e9 + 7
def main():
    # for t in range(int(input())):
        # n = int(input())
        # d = dict()
        n,k = [int(j) for j in input().split()]
        l = [int(j) for j in input().split()]
        pos = []
        neg = []
        for i in range(n):
            if l[i]>=0:
                pos.append(l[i])
            else:
                neg.append(l[i])
        pos.sort(reverse=True)
        neg.sort()

        ppos = [i for i in pos]
        nneg = [j for j in neg]
        for i in range(1,len(pos)):
            ppos[i]=(ppos[i-1]*ppos[i])%M
        for i in range(1, len(neg)):
            nneg[i] *= (nneg[i-1]%M)
            # print(nneg)
            nneg[i] = nneg[i]%M
        negp = neg[::-1]
        nnegp = [j for j in negp]
        for i in range(1, len(negp)):
            nnegp[i] *= nnegp[i-1]
            nnegp[i] = nnegp[i]%M
        fans = -1*float('inf')
        if len(neg):
            nneg[0] = nneg[0]%M
            nnegp[0] = nnegp[0]%M
        # print(ppos, nnegp, nneg)
        for x in range(1,k+1):
            y = k-x
            # print(x,y,"ds")
            if x>len(ppos) or y>len(nneg):
                continue 

            tans = 1
            if y>0:
                if(y%2):
                    tans*=nnegp[y-1]
                else:
                    tans*=nneg[y-1]
            tans = tans%M*ppos[x-1]
            if y%2==0:
                fans = max(tans%M, fans)
            else:
                fans = max(tans%M-M, fans)
        if len(nneg)>=k:
            tans = 1
            y = k-1
            # print(nneg, y)
            if(y%2):
                tans*=nneg[y]
            else:
                tans*=nnegp[y]
            # tans = tans*ppos[x-1]
            if y%2==1:
                fans = max(tans%M, fans)
            else:
                fans = max(tans%M-M, fans)
        print(int(fans%M))



            # heappush(h, l[i])

        


        
        




# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7

n, k = [int(_) for _ in input().split()]

a = [int(_) for _ in input().split()]

m = list(filter(lambda x: x < 0, a))
p = list(filter(lambda x: x > 0, a))

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


if len(p)+len(m) < k:
    print(0)
    exit()

if len(p) == 0 and k % 2 == 1:
    ans = 1
    for i in range(k):
        ans = (ans*m[-i-1]) % MOD
    if 0 in a:
        ans *= 0
    print(ans)
    exit()


i, j = 0, 0
if k % 2 == 1:
    d = p.pop(-1)
m.append(0)
m.append(0)
p.append(0)
p.append(0)
ans = 1
for c in range(k//2):
    # print(i, j)
    if m[i]*m[i+1] >= p[j]*p[j+1]:
        ans = (ans*m[i]*m[i+1]) % MOD
        i += 2
    else:
        ans = (ans*p[j]*p[j+1]) % MOD
        j += 2

if k % 2 == 1:
    ans = (ans*max(p[j], d)) % MOD


if ans == MOD:
    ans = 0
print(ans)

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



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:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n,k = m()

a = l()

a.sort()

mina = []

pra = []

for i in range(n):
	if a[i] >= 0:
		pra.append(a[i])
	else:
		mina.append(a[i])

lp = len(pra)

lm = len(mina)
ans = 1
if lp == 0:
	if k % 2 != 0:
		for i in range(0,k,2):
			if i == k-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		for i in range(0,k,2):
			ans *= (mina[i]*mina[i+1]) % mod
			ans %= mod
		print(ans % mod)
elif lp == 1:
	if n == k:
		ans *= pra[0]
		for i in range(0,lp,2):
			if i == lp-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		if k % 2 == 0:
			for i in range(0,k,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
		else:
			ans *= pra[0] 
			for i in range(0,k-1,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
else:
	cp = lp-1
	cm = 0
	count = 0
	#data = []
	
	for _ in range(k):
		if cp != -1 and cm != lm:
			if abs(mina[cm]) < pra[cp]:
				if cp == 0:
					if (k-lp) % 2 == 0:
						count += 1
						#ans *= pra[cp]
						#data.append(pra[cp])
						cp -= 1
					else:
						count += 1
						#ans *= mina[cm]
						#data.append(mina[cm])
						cm += 1

				else:
					count += 1
					#ans *= pra[cp]
					#data.append(pra[cp])
					cp -= 1
			else:
				if cm == lm-1:
					if lm % 2 == 0:
						count += 1
						#ans *= mina[cm]
						#data.append(mina[cm])
						cm += 1
					else:
						count += 1
						#ans *= pra[cp]
						#data.append(pra[cp])
						cp -= 1


				else:
					count += 1
					#ans *= mina[cm]
					#data.append(mina[cm])
					cm += 1
		elif cp != lp:
			#ans *= pra[cp]
			#data.append(pra[cp])
			cp -= 1
			count += 1
		elif cm != lm:
			#ans *= mina[cm]
			#data.append(mina[cm])
			cm += 1
			count += 1

		else:
			break

	#data.sort()
	co = 0

	for i in range(0,cm,2):
		ans *= (mina[i] * mina[i+1]) % mod
		ans %= mod
	for i in range(lp-1,cp,-1):
		ans *= pra[i] % mod
		ans %= mod


		
	print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
    import bisect
    N, K = [int(i) for i in input().split()]
    A = sorted([int(i) for i in input().split()])
    l = bisect.bisect_left(A, 0)
    Aneg = A[:l]
    Apos = A[l:]
    ans = []
    if N == K:
        ans = A
    elif len(Apos) == 0:
        if K % 2 == 0:
            ans = Aneg[:K]
        else:
            ans = Aneg[N - K:]
    elif len(Aneg) == 0:
        ans = Apos[N - K:]
    else:
        if (K - len(Apos)) % 2 == 1:
            ni, pi = len(Aneg) - 1, 0
            cnt = 0
            while K - cnt > 0:
                if K - cnt < 2:
                    if ni >= 0:
                        ans.append(Aneg[ni])
                        cnt += 1
                    else:
                        # TODO:?
                        ans.append(Apos[-1])
                        cnt += 1
                else:
                    if pi < (len(Apos) - 1) and (ni <
                                                 1 or (Apos[pi] * Apos[pi + 1] < Aneg[ni] * Aneg[ni - 1])):
                        ans.append(Apos[pi])
                        ans.append(Apos[pi + 1])
                        pi += 2
                        cnt += 2
                    elif ni > 0:
                        ans.append(Aneg[ni])
                        ans.append(Aneg[ni - 1])
                        ni -= 2
                        cnt += 2
                    else:
                        pass
        else:
            ni, pi = 0, len(Apos) - 1
            cnt = 0
            while K - cnt > 0:
                if K - cnt < 2:
                    if pi >= 0:
                        ans.append(Apos[pi])
                        cnt += 1
                    else:
                        # TODO:?
                        ans.append(Aneg[-1])
                        cnt += 1
                else:
                    if ni < (len(Aneg) - 1) and (pi <
                                                 1 or (Aneg[ni] * Aneg[ni + 1] > Apos[pi] * Apos[pi - 1])):
                        ans.append(Aneg[ni])
                        ans.append(Aneg[ni + 1])
                        ni += 2
                        cnt += 2
                    elif pi > 0:
                        ans.append(Apos[pi])
                        ans.append(Apos[pi - 1])
                        pi -= 2
                        cnt += 2
                    else:
                        pass
            # cnt += 1
            # ni += 1
            # pi -= 1
            # ni < len(Aneg)
            # pi >= 0

    mod = 10**9 + 7
    prt = 1 % mod
    for a in ans:
        prt *= (a % mod)
    print(prt % mod)


resolve()

Submission status: Wrong Answer

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

def mod_inverse(a, p):
    mod = 1
    p_bin = bin(p-2)
    for i in range(len(p_bin) - 1, 1, -1):
        if i == len(p_bin) - 1:
            mul = a
            mul %= p
            mod *= (mul ** int(p_bin[i]))
            mod %= p
        else:
            mul = mul ** 2
            mul %= p
            mod *= (mul ** int(p_bin[i]))
            mod %= p
    return mod

a2 = []
for i in range(n):
    if a[i] == 0:
        a2.append([0, 1])
    else:
        a2.append([abs(a[i]), abs(a[i]) // a[i]])
a2.sort(reverse = True)
ans = 1
count_m = 0
min_p = float("inf")
min_m = float("inf")
for i in range(k):
    ans *= a2[i][0]
    ans %= mod
    if a2[i][1] == -1:
        count_m += 1
        min_m = a2[i][0]
    else:
        min_p = a2[i][0]
if count_m % 2 == 0 or ans == 0:
    print(ans)
else:
    num = k
    while num < n:
        temp = a2[num][1]
        if temp == -1:
            if min_p != float("inf"):
                ans *= mod_inverse(min_p, mod)
                ans %= mod
                ans *= a2[num][0]
                ans %= mod
                print(ans)
                break
            else:
                num += 1
        else:
            if min_m != float("inf"):
                ans *= mod_inverse(min_m, mod)
                ans %= mod
                ans *= a2[num][0]
                ans %= mod
                print(ans)
                break
            else:
                num += 1
    else:
        a2.sort()
        ans = -1
        for i in range(k):
            ans *= a2[i][0]
            ans %= mod
        print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, K = mi()
A = li()

d = defaultdict(int)
mod = 10**9+7
K_ = K

if N == K:
    ans = 1
    for num in A:
        ans *= num
        ans %= mod
    print(ans)
    exit()

for i in range(N):
    d[A[i]] += 1
    if A[i] < 0:
        A[i] *= -1

A = sorted(A, reverse=True)
l = []

for num in A:
    if d[-num] > 0:
        l.append(1)
        d[-num] -= 1
    else:
        l.append(0)
        d[num] -= 1

#print(l)
#print(sum(l[:K]))

if not sum(l[:K])%2:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= mod
    print(ans)

else:
    flag = False
    ans = 1
    for i in range(K, N):
        if not l[i]:
            flag = True
            ans *= A[i]
            ans %= mod
            break
    
    if flag:
        for i in reversed(range(K)):
            if flag and l[i]:
                flag = 0
                continue
            ans *= A[i]
            ans %= mod
        print(ans)
    
    else:
        if K%2:
            for i in range(N-K, N):
                ans *= -A[i]
                ans %= mod
            print(ans)

        else:
            for i in range(N):
                if l[i]:
                    K -= 1
                    ans *= A[i]
                    ans %= mod
                if K == 0:
                    break

            else:
    
                ans = 1
                flag = True
                for i in reversed(range(K_)):
                    if flag and not l[i]:
                        flag = 0
                        continue
                    ans *= A[i]
                    ans %= mod
                ans *= A[K_]
                ans %= mod
                print(ans)
                exit()

            print(ans)