Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

We will choose exactly K of these elements. Find the maximum possible product of the chosen elements.

Then, print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Constraints

1 \leq K \leq N \leq 2\times 10^5

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

Print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

The possible products of the two chosen elements are 2, -3, -4, -6, -8, and 12, so the maximum product is 12.

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

The possible products of the three chosen elements are -24, -12, -8, and -6, so the maximum product is -6.

We print this value modulo (10^9+7), that is, 1000000001.

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

The possible products of the one chosen element are -1 and 1000000000, so the maximum product is 1000000000.

Sample Input 4

10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1

Sample Output 4

999983200

Be sure to print the product modulo (10^9+7).



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Wrong Answer

Solution code:
import sys
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


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]
            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:
        for i in range(N-K, N):
            ans *= -A[i]
            ans %= mod
        print(ans)

Submission status: Wrong Answer

Solution code:

def maxProductSubarrayOfSizeK(A, n, k): 
	A.sort() 
	product = 1
	if (A[n - 1] == 0 and (k & 1)): 
		return 0
	if (A[n - 1] <= 0 and (k & 1)) : 
		for i in range(n - 1, n - k + 1, -1): 
			product *= A[i] 
		return product 
	i = 0
	j = n - 1
	if (k & 1): 
		product *= A[j] 
		j-= 1
		k-=1
	k >>= 1 
	for itr in range( k) : 
		left_product = A[i] * A[i + 1] 
		right_product = A[j] * A[j - 1] 
		if (left_product > right_product) : 
			product *= left_product 
			i += 2
		else : 
			product *= right_product 
			j -= 2
	return product % (10**9 + 7)

n,k = [int(x) for x in input().split()]
l = [int(x) for x in input().split()]
print(maxProductSubarrayOfSizeK(l,n,k))

Submission status: Wrong Answer

Solution code:
import bisect
N ,K = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
mod = 10 ** 9 + 7
# ans = 0
if A.count(0) > (N - K):
  print(0)
  quit()
  
# ans = minus
plus = bisect.bisect_right(A, 0)
minus = bisect.bisect_left(A, 0) 
if N == K:
  ans = 1
  for i in range(N):
    ans *= A[i]
    ans %= mod
  print(ans)
  quit()
  
if minus == N:
  ans = 1
  for i in range(1, K + 1):
    ans *= A[-i]
    ans %= mod
  print(ans)
  quit()
  
ans = 1

count = 0
i = 0
j = -1
while count < K:
  if K - count >= 2:
    fo = (A[i] * A[i + 1]) % mod
    re = (A[j] * A[j - 1]) % mod
    #print(fo, re)
    if fo > re:
      ans *= fo 
      ans %= mod
      i += 2
    else:
      ans *= re
      ans %= mod
      j -= 2
    count += 2  
  else:
    count += 1
    ans *= A[j]
      
  #print(ans)
print(ans % mod)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True, key = lambda x: abs(x))
mod = 10**9+7
nega = 0
posi = 0
zero = 0
for i in range(n):
    if a[i] > 0:
        posi += 1
    elif a[i] == 0:
        zero += 1
    else:
        nega += 1

if n == k:
    ans = 1
    for i in range(n):
        ans *= abs(a[i])
        ans %= mod
    if nega%2 == 1:
        ans *= -1

elif posi == 0:

    if k % 2 == 0:
        ans = 1
        for i in range(k):
            ans *= abs(a[i])
            ans %= mod

    else:
        if a.count(0) > 0:
            ans = 0
        else:
            a.reverse()
            ans = 1
            for i in range(k):
                ans *= abs(a[i])
                ans %= mod

            ans *= -1


