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:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy

MAX = 10 ** 9 + 7

def prod_mod(la, mod):
  x = 1
  for a in la:
    x *= a
    x %= mod
  return x

def main():
  n, k = map(int, input().strip().split())
  la = numpy.array(list(map(int, input().strip().split())))
  la = la[numpy.argsort(numpy.abs(la))][::-1]
  if n == k:
    print(prod_mod(la, MAX))
  else:
    if k % 2 == 1 and (la >= 0).sum() == 0:
      print(prod_mod(la[-k:], MAX))
    else:
      lap = [a for a in la if a >= 0] + [0, 0]
      lam = [a for a in la if a < 0] + [0, 0]
      cp, cm = 0, 0
      ans = 1
      if k % 2 == 1:
        ans *= lap[cp]
        cp += 1
      while k - (cp + cm + 2) >= 0:
        if numpy.prod(lap[cp:cp+2]) > numpy.prod(lam[cm:cm+2]):
          ans *= numpy.prod(lap[cp:cp+2])
          cp += 2
        else:
          ans *= numpy.prod(lam[cm:cm+2])
          cm += 2
        ans %= MAX
      print(ans % MAX)
          

if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy

MAX = 10 ** 9 + 7

def prod_mod(la, mod):
  x = 1
  for a in la:
    x *= a
    x %= mod
  return x

def main():
  n, k = map(int, input().strip().split())
  la = numpy.array(list(map(int, input().strip().split())))
  la.sort()
  if n == k:
    print(prod_mod(la, MAX))
  else:
    if k % 2 == 1 and (la >= 0).sum() == 0:
      print(prod_mod(la[-k:], MAX))
    else:
      il, ir = 0, n-1
      cnt = 0
      l = []
      while k - (cnt + 2) >= 0:
        if la[il] * la[il+1] > la[ir-1] * la[ir]:
          l.extend([la[il], la[il+1]])
          il += 2
        else:
          l.extend([la[ir-1], la[ir]])
          ir -= 2
        cnt += 2
      if k % 2 == 1:
        l.append(la[ir])
      print(prod_mod(l, MAX))
      

if __name__=='__main__':
  main()

Submission status: Wrong Answer

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

if lst[-1] < 0 or k % 2 == 1:
	ans1 = 1
	for i in range(k):
		ans1 *= lst[- i - 1] % mod
	print(ans1 % mod)
	exit()

ans2 = 1
l = 0
r = n - 1
if k % 2 == 1:
	ans2 = lst(k) 
	r -= 1
	