else:
    posi = 0
    nega = 0
    zero = 0
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod

    for i in range(k):
        if a[i] > 0:
            posi += 1
        elif a[i] < 0:
            nega += 1
        else:
            zero += 1
    if zero > 0:
        ans = 0

    elif nega % 2 != 0:
        minposi = 0
        minnega = 0
        for i in range(k-1, -1, -1):
            if a[i] > 0:
                if minposi == 0:
                    minposi = a[i]
            else:
                if minnega == 0:
                    minnega = a[i]

        maxposi = 0
        maxnega = 0
        for i in range(k, n):
            if a[i] > 0:
                if maxposi == 0:
                    maxposi = a[i]
            else:
                if maxnega == 0:
                    maxnega = a[i]

        if abs(minposi*maxposi) > abs(minnega*minnega):
            ans *= pow(abs(maxnega), mod-2, mod)
            ans *= minposi
        else:
            ans *= pow(abs(maxposi), mod-2, mod)
            ans *= abs(minnega)

print(ans % mod)

Submission status: Wrong Answer

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

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

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

    ans = 1
    if max(A) < 0 and K % 2:
        x = sorted(A,reverse=True)
        for i in range(K):
            ans = (ans * A[i]) % MOD
        print(ans)
        return


    x = sorted(A, key=lambda x: abs(x), reverse=True)
    m = 0
    for i in range(K):
        ans = (ans * x[i]) % MOD
        if x[i] < 0 :m += 1

    if K == N or m % 2 == 0:
        print(ans)
        return
    if x[K] == 0:
        print(0)
        return
    else:
        for i in range(K-1,-1,-1):
            if x[i] * x[K] < 0:
                ans = (ans * pow(x[i],MOD-2,MOD) * x[K]) % MOD
                print(ans)
                return
        print(ans)
        return



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

A.sort()

mod = int(1e9+7)
AM = []
AP = []
AZC = 0
for a in A:
  if a < 0:
    AM.append(a)
  elif a == 0:
    AZC += 1
  else:
    AP.append(a)

#print(AM)
#print(AP)
#print(AZC)
# zero選ばないとだめならゼロ
if N-K < AZC:
  print(0)
  exit(0)

# minusしか選べないケースってあるの？
# AMしかなくて、Kがodd
# zeroが一つでもあればZERO
if len(AP) == 0 and K%2 == 1:
  if AZC > 0:
    print(0)
  else:
    wk = 1
    for i in range(K):
      wk *= AM[-1-i]
      wk %= mod
    print(wk)
  exit(0)  
   
# plusを狙える
# K odd -> plus max 1
# K even -> ２個いちで選んで行ってMAXを
wk = 1
if K%2 == 1:
  wk *= AP.pop(-1)
  wk %= mod
  
K = K // 2
mi, pi = 0, 0
AP = AP[::-1]
while K>0:
  mwk = AM[mi] * AM[mi + 1] if mi + 1 < len(AM) else 0
  pwk = AP[pi] * AP[pi + 1] if pi + 1 < len(AP) else 0
  if mwk <= pwk:
    wk *= pwk % mod
    pi += 2
  else:
    wk *= mwk % mod
    mi += 2
  #print(wk)
  wk %= mod
  K -= 1
print(wk)

Submission status: Wrong Answer

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

P = []
M = []
for i in A:
  if i < 0:
    M.append(abs(i))
  if i > 0:
    P.append(i)

if len(M) + len(P) < K:
  print(0)
  exit()
elif len(M) + len(P) == K:
  ans = 1
  for i in M:
    ans = ans * i % MOD
  for i in P:
    ans = ans * i % MOD
  if len(M) % 2 == 1:
    ans *= -1
    ans += MOD
  print(ans)
  exit()

M.sort(reverse = True)
P.sort(reverse = True)

if len(P) == 0:
  ans = 1
  if K % 2 == 0:
    for i in range(K):
      ans = ans * M[i] % MOD
  else:
    for i in range(K):
      ans = ans * -M[-1 -i] % MOD
    while ans < 0:
      ans += MOD
  print(ans)
else:
  ans = 1
  pn = 0
  mn = 0
  if K % 2 == 1:
    K -= 1
    ans *= P[0]
    pn = 1
  for i in range(K // 2):
    if pn + 2 > len(P):
      ans = ans * M[mn] * M[mn + 1] % MOD
      mn += 2
    elif mn + 2 > len(M):
      ans = ans * P[pn] * P[pn + 1] % MOD
      pn += 2
    else:
      p = P[pn] * P[pn + 1]
      m = M[mn] * M[mn + 1]
      if p > m:
        ans = ans * p % MOD
        pn += 2
      else:
        ans = ans * m % MOD
        mn += 2
  print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
A.sort(key=lambda x:-abs(x))
mod=10**9+7

"""
pl=[]
mi=[]
ze=0
for num in A:
    if num>0:
        pl.append(num)
        break
    elif num<0:
        mi.append(num)
        break
    else:
        ze+=1

pl.sort()
mi.sort()

ans=0
if len(pl)+len(mi)<k:
    ans=0
    print(ans)

tab=[]
"""

ans=1
flg=1
flgcnt=0
save=1
for i in range(k-1):
    now=A[i]
    if now <0:
        flg*=-1
        flgcnt+=1
    ans=ans*abs(now)%mod
    if i==k-3:
        save=ans

#print(ans,flg)
for i in range(k-1,n):
    now=A[i]
    if now >=0:
        lasflg=1
    else:
        lasflg=-1
    if flg*lasflg==1:
        print(ans*abs(now)%mod)
        break
else:
    if flgcnt==k-1 and k>=2 and max(A)>0:
        ans=save
        two=2
        for i in range(k-2,n):
            now=A[i]
            if now>=0:
                two-=1
                ans=ans*abs(now)%mod
            if two==0:
                print(ans)
                break
    else:
        ans=1
        for i in range(k):
            ans=ans*A[n-1-i]%mod
        print(ans)

Submission status: Wrong Answer

Solution code:
n,k = list(map(int, input().strip().split()))
A = list(map(int, input().strip().split()))
x=1
B=[0]*n
for i in range(n):
    B[i]=abs(A[i])
B.sort()
C=[0]*n
for i in range(n):
    C[i]=B[n-1-i]
for i in range(k):
    x*=C[i]
print(x)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
mod=10**9+7
P=1
B=[]
C=False
for i in range(N):
  if A[i]:
    B.append(A[i])
  else:
    C=True
if len(B)<K:
  print(0)
  exit()
B.sort(reverse=True,key=lambda x:abs(x))
Y=0
for i in range(K):
  if B[i]<0:
    Y+=1
  P=P*B[i]%mod
if Y&1==0:
  print(P)
  exit()
if Y==K:
  B.sort()
  if B[-1]<0:
    if C:
      print(0)
      exit()
    P=1
    for i in range(K):
      P=P*B[-(i+1)]%mod
    print(P)
    exit()
  P=P*pow(B[0],mod-2,mod)*B[-1]%mod
  print(P)
  exit()
Y,Z=0,0
for i in range(K,len(B)):
  if B[i]<0:
    Y=B[i]
    break
for i in range(K,len(B)):
  if B[i]>0:
    Z=B[i]
    break
if Y==0:
  for i in range(K-1,-1,-1):
    if B[i]<0:
      P=P*pow(B[i],mod-2,mod)
      break
  print(P*Z%mod)
elif Z==0:
  for i in range(K-1,-1,-1):
    if B[i]>0:
      P=P*pow(B[i],mod-2,mod)
      break
  print(P*Y%mod)
if Y==0 or Z==0:
  exit()
V,W=0,0
for i in range(K-1,-1,-1):
  if B[i]<0:
    V=B[i]
    break
for i in range(K-1,-1,-1):
  if B[i]>0:
    W=B[i]
    break
if -Y/V>-Z/W:
  print(P*Y*pow(V,mod-2,mod)%mod)
else:
  print(P*Z*pow(W,mod-2,mod)%mod)

Submission status: Wrong Answer

Solution code:
mod = 10**9+7
n, k = map(int, input().split())
arr = [int(i) for i in input().split()]

arr.sort()

prod1, prod2 = 1, 1 
for i in range(k):
	prod1 *= arr[i];
	prod2 *= arr[n-1-i]

if (prod1 > prod2):
	print(prod1%mod)
else:
	print(prod2%mod)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate
import operator as op
mod = int(1e9+7)
n,k = map(int,input().split())
L=list(map(int,input().split()))
L.sort()

l1 = L[:k]
l2 = L[n-k:]
pr1 = 1
pr2 = 1
count1=0
count2=0 
for i in range(k):
    pr1 = abs(pr1* l1[i])%mod
    if l1[i]<0:
        count1+=1
        pr1 = ((-1)**count1)*pr1
    pr2 = abs(pr2* l2[i])%mod
    if l2[i]<0:
        count2+=1
        pr2 = ((-1)**count2)*pr2

val = max(pr1,pr2)
print(val%mod)

Submission status: Wrong Answer

Solution code:
def main():
    M=10**9+7
    n,k,*a=map(int,open(0).read().split())
    x,y=[],[]
    for i in a:
        if i>0:x.append(i)
        if i<0:y.append(i)
    x.sort(reverse=1)
    y.sort()
    if len(x)+len(y)<k or len(x)<k and (k-len(x))%2 and len(x)+len(y)<n:
        print(0)
        exit()
    if len(x)<k and (k-len(x))%2:
        c=1
        for i in x+y[::-1][:k-len(x)]:
            c=c*i%M
        print(c)
        exit()
    x=x[:k]
    m=len(y)
    i=len(x)
    j=0
    if i<k:
        j=k-i
        x+=y[:j]
        j+=1
    while i>1 and j+1<m and x[i-1]*x[i-2]<y[j]*y[j+1]:
        x[i-1],x[i-2]=y[j],y[j+1]
        i-=2
        j+=2
    c=1
    for i in x:
        c=c*i%M
    print(c)
main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    A=LI()
    Lp=[]
    Lm=[]
    Lz=[]
    for i in range(N):
        if A[i]==0:
            Lz.append(0)
        elif A[i]>0:
            Lp.append(A[i])
        else:
            Lm.append(A[i])
            
    Lp.sort(reverse=True)
    Lm.sort()
    
    Np=len(Lp)
    Nm=len(Lm)
    
    if len(Lp)+len(Lm)<K:#どうしても0が入る
        print(0)
        exit()
    if K==1:
        print(max(A))
        exit()
    if max(A)<0:#全部負
        if K%2==0:
            A.sort()
        else:
            A.sort(reverse=True)
        ans=1
        for i in range(K):
            ans=(ans*A[i])%mod
        print(ans)
        exit()
    
    Lp.append(0)
    Lp.append(0)
    Lp.append(0)
    Lm.append(0)
    Lm.append(0)
    nowp=0
    nowm=0
    
    ans=1
    if K%2==0:
        for i in range(K//2):
            a=Lp[nowp]*Lp[nowp+1]
            b=Lm[nowm]*Lm[nowm+1]
            if a>=b:
                ans=(ans*a)%mod
                nowp+=2
            else:
                ans=(ans*b)%mod
                nowm+=2
    else:
        ans=Lp[0]
        nowp+=1
        for i in range(K//2):
            a=Lp[nowp]*Lp[nowp+1]
            b=Lm[nowm]*Lm[nowm+1]
            if a>=b:
                ans=(ans*a)%mod
                nowp+=2
            else:
                ans=(ans*b)%mod
                nowm+=2
    print(ans)
        
            

        
 
    
            
            

main()

Submission status: Wrong Answer

Solution code:
import bisect
N ,K = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
mod = 10 ** 9 + 7
# ans = 0
if A.count(0) > (N - K):
  print(0)
  quit()
  
# ans = minus
plus = bisect.bisect_right(A, 0)
minus = bisect.bisect_left(A, 0) 
if N == K:
  ans = 1
  for i in range(N):
    ans *= A[i]
    ans %= mod
  print(ans)
  quit()
  
if minus == N:
  ans = 1
  for i in range(1, K + 1):
    ans *= A[-i]
    ans %= mod
  print(ans)
  quit()
  
ans = 1

count = 0
i = 0
j = -1
while count < K:
  if K - count >= 2:
    fo = (A[i] * A[i + 1]) % mod
    re = (A[j] * A[j - 1]) % mod
    #print(fo, re)
    if fo > re:
      ans *= fo 
      ans %= mod
      i += 2
    else:
      ans *= re
      ans %= re
      j -= 2
    count += 2  
  else:
    count += 1
    ans *= A[j]
      
  #print(ans)
print(ans % mod)

Submission status: Wrong Answer

Solution code:
mod=1000000007
def maxp(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=(product%mod* A[i]%mod)%mod 
        return product%mod 
  
    # 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%mod* A[j]%mod)%mod 
        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]%mod * A[i + 1]%mod)%mod 
  
        # product from right pointers 
        right_product = (A[j]%mod* A[j - 1]%mod)%mod 
  
        # Taking the max product from two  
        # choices. Correspondingly changing 
        # the pointer's position 
        if (left_product > right_product) : 
            product =(product%mod* left_product%mod)%mod
            i += 2
          
        else : 
            product =(product%mod*right_product%mod)%mod
            j -= 2
  
    # Finally return product 
    return product%mod
  
# Driver Code 
if __name__ == "__main__": 
      
    n, k = [int(x) for x in input().split()]
    a = list(map(int,input().strip().split()))[:n]
    print(maxp(a,n,k)%mod)

Submission status: Wrong Answer

Solution code:
# FROM GEEKSFORGEEKS

# Required function 
def maxProductSubarrayOfSizeK(A, n, k):
	A.sort()
	product = 1
	if (A[n - 1] == 0 and (k & 1)): 
		return 0
	if (A[n - 1] <= 0 and (k & 1)) : 
		for i in range(n - 1, n - k + 1, -1): 
			product *= A[i] 
		return product%1000000007 
	i = 0
	j = n - 1
	if (k & 1): 
		product *= A[j] 
		j-= 1
		k-=1
	k >>= 1
	for itr in range( k) :
		left_product = A[i] * A[i + 1]
		right_product = A[j] * A[j - 1]
		if (left_product > right_product) : 
			product *= left_product 
			i += 2
		else : 
			product *= right_product 
			j -= 2
	return product%1000000007
if __name__ == "__main__": 
	n,k=map(int,input().split())
	A=list(map(int,input().split()))
	print(maxProductSubarrayOfSizeK(A, n, k)%1000000007)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from scipy.sparse.csgraph import floyd_warshall
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush, heapify
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    a.sort()
    ans = 1
    cnt = 0
    l = 0
    r = n-1
    x = bisect.bisect_left(a,0)
    y = bisect.bisect_right(a,0)
    flag = 0
    if k == n:
        if x%2 == 0:
            flag = 1
    elif k == n-1:
        if x == n:
            if k%2 == 0:
                flag = 1
        else:
            if not(x == n and x%2 == 0):
                flag = 1
    else:
        flag = 1
    if flag:
        while True:
            if a[l+1] >= 0:
                ans *= a[r]
                ans %= mod
                cnt += 1
                r -= 1
            else:
                if a[l]*a[l+1] >= a[r]*a[r-1] and cnt < k-1:
                    ans *= a[l]
                    ans *= a[l+1]
                    ans %= mod
                    cnt += 2
                    l += 2
                else:
                    ans *= a[r]
                    ans %= mod
                    cnt += 1
                    r -= 1
            if cnt == k:
                break
        print(ans)
    else:
        for i in range(n):
            a[i] = abs(a[i])
        a.sort()
        for i in range(k):
            ans *= a[i]
            ans %= mod
        ans *= -1
        ans %= mod
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

MOD = 10**9 + 7


def read_int():
    line = sys.stdin.readline().rstrip('\n')
    return int(line)

def read_int_list():
    line = sys.stdin.readline().rstrip('\n')
    return [int(e) for e in line.split(' ')]

def sign(n):
    if n > 0:
        return 1
    if n < 0:
        return -1
    return 0

def abs_prod(A, K, add, remove):
    prod = 1
    for i in range(K):
        if i == remove:
            continue
        prod *= abs(A[i])
        prod %= MOD
    if add != None:
        prod *= abs(A[add])
        prod %= MOD
    return prod


N, K = read_int_list()
A = read_int_list()

A.sort(key=lambda i: -abs(i))

last_plus = None
last_minus = None
sig = 1
for i in range(K):
    sig *= sign(A[i])
    if A[i] > 0:
        last_plus = i
    if A[i] < 0:
        last_minus = i
remove = None
add = None
if sig < 0:
    for i in range(K, N):
        if A[i] > 0 and last_minus != None:
            remove = last_minus
            add = i
            sig = 1
            break
        elif A[i] < 0 and last_plus != None:
            remove = last_plus
            add = i
            sig = 1
            break
        elif A[i] == 0:
            sig = 0
            break

if sig == 0:
    print(0)

ap = abs_prod(A, K, add, remove)

if sig > 0:
    print(ap)
else:
    print((MOD - ap) % MOD)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import heapq
import sys

MOD = 10**9+7

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

a_plus=[]
a_minus=[]
a_zero = 0

for ai in a:
    if ai>0:
        heapq.heappush(a_plus, -ai)
    elif ai<0:
        heapq.heappush(a_minus, ai)
    else:
        a_zero += 1
        
if a_zero > n-k:
    print(0)
    sys.exit()
elif len(a_minus) == n and k%2 == 1:
    for _ in range(n-k):
        heapq.heappop(a_minus)
    ans = 1
    for _ in range(k):
        ans *= - heapq.heappop(a_minus)
        ans %= MOD
    print(-ans % MOD)
    sys.exit()


ans = 1
last_plus = MOD
last_minus = MOD
sign = 1

for _ in range(k):
    if len(a_minus)==0 or (len(a_plus)>0 and a_plus[0] < a_minus[0]):
        last_plus = -heapq.heappop(a_plus)
        ans *= last_plus
    else:
        last_minus = -heapq.heappop(a_minus)
        ans *= last_minus
        sign *= -1
    
    ans %= MOD
    

if sign>0:
    print(ans)
else:
    heapq.heappush(a_plus,0)
    heapq.heappush(a_minus,0)
    
    if -a_plus[0] / last_minus > -a_minus[0] / last_plus:
        ans = ans * (-a_plus[0]) % MOD * pow(last_minus,MOD-2,MOD) % MOD
    else:
        ans = ans * (-a_minus[0]) % MOD * pow(last_plus,MOD-2,MOD) % MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    if n == k:
        ans = a[0]
        for i in a[1:]:
            ans *= i
            ans %= mod
        print(ans)
        return
    mi = []
    ma = []
    a.sort()
    for ai in a:
        if ai <= 0:
            heappush(mi, ai)
        else:
            heappush(ma, -ai)
    if not ma:
        ans = 1
        if k & 1:
            for i in range(k):
                ans *= a[-i - 1]
                ans %= mod
        else:
            for i in range(k):
                ans *= a[i]
                ans %= mod
        print(ans)
        return
    if len(mi) >= k:
        ans = 1
        A = []
        if k & 1:
            k -= 1
            ans *= -heappop(ma)
        for _ in range(k):
            x = heappop(mi)
            ans *= x
            ans %= mod
            heappush(A, -x)
        while len(ma) >= 2 and len(A) >= 2:
            g1 = -heappop(ma)
            g2 = -heappop(ma)
            h1 = -heappop(A)
            h2 = -heappop(A)
            if g1 * g2 < h1 * h2:
                print(ans)
                return
            ans *= pow(h1 * h2, mod - 2, mod)
            ans %= mod
            ans *= g1 * g2
            ans %= mod
        print(ans)
    else:
        ans = 1
        L = len(mi)
        A = []
        X = k - L
        if len(mi) & 1:
            L -= 1
            X += 1
        for i in range(L):
            x = heappop(mi)
            ans *= x
            ans %= mod
            heappush(A, -x)
        for i in range(X):
            x = -heappop(ma)
            ans *= x
            ans %= mod
        while len(ma) >= 2 and len(A) >= 2:
            g1 = -heappop(ma)
            g2 = -heappop(ma)
            h1 = -heappop(A)
            h2 = -heappop(A)
            if g1 * g2 < h1 * h2:
                print(ans)
                return
            ans *= pow(h1 * h2, mod - 2, mod)
            ans %= mod
            ans *= g1 * g2
            ans %= mod
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
# https://qiita.com/sotetsuk/items/a4b810923beffe331f1a
import functools
import operator
pro = functools.partial(functools.reduce, operator.mul)

MOD = 10**9 + 7

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

a.sort(key=lambda x: abs(x), reverse=True)

# if sum(int(e < 0) for e in a[:k]) % 2 == 0:
print(max(pro(a[:k]), pro(a[len(a) - k:])) % MOD)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

mod = 10**9+7

cp = 0
cm = 0
for i in range(N):
    n = 1
    if A[i] < 0:
        n = -1
    elif A[i] == 0:
        n = 0
    A[i] = (abs(A[i]), n)
    if n > 0:
        cp += 1
    elif n < 0:
        cm += 1

if K > cp+cm:
    ans = 0
elif (cp == 0 and K%2 == 1) or (K == N and cm % 2 == 1):
    if N > cp+cm:
        ans = 0
    else:
        A.sort()
        ans = 1
        for i in range(K):
            ans *= A[i][0]
            ans %= mod
        ans *= -1
        ans %= mod
else:
    A.sort(reverse=True)
    cnt = 0
    ans = 1
    for i in range(K):
        ans *= A[i][0]
        ans %= mod
        if A[i][1] < 0:
            cnt += 1

    if cnt % 2 == 1:
        a1 = 1
        f11 = False
        f12 = False
        for i in range(K, N):
            if A[i][1] < 0:
                a1 *= A[i][0]
                f11 = True
                break
        for i in range(K-1, -1, -1):
            if A[i][1] > 0:
                a1 /= A[i][0]
                f12 = True
                break
        a2 = 1
        f21 = False
        f22 = False
        for i in range(K, N):
            if A[i][1] > 0:
                a2 *= A[i][0]
                f21 = True
                break
        for i in range(K-1, -1, -1):
            if A[i][1] < 0:
                a2 /= A[i][0]
                f22 = True
                break

        if a1 > a2 and f11 and f12 and f21 and f22:
            for i in range(K, N):
                if A[i][1] < 0:
                    ans *= A[i][0]
                    ans %= mod
                    break
            for i in range(K-1, -1, -1):
                if A[i][1] > 0:
                    ans *= pow(A[i][0], mod-2, mod)
                    ans %= mod
                    break
        elif f11 and f12 and f21 and f22:
            for i in range(K, N):
                if A[i][1] > 0:
                    ans *= A[i][0]
                    ans %= mod
                    break
            for i in range(K-1, -1, -1):
                if A[i][1] < 0:
                    ans *= pow(A[i][0], mod-2, mod)
                    ans %= mod
                    break
        elif f11 and f12:
            for i in range(K, N):
                if A[i][1] < 0:
                    ans *= A[i][0]
                    ans %= mod
                    break
            for i in range(K-1, -1, -1):
                if A[i][1] > 0:
                    ans *= pow(A[i][0], mod-2, mod)
                    ans %= mod
                    break
        else:
            for i in range(K, N):
                if A[i][1] > 0:
                    ans *= A[i][0]
                    ans %= mod
                    break
            for i in range(K-1, -1, -1):
                if A[i][1] < 0:
                    ans *= pow(A[i][0], mod-2, mod)
                    ans %= mod
                    break

print(ans)