for i in range(k // 2):
	left = lst[l] * lst[l + 1]
	right = lst[r - 1] * lst[r]
	if left > right:
		ans2 *= left % mod 
		ans2 %= mod 
		l += 2
	else:
		ans2 *= right % mod
		ans2 %= mod
		r -= 2
	
print(ans2 % mod)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
M = []
m = []
for a in A:
    if a < 0:
        m.append(abs(a))
    else:
        M.append(a)

i = 0
j = 0
tmp = 1
P = 10**9 + 7

if (K%2 == 0 and (len(m)//2*2 + len(M)//2*2) >= K) or (K%2 == 1 and (len(M) + len(m)//2*2) >= K and len(M) > 0):
    m.sort(reverse=True)
    M.sort(reverse=True)
    while K > 0:
        if K >= 2:
            if j+2 <= len(M) and i+2 <= len(m):
                if m[i]*m[i+1] < M[j]*M[j+1]:
                    tmp *= M[j]*M[j+1]
                    j += 2
                else:
                    tmp *= m[i]*m[i+1]
                    i += 2
            elif j+2 <= len(M):
                tmp *= M[j]*M[j+1]
                j += 2
            elif i+2 <= len(m):
                tmp *= m[i]*m[i+1]
                i += 2
            else:
                tmp *= m[i]*M[j]
            K -= 2
        else:
            tmp *= M[j]
            K -= 1
        tmp %= P
else:
    m.sort()
    M.sort()
    for _ in range(K):
        if j+1 <= len(M) and i+1 <= len(m):
            if M[j] < m[i]:
                tmp *= M[j]
                j += 1
            else:
                tmp *= m[i]
                i += 1
        elif j+1 <= len(M):
            tmp *= M[j]
            j += 1
        else:
            tmp *= m[i]
            i += 1
        tmp %= P
    tmp *= -1
    tmp %= P
        
print(tmp)

Submission status: Wrong Answer

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

if lst[-1] < 0 or k % 2 == 1:
	ans1 = 1
	for i in range(k):
		ans1 *= lst[- i - 1]
	print(ans1 % mod)
	exit()

else:
	ans2 = 1
	l = 0
	r = n - 1
	if k % 2 == 1:
		ans2 = lst(k) 
		r -= 1
	
	for i in range(k // 2):
		left = lst[l] * lst[l + 1]
		right = lst[r - 1] * lst[r]
		if left > right:
			ans2 *= left % mod 
			ans2 = ans2 % mod 
			l += 2
		else:
			ans2 *= right % mod
			ans2 = ans2 % mod
			r -= 2
	
	print(ans2)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
lst = sorted(list(map(int, input().split())))
#print(lst)

if lst[-1] < 0 or k % 2 == 1:
	ans1 = 1
	for i in range(k):
		ans1 *= lst[- i - 1]
	print(ans1 % (10 ** 9 + 7))
	exit()

else:
	ans2 = 1
	l = 0
	r = n - 1
	if k % 2 == 1:
		ans2 *= lst(k)
		r -= 1
	
	for i in range(k // 2):
		left = lst[l] * lst[l + 1]
		right = lst[r - 1] * lst[r]
		if left > right:
			ans2 *= left
			l += 2
		else:
			ans2 *= right
			r -= 2
	
	print(ans2 %(10 ** 9 + 7))

Submission status: Wrong Answer

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

p=[]
n=[]
for i in range(N):
    if A[i]>0:
        p.append(A[i])
    elif A[i]<0:
        n.append(A[i])

p.sort(reverse=True)
n.sort()
num_of_0=N-(len(p)+len(n))
M=10**9+7

if len(p)+len(n)<K:
    ans=0
elif len(n)==N:
    ans = 1
    for i in range(K):
        ans = (ans*n.pop(-1))%M
elif len(p)+len(n)==K and len(n)%2==1:
    ans=0
elif len(p)+len(n)==K and len(n)%2==0:
    ans=1
    for i in range(len(p)):
        ans = (ans*p.pop(0))%M
    for i in range(len(n)):
        ans = (ans*n.pop(0))%M
else:
    ans=1
    num_of_n=0
    for i in range(K):
        if i==K-1:
            if num_of_n%2==1:
                ans = (ans*n.pop(0))%M
            else:
                ans = (ans*p.pop(0))%M
        elif len(p)<2:
            ans = (ans*n.pop(0))%M
            num_of_n =+ 1
        elif len(n)<2:
            ans = (ans*p.pop(0))%M
        else:
            if p[0]<abs(n[0]):
                ans = (ans*n.pop(0))%M
                num_of_n =+ 1
            else:
                ans = (ans*p.pop(0))%M
print(ans)

Submission status: Wrong Answer

Solution code:
# AFTER EDITORIAL, WIP

def solve(ls, k, debug=0):
    modulo = 10 ** 9 + 7
    n = len(ls)
    n_neg = 0
    for i in range(n):
        n_neg += ls[i] < 0
    n_pos = n - n_neg

    # Sort by abs
    ls_abs = [abs(x) for x in ls]
    ls_abs_argsort = sorted(list(range(n)), key=lambda i: -ls_abs[i])

    # Check if positive result is impossible
    if n_neg >= k:
        positive = (k % 2 == 0) or (n_pos > 0)
    else:
        positive = (n_neg % 2 == 0) or (n > k)

    # If positive is impossible, pick "abs" small ones
    if not positive:
        p = 1
        for i in range(k):
            x = ls[ls_abs_argsort[-1 - i]]
            p *= x
            p %= modulo
        return p

    #
    # If positive is possible, ...
    #
    # PROP.
    #   At most one swap is needed for making product non-negative.
    #   PROOF. TODO
    #

    # Check sign when we pick "abs" large ones
    s = 1
    for i in range(k):
        x = ls[ls_abs_argsort[i]]
        s *= -1 if x < 0 else 1

    # If non-negative, we take as it is
    if s > 0:
        p = 1
        for i in range(k):
            x = ls[ls_abs_argsort[i]]
            p *= x
            p %= modulo
        return p

    # If negative, ...
    #   1. replace small negative with large positive, or
    #   2. replace small positive with large negative

    # Check if "1" is possible
    swap_pos = None
    for i in range(k, n):
        if ls[ls_abs_argsort[i]] >= 0:
            swap_pos = i
            break

    swap_neg = None
    for i in range(k)[::-1]:
        if ls[ls_abs_argsort[i]] < 0:
            swap_neg = i
            break

    # Go with "1"
    if swap_pos is not None and swap_neg is not None:
        p = 1
        p *= ls[ls_abs_argsort[swap_pos]]
        p %= modulo
        for i in range(k):
            if i == swap_neg:
                continue
            x = ls[ls_abs_argsort[i]]
            p *= x
            p %= modulo
        return p

    # Go with "2"
    swap_pos = None
    for i in range(k)[::-1]:
        if ls[ls_abs_argsort[i]] >= 0:
            swap_pos = i
            break

    swap_neg = None
    for i in range(k, n):
        if ls[ls_abs_argsort[i]] < 0:
            swap_neg = i
            break

    p = 1
    p *= ls[ls_abs_argsort[swap_neg]]
    p %= modulo
    for i in range(k):
        if i == swap_pos:
            continue
        x = ls[ls_abs_argsort[i]]
        p *= x
        p %= modulo
    return p


def main(istr, ostr):
    n, k = list(map(int, istr.readline().strip().split()))
    ls = list(map(int, istr.readline().strip().split()))
    result = solve(ls, k)
    print(result, file=ostr)


if __name__ == "__main__":
    import sys

    main(sys.stdin, sys.stdout)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a_sort_abs = sorted(a, key=abs, reverse=True)
a_sort_abs_1 = a_sort_abs[0:k]
a_sort_abs_2 = a_sort_abs[k:n]
a_sort_abs_1_negative = [a_sort_abs_1[i] for i in range(k) if a_sort_abs_1[i] < 0]
a_sort_abs_1_positive = [a_sort_abs_1[i] for i in range(k) if a_sort_abs_1[i] >= 0]
a_sort_abs_2_negative = [a_sort_abs_2[i] for i in range(n-k) if a_sort_abs_2[i] < 0]
a_sort_abs_2_positive = [a_sort_abs_2[i] for i in range(n-k) if a_sort_abs_2[i] >= 0]
a_sort_abs_1_abs = [abs(a_sort_abs_1[i]) for i in range(k)]
mod = 10 ** 9 + 7


def compare():
    if (a_sort_abs_2_negative and a_sort_abs_1_positive) and a_sort_abs_2_positive:
        return max(abs(max(a_sort_abs_2_positive) / max(a_sort_abs_1_negative)),
                   abs(min(a_sort_abs_2_negative) / min(a_sort_abs_1_positive)))
    if (a_sort_abs_2_negative and a_sort_abs_1_positive) == False and a_sort_abs_2_positive:
        return abs(max(a_sort_abs_2_positive) / max(a_sort_abs_1_negative))
    if (a_sort_abs_2_negative and a_sort_abs_1_positive) and a_sort_abs_2_positive == False:
        return abs(min(a_sort_abs_2_negative) / min(a_sort_abs_1_positive))
    else:
        return 1


if len(a_sort_abs_1_negative) + len(a_sort_abs_2_negative) == n and k % 2 == 1:
    ans = 1
    aaa = sorted([-a[i] for i in range(n)])
    for i in range(k):
        ans *= aaa[i]
        ans %= mod
    ans *= -1
    ans %= mod
    print(ans)
else:
    ans = 1
    for i in range(k):
        ans *= a_sort_abs_1_abs[i]
        ans %= mod

    if len(a_sort_abs_1_negative) % 2 == 0:
        print(ans)

    else:
        compare = int(compare())
        ans *= compare
        print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
m=10**9+7
l=1
c=0
if n==k or (a[-1]<0 and k%2==1):
    for i in range(1,k+1):
        l=(l*abs(a[-i]))%m
        if a[-i]<0:
            c+=1
    print((l*(-1)**c)%m)
else:
    a=sorted(a,key=lambda x:abs(x))
    for i in range(1,k):
        l=(l*abs(a[-i]))%m
        if a[-i]<0:
            c+=1
    l=l*(-1)**c
    for i in range(k,n):
        if l*a[i]>0:
            print((l*a[i])%m)
            break

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
m=10**9+7
l=1
c=0
if n==k or (a[-1]<0 and k%2==1):
    for i in range(1,k+1):
        l=(l*abs(a[-i]))%m
        if a[-i]<0:
            c+=1
    print(l*(-1)**c)
else:
    a=sorted(a,key=lambda x:abs(x))
    for i in range(1,k):
        l=(l*abs(a[-i]))%m
        if a[-i]<0:
            c+=1
    l=l*(-1)**c
    for i in range(k,n):
        if l*a[i]>0:
            print(l*a[i])
            break

Submission status: Wrong Answer

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

a.sort()

ans=1

while k>0:
  if k>=2:
    if a[0]*a[1]>a[-1]*a[-2]:
      ans*=a[0]
      ans%=mod
      ans*a[1]
      ans%=mod
      a.pop(0)
      a.pop(0)
      k-=2
    else:
      ans*=a[-1]
      ans%=mod
      a.pop()
      k-=1

  elif k==1:
    ans*=a[-1]
    ans%=mod
    k-=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

if A[-1]<0 and k%2==1:
    now=1
    for i in range(k):
        now*= A[-i-1]
        now%=mod
    print(now) ;exit()

l=0 ; r=n-1
ans=1
if k%2==1:
    ans=A[-1]

for i in range(k//2):
    mi=A[l]*A[l+1]
    pl=A[r]*A[r-1]
    if mi>pl:
        ans*=mi
        l+=2
    else:
        ans*=pl
        r-=2
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=sorted(list(map(int,input().split())) , key=abs , reverse=1)
import bisect as bi
# print(A)
# import numpy as np
# G=np.prod(A[:k])
def seki(A,mod=10**9+7):
    now=1
    for i in A:
        i=abs(i)
        if i>0 : now*=i
        # if i<0 : now*=i
        if i==0 :return 0
        if now>0 : now%=mod
    return now

CH=A[:k] 
NO=A[k:]
# G=seki(A[:k])

mod=10**9+7
# if G>=0 : print(G%mod) ; exit()
if sum([A[i]>=0 for i in range(n)])==0 and k%2==1:
  print((-seki(A[n-k:]))%mod) ;exit()
if n==k and sum([A[i]<0 for i in range(n)])%2==1 :
    print((-seki(A))%mod) ;exit()
if sum([i<0 for i in CH])%2==0 :
    print(seki(CH)%mod) ; exit()
if 0 in CH:
    print(0);exit()
  
# done=0 ; done2=0
# # ch=-73267983297 ; ch2=-9263498381621
# 
# for i in range(k-1,-1,-1):
#     if A[i]<0 and done==0:
#         for j in range(i+1,n):
#             if A[j]>=0: 
#                 # ch=G*A[j]//A[i]
#                 x1=A[j] ; y1=A[i]
#                 done=1
#                 break
#     if A[i]>0 and done2==0:
#         for j in range(i+1,n):
#             if A[j]<=0: 
#                 # ch2=G*A[j]//A[i]
#                 x2=A[j] ; y2=A[i]
#                 done2=1
#                 break
# #     if done==1 and done2==1 : break
# 
# G=seki(A[:k])
# G=-G
# if done and done2 :
#     if x1 * y2 > x2 * y1 :
#         print((G*x1//y1)%mod)
#     else:
#         print((G*x2//y2)%mod)
# elif done==1:
#     print((G*x1//y1)%mod)
# elif done2==1:
#     print((G*x2//y2)%mod)
        

done=0 ; done2=0
muri,muri2=0,0

# x1,x2,y1,y2=0,0,0,0
if sum([i>=0 for i in NO])==0 : #NO全部-
    muri=1
if sum([i>=0 for i in CH])==0 : #CH全部-
    muri2=1
if sum([i<0 for i in NO])==0: #-を入れられない
    muri2=1
    
if muri==0:
    y1= sorted([i for i in CH if i<0])[-1]
    x1= sorted([i for i in NO if i>=0])[-1]
    # done=1
if muri2==0:
    y2= sorted([i for i in CH if i>0])[0]
    x2= sorted([i for i in NO if i<0])[0]
    # done2=1

if muri==0 and muri2==0:
    if x1 * y2 > x2 * y1 :
        print((-seki(CH)*x1//y1)%mod)
    else:
        print((-seki(CH)*x2//y2)%mod)
elif muri:
    print((-seki(CH)*x2//y2)%mod)
else:
    print((-seki(CH)*x1//y1)%mod)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=sorted(list(map(int,input().split())) , key=abs , reverse=1)
import bisect as bi
# print(A)
# import numpy as np
# G=np.prod(A[:k])
def seki(A,mod=10**9+7):
    now=1
    for i in A:
        i=abs(i)
        if i>0 : now*=i
        # if i<0 : now*=i
        if i==0 :return 0
        if now>0 : now%=mod
    return now

CH=A[:k]
NO=A[k:]
# G=seki(A[:k])

mod=10**9+7
# if G>=0 : print(G%mod) ; exit()
if sum([A[i]>0 for i in range(n)])==0 and k%2==1:
  print((-seki(A[n-k:]))%mod) ;exit()
if n==k and len(A[bi.bisect_left(A,-1):])%2==1 :
    print((-seki(A))%mod) ;exit()
if sum([i<0 for i in A[:k]])%2==0 :
    print(seki(A[:k])%mod) ; exit()
if 0 in CH:
    print(0);exit()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=sorted(list(map(int,input().split())) , key=abs , reverse=1)
import bisect as bi
# print(A)
# import numpy as np
# G=np.prod(A[:k])
def seki(A,mod=10**9+7):
    now=1
    for i in A:
        i=abs(i)
        if i>0 : now*=i
        # if i<0 : now*=i
        if i==0 :return 0
        if now>0 : now%=mod
    return now


# G=seki(A[:k])

mod=10**9+7
# if G>=0 : print(G%mod) ; exit()
if sum([A[i]>0 for i in range(n)])==0 and k%2==1:
  print((-seki(A[n-k:]))%mod) ;exit()
if n==k and len(A[bi.bisect_left(A,-1):])%2==1 :
    print((-seki(A))%mod) ;exit()
if sum([i<0 for i in A[:k]])%2==0 :
    print(seki(A[:k])%mod) ; exit()
  
  
done=0 ; done2=0
# ch=-73267983297 ; ch2=-9263498381621

for i in range(k-1,-1,-1):
    if A[i]<0 and done==0:
        for j in range(i+1,n):
            if A[j]>=0: 
                # ch=G*A[j]//A[i]
                x1=A[j] ; y1=A[i]
                done=1
                break
    if A[i]>0 and done2==0:
        for j in range(i+1,n):
            if A[j]<=0: 
                # ch2=G*A[j]//A[i]
                x2=A[j] ; y2=A[i]
                done2=1
                break
    if done==1 and done2==1 : break

G=seki(A[:k])
G=-G
if done and done2 :
    if x1 * y2 > x2 * y1 :
        print((G*x1//y1)%mod)
    else:
        print((G*x2//y2)%mod)
elif done==1:
    print((G*x1//y1)%mod)
elif done2==1:
    print((G*x2//y2)%mod)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=sorted(list(map(int,input().split())) , key=abs , reverse=1)
import bisect as bi
# print(A)
# import numpy as np
# G=np.prod(A[:k])
def seki(A,mod=10**9+7):
    now=1
    for i in A:
        if i>0 : now*=(i %mod)
        if i<0 : now*=i
        if i==0 :return 0
        if now>0 : now%=mod
    return now


G=seki(A[:k])

mod=10**9+7
if G>=0 : print(G%mod) ; exit()
if sum([A[i]>0 for i in range(n)])==0 and k%2==1:
  print(seki(A[n-k:])%mod) ; exit()
if n==k and len(A[bi.bisect_left(A,-1):])%2==1 :
    print(G%mod) ;exit()
  
  
  
done=0 ; done2=0
ch=-73267983297 ; ch2=-9263498381621

for i in range(k-1,-1,-1):
    if A[i]<0 and done==0:
        for j in range(i+1,n):
            if A[j]>=0: 
                # ch=G*A[j]//A[i]
                x1=A[j] ; y1=A[i]
                done=1
                break
    if A[i]>0 and done2==0:
        for j in range(i+1,n):
            if A[j]>=0: 
                # ch2=G*A[j]//A[i]
                x2=A[j] ; y2=A[i]
                done2=1
                break
    if done==1 and done2==1 : break

if done and done2 :
    if x1 * y2 > x2 * y1 :
        print((G*x1//y1)%mod)
    else:
        print((G*x2//y2)%mod)
elif done==1:
    print((G*x1//y1)%mod)
elif done2==1:
    print((G*x2//y2)%mod)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=sorted(list(map(int,input().split())) , key=abs , reverse=1)
# print(A)
# import numpy as np
# G=np.prod(A[:k])
def seki(A,mod=10**9+7):
    now=1
    for i in A:
        if i>0 : now*=(i %mod)
        if i<0 : now*=i
        if i==0 :return 0
        if now>0 : now%=mod
    return now


G=seki(A[:k])

mod=10**9+7
if G>=0 : print(G%mod) ; exit()
if sum([A[i]>0 for i in range(n)])==0 and k%2==1:
  print(seki(A[n-k:])%mod) ; exit()
  
  
  
done=0 ; done2=0
ch=-73267983297 ; ch2=-9263498381621

for i in range(k-1,-1,-1):
    if A[i]<0 and done==0:
        for j in range(i+1,n):
            if A[j]>=0: 
                # ch=G*A[j]//A[i]
                x1=A[j] ; y1=A[i]
                done=1
                break
    if A[i]>0 and done2==0:
        for j in range(i+1,n):
            if A[j]>=0: 
                # ch2=G*A[j]//A[i]
                x2=A[j] ; y2=A[i]
                done2=1
                break
    if done==1 and done2==1 : break

if done and done2 :
    if x1 * y2 > x2 * y1 :
        print((G*x1//y1)%mod)
    else:
        print((G*x2//y2)%mod)
elif done==1:
    print((G*x1//y1)%mod)
elif done2==1:
    print((G*x2//y2)%mod)

Submission status: Wrong Answer

Solution code:
# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

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")

# ------------------- fast io --------------------
from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y


for _ in range(int(input()) if not True else 1):
    n, k = map(int, input().split())
    #a, b = map(int, input().split())
    #c, d = map(int, input().split())
    a = list(map(int, input().split()))
    di = {}
    x = []
    for i in a:
        ab = abs(i)
        x += [ab]
        if ab not in di:
            di[ab] = []
        di[ab] += [1 if i>=0 else -1]

    x = sorted(x, reverse=True)
    signs = []
    for each in x:
        signs += [di[each].pop()]

    cursign = 1
    ans = 1
    firstpos = -1
    firstneg = 0
    nextpos = None
    nextneg = None
    for i in range(k):
        ans = (ans * x[i]) % (10**9+7)
        cursign *= signs[i]
        if signs[i] == 1:
            firstpos = i
        if signs[i] == -1:
            firstneg = i

    if cursign == 1:
        print(ans)
        quit()

    for i in range(k, len(x)):
        if signs[i] == 1 and nextpos is None:
            nextpos = i
        if signs[i] == -1 and nextneg is None:
            nextneg = i
    ansdex = [i for i in range(k)]
    from math import inf
    ans = ans*-1
    #print(ans)
    #print(nextpos)
    ans1, ans2 = -10**18, -10**18
    if nextpos is not None:
        ansd = [i for i in range(k)]
        ans22 = 1
        ansd[firstneg] = nextpos
        for each in ansd:
            ans22 = (ans22 * x[each]) % (10**9+7)
        ans2 = ans22

    if nextneg is not None and firstpos != -1:
        ansd = [i for i in range(k)]
        ans22 = 1
        ansd[firstpos] = nextneg
        for each in ansd:
            ans22 = (ans22 * x[each]) % (10 ** 9 + 7)
        ans1 = ans22
    if ans1 != -10**18 and ans2 != -10**18:
        print(ans1 if x[nextneg]/x[firstpos] >= x[nextpos]/x[firstneg] else ans2)
        quit()
    if ans1 != -10**18 or ans2 != -10**18:
        print(max(ans1, ans2))
        quit()

    a = sorted(a, reverse=True)
    ans=1
    for i in range(k):ans=(ans*(a[i])) % (10**9+7)
    print(ans)

Submission status: Wrong Answer

Solution code:
# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

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")

# ------------------- fast io --------------------
from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y


for _ in range(int(input()) if not True else 1):
    n, k = map(int, input().split())
    #a, b = map(int, input().split())
    #c, d = map(int, input().split())
    a = list(map(int, input().split()))
    di = {}
    x = []
    for i in a:
        ab = abs(i)
        x += [ab]
        if ab not in di:
            di[ab] = []
        di[ab] += [1 if i>=0 else -1]

    x = sorted(x, reverse=True)
    signs = []
    for each in x:
        signs += [di[each].pop()]

    cursign = 1
    ans = 1
    firstpos = -1
    firstneg = 0
    nextpos = None
    nextneg = None
    for i in range(k):
        ans = (ans * x[i]) % (10**9+7)
        cursign *= signs[i]
        if signs[i] == 1:
            firstpos = i
        if signs[i] == -1:
            firstneg = i

    if cursign == 1:
        print(ans)
        quit()

    for i in range(k, len(x)):
        if signs[i] == 1 and nextpos is None:
            nextpos = i
        if signs[i] == -1 and nextneg is None:
            nextneg = i
    ansdex = [i for i in range(k)]
    from math import inf
    ans = ans*-1
    #print(ans)
    #print(nextpos)
    ans1, ans2 = -10**18, -10**18
    if nextpos is not None:
        ansd = [i for i in range(k)]
        ans22 = 1
        ansd[firstneg] = nextpos
        for each in ansd:
            ans22 = (ans22 * x[each]) % (10**9+7)
        ans2 = ans22

    if nextneg is not None and firstpos != -1:
        ansd = [i for i in range(k)]
        ans22 = 1
        ansd[firstpos] = nextneg
        for each in ansd:
            ans22 = (ans22 * x[each]) % (10 ** 9 + 7)
        ans1 = ans22
    if ans1 != -10**18 and ans2 != -10**18:
        print(ans1 if x[nextneg]/x[firstpos] > x[nextpos]/x[firstneg] else ans2)
        quit()
    if ans1 != -10**18 or ans2 != -10**18:
        print(max(ans1, ans2))
        quit()

    a = sorted(a, reverse=True)
    ans=1
    for i in range(k):ans=(ans*(a[i])) % (10**9+7)
    print(ans)