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: Accepted

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

if N==K:
    ans=1
    for i in range(N):
        ans=(ans*A[i])%mod
    print(ans%mod)
else:
    neg=[]
    posi=[]
    zero=0
    for i in range(N):
        if A[i]>0:
            posi.append(A[i])
        elif A[i]<0:
            neg.append(-A[i])
        else:
            zero+=1
    if K>N-zero:
        print(0)
    elif len(neg)==N and K%2==1:
        neg.sort()
        ans=1
        for i in range(K):
            ans=(-ans*neg[i])%mod
        print(ans%mod)
    else:
        A.sort(key=lambda x:-abs(x))
        temp=A[:K]
        rest=A[K:]
        check=0
        for i in range(K):
            if temp[i]<0:
                check+=1
        if check%2==0:
            ans=1
            for i in range(K):
                ans=(ans*abs(temp[i]))%mod
            print(ans%mod)
        else:
            rest.sort()
            temp.sort()
            if rest[0]==0 and rest[-1]==0:
                print(0)
            else:
                if check!=K and check!=0:
                    #neg->posi
                    val1=-1
                    val2=-1
                    for i in range(K-1):
                        if temp[i]<0 and temp[i+1]>0:
                            val1=temp[i]
                            val2=temp[i+1]
                            break
                    #(abs(val1),rest[-1])
                    #posi->neg
                    #(abs(val2),abs(rest[0]))
                    if rest[-1]>=0 and rest[0]<0:
                        if abs(rest[-1])*abs(val2)>abs(rest[0])*abs(val1):
                            ans=1
                            for i in range(K):
                                ans=(ans*abs(temp[i]))%mod
                            ans=(ans*abs(rest[-1]))%mod
                            ans=(ans*pow(abs(val1),mod-2,mod))%mod
                            print(ans%mod)
                        else:
                            ans=1
                            for i in range(K):
                                ans=(ans*abs(temp[i]))%mod
                            ans=(ans*abs(rest[0]))%mod
                            ans=(ans*pow(abs(val2),mod-2,mod))%mod
                            print(ans%mod)
                    elif rest[-1]<0:
                        ans=1
                        for i in range(K):
                            ans=(ans*abs(temp[i]))%mod
                        ans=(ans*abs(rest[0]))%mod
                        ans=(ans*pow(abs(val2),mod-2,mod))%mod
                        print(ans%mod)
                    else:
                        ans=1
                        for i in range(K):
                            ans=(ans*abs(temp[i]))%mod
                        ans=(ans*abs(rest[-1]))%mod
                        ans=(ans*pow(abs(val1),mod-2,mod))%mod
                        print(ans%mod)
                elif check==K:
                    val1=abs(temp[-1])
                    ans=1
                    for i in range(K):
                        ans=(ans*abs(temp[i]))%mod
                    ans=(ans*abs(rest[-1]))%mod
                    ans=(ans*pow(abs(val1),mod-2,mod))%mod
                    print(ans%mod)
                else:
                    val2=abs(temp[0])
                    ans=1
                    for i in range(K):
                        ans=(ans*abs(temp[i]))%mod
                    ans=(ans*abs(rest[0]))%mod
                    ans=(ans*pow(abs(val2),mod-2,mod))%mod
                    print(ans%mod)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))

INF=10**9+7

x=False
y=False
z=False
xl=[]
yl=[]
for i in a:
    if i>0:
        x=True
        xl.append(i)
    elif i<0:
        y=True
        yl.append(i)
    else:
        z=True

if not y:
    a.sort(reverse=True)
    ans=1
    for i in range(k):
        ans=(ans*a[i])%INF

else:
    if not x:
        if z:
            if k%2==0:
                a.sort()
                ans=1
                for i in range(k):
                    ans=(ans*a[i])%INF
            else:
                ans=0
        else:
            if k%2==0:
                a.sort()
                ans=1
                for i in range(k):
                    ans=(ans*a[i])%INF
            else:
                a.sort(reverse=True)
                ans=1
                for i in range(k):
                    ans=(ans*a[i])%INF
    else:
        if z:
            if len(xl)+len(yl)<k:
                ans=0
            elif len(xl)+len(yl)==k:
                ans=1
                for i in xl:
                    ans=(ans*i)%INF
                for i in yl:
                    ans=(ans*i)%INF
                if len(yl)%2==0:
                    pass
                else:
                    ans=0
            else:
                if k%2==0:
                    xyl=[]
                    xl.sort(reverse=True)
                    yl.sort()
                    for i in range(len(xl)//2):
                        xyl.append(xl[i*2]*xl[i*2+1])
                    for i in range(len(yl)//2):
                        xyl.append(yl[i*2]*yl[i*2+1])
                    xyl.sort(reverse=True)
                    ans=1
                    for i in range(k//2):
                        ans=(ans*xyl[i])%INF

                else:
                    xyl = []
                    xl.sort(reverse=True)
                    yl.sort()
                    for i in range((len(xl)-1) // 2):
                        xyl.append(xl[i * 2+1] * xl[i * 2 + 2])
                    for i in range(len(yl) // 2):
                        xyl.append(yl[i * 2] * yl[i * 2 + 1])
                    xyl.sort(reverse=True)
                    ans = xl[0]
                    for i in range((k-1) // 2):
                        ans = (ans * xyl[i]) % INF

        else:
            if k==n:
                ans=1
                for i in a:
                    ans=(ans*i)%INF
            else:
                if k%2==0:
                    xyl=[]
                    xl.sort(reverse=True)
                    yl.sort()
                    for i in range(len(xl)//2):
                        xyl.append(xl[i*2]*xl[i*2+1])
                    for i in range(len(yl)//2):
                        xyl.append(yl[i*2]*yl[i*2+1])
                    xyl.sort(reverse=True)
                    ans=1
                    for i in range(k//2):
                        ans=(ans*xyl[i])%INF

                else:
                    xyl = []
                    xl.sort(reverse=True)
                    yl.sort()
                    for i in range((len(xl)-1) // 2):
                        xyl.append(xl[i * 2+1] * xl[i * 2 + 2])
                    for i in range(len(yl) // 2):
                        xyl.append(yl[i * 2] * yl[i * 2 + 1])
                    xyl.sort(reverse=True)
                    ans = xl[0]
                    for i in range((k-1) // 2):
                        ans = (ans * xyl[i]) % INF


print(ans)

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
mod=10**9+7
A.sort(reverse=True,key=lambda x:abs(x))

if min(A)>0:
  ans=1
  for i in range(k):
    ans=(ans*A[i])%mod
  print(ans)
elif max(A)<0:
  ans=1
  if k%2==0:
    for i in range(k):
      ans=(ans*A[i])%mod
    print(ans)
  else:
    for i in range(k):
      ans=(ans*A[n-1-i])%mod
    print(ans)
elif n==k:
  ans=1
  for i in range(k):
    ans=(ans*A[i])%mod
  print(ans)
elif k==1:
  print(max(A)%mod)

else:
  L1,L2,R1,R2=[],[],[],[]
  ct=0
  for a in A:
    if a==0:
      continue
    if ct<k:
      if a>0:
        L1.append(a)
      elif a<0:
        L2.append(a)
      ct+=1
    else:
      if a>0:
        R1.append(a)
      elif a<0:
        R2.append(a)
  if ct<k:
    print(0)
  else:
    if not L1:
      if k%2==1:
        if not R1:
          print(0)


        else:
          c=R1[0]
          ans=1
          for i in range(len(L2)-1):
            ans=(ans*L2[i])%mod
          ans=(ans*c)%mod
          print(ans)
      else:
        ans=1
        for i in range(len(L2)):
          ans=(ans*L2[i])%mod
        print(ans)
    elif not L2:
      ans=1
      for i in range(len(L1)):
        ans=(ans*L1[i])%mod
      print(ans)
    else:
      if len(L2)%2==0:
        ans=1
        for a in L1:
          ans=(ans*a)%mod
        for a in L2:
          ans=(ans*a)%mod
        print(ans)
      else:
        if not R1:
          if not R2:
            if 0 in A:
              print(0)
            else:
              ans=1
              for a in L1:
                ans=(ans*a)%mod
              for a in L2:
                ans=(ans*a)%mod
              print(ans)
          else:
            d=-R2[0]
            ans=d
            for i in range(len(L1)-1):
              ans=(ans*L1[i])%mod
            for i in range(len(L2)):
              ans=(ans*abs(L2[i]))%mod
            print(ans)
        else:
          c=R1[0]
          a=L1[-1]
          b=L2[-1]
          if R2 and R2[0]*b>a*c:
            ans=R2[0]
            for i in range(len(L1)-1):
              ans=(ans*L1[i])%mod
            for i in range(len(L2)):
              ans=(ans*L2[i])%mod
            print(ans)
          else:
            ans=c
            for i in range(len(L1)):
              ans=(ans*L1[i])%mod
            for i in range(len(L2)-1):
              ans=(ans*L2[i])%mod
            print(ans)

Submission status: Accepted

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

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

m = []
p = []
zero = 0
for i in a:
    if i < 0:
        m.append(-i)
    elif i > 0:
        p.append(i)
    else:
        zero += 1

if n - k < zero:
    print(0)
    exit()

if n - k == zero:
    if len(m) % 2 == 1:
        print(0)
        exit()

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

m.sort(reverse=True)
p.sort(reverse=True)
nm = 0
np = 0
ans = 1
if k % 2 == 1:
    ans *= p[0]
    np += 1
lap = k // 2

while nm < len(m) - 1 and np < len(p) - 1 and lap > 0:
    lap -= 1
    i = m[nm] * m[nm + 1]
    j = p[np] * p[np + 1]
    if i > j:
        ans *= i
        ans %= mod
        nm += 2
    else:
        ans *= j
        ans %= mod
        np += 2

if lap > 0:
    if nm < len(m) - 1:
        for i in range(nm, nm + lap * 2):
            ans *= m[i]
            ans %= mod
    else:
        for i in range(np, np + lap * 2):
            ans *= p[i]
            ans %= mod

print(ans % mod)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

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

    A.sort(key=lambda a: abs(a), reverse=True)
    A_pos = []
    A_neg = []
    for a in A:
        if a >= 0:
            A_pos.append(a)
        else:
            A_neg.append(-a)
    pos_last = 0.1
    neg_last = 0.1
    ans = 1
    cnt = 0
    for a in A[:K]:
        if a >= 0:
            pos_last = a
            ans = (ans * a)%mod
        else:
            neg_last = -a
            ans = (ans * a)%mod
            cnt += 1
    if cnt%2 == 0:
        print(ans)
        exit()

    if pos_last == 0.1:
        pos_add = -1
        for i in range(K, N):
            if A[i] >= 0:
                pos_add = A[i]
                break
        if pos_add == -1:
            ans = 1
            A.reverse()
            for a in A[:K]:
                ans = (ans * a)%mod
            print(ans)
            exit()
        else:
            neg_del = neg_last
            if neg_del == 0.1:
                print(ans)
            else:
                print(((-ans) * pos_add * pow(neg_del, mod-2, mod))%mod)
    else:
        if neg_last == 0.1:
            neg_add = 1
            for i in range(K, N):
                if A[i] < 0:
                    neg_add = -A[i]
                    break
            if neg_add == 1:
                assert False
            else:
                print(((-ans) * neg_add * pow(pos_last, mod - 2, mod)) % mod)
        else:
            pos_add = -1
            for i in range(K, N):
                if A[i] >= 0:
                    pos_add = A[i]
                    break
            neg_add = 1
            for i in range(K, N):
                if A[i] < 0:
                    neg_add = -A[i]
                    break
            if pos_add == -1 and neg_add == 1:
                print(ans)
            elif pos_add == -1:
                print(((-ans) * neg_add * pow(pos_last, mod - 2, mod)) % mod)
            elif neg_add == 1:
                print(((-ans) * pos_add * pow(neg_last, mod - 2, mod)) % mod)
            else:
                if pos_add * pos_last > neg_add * neg_last:
                    print(((-ans) * pos_add * pow(neg_last, mod - 2, mod)) % mod)
                else:
                    print(((-ans) * neg_add * pow(pos_last, mod - 2, mod)) % mod)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=sorted(list(map(int,input().split())),reverse=True)
MOD=10**9+7
if N==K:
    ans=1
    for i in A:
        ans=ans*i%MOD
    print(ans)
    exit()
if K==1:
    print(A[0]%MOD)
    exit()
if K%2==1 and A[0]==0:
    print(0)
    exit()
if K%2==1 and A[0]<0:
    ans=1
    for i in range(K):
        ans=ans*A[i]%MOD
    print(ans)
    exit()
if N-A.count(0) <K:
    print(0)
    exit()
if A[-1]>=0:
    ans=1
    for i in range(K):
        ans=ans*A[i]%MOD
    print(ans)
    exit()
l=0
r=N-1
t=[]
c=0
if K%2==1:
    tk=K-1
    flg=True
else:
    tk=K
    flg=False
while c<tk:
    if A[l]*A[l+1]<=A[r]*A[r-1]:
        t.append(A[r])
        t.append(A[r-1])
        r-=2
        c+=2
    else:
        t.append(A[l])
        t.append(A[l+1])
        l+=2
        c+=2
if flg:
    t.append(A[l])
ans=1
for i in t:
    ans=ans*i%MOD
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
s = []
f = []
z = 0
for ai in a:
  if ai > 0:
    s.append(ai)
  elif ai < 0:
    f.append(-ai)
  else:
    z += 1
p = len(s)
q = len(f)
l = max(0,k-p)
h = min(k,q)
mod = 10**9+7
if l > h:
  print(0)
  exit()
if l%2 == 0 or h-l >= 1:
  if l%2 == 0:
    c = l
  else:
    c = l+1
  s.sort(reverse=True)
  f.sort(reverse=True)
  while c+2 <= h:
    if f[c]*f[c+1] > s[k-c-1]*s[k-c-2]:
      c += 2
    else:
      break
  ans = 1
  for i in range(c):
    ans =(ans*f[i])%mod
  for i in range(k-c):
    ans = (ans*s[i])%mod
  print(ans)
  exit()
if z > 0:
  print(0)
  exit()
m = s + f
m.sort()
ans = 1
for i in range(k):
  ans = (ans*(m[i]))%mod
ans = (-ans)%mod
print(ans)

Submission status: Accepted

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

#n=10000
#k=n//2
#a=[100000000*(-1)**i for i in range(n)]

mod=pow(10,9)+7
a.sort()
if a[-1]<=0:
  if k%2==0:
    ans=1
    for i in range(k):
      ans*=a[i]
      ans%=mod
    print(ans%mod)
  else:
    ans=1
    for i in range(k):
      ans*=a[-1-i]
      ans%=mod
    print(ans%mod)
elif a[0]>=0:
  ans=1
  for i in range(k):
    ans*=a[-1-i]
    ans%=mod
  print(ans%mod)
else:
  from collections import deque
  a=deque(a)
  ans=1
  while k:
    if k==1:
      ans*=a.pop()
      ans%=mod
      k-=1
    else:
      if a[0]*a[1]>=a[-1]*a[-2]:
        ans*=a.popleft()
        ans*=a.popleft()
        ans%=mod
        k-=2
      else:
        ans*=a.pop()
        ans*=a.pop()
        ans%=mod
        k-=2
  print(ans)

Submission status: Accepted

Solution code:
mod = 10**9 + 7
def sgn(v):
    return (v > 0) - (v < 0)
def find_ans():
	v.sort(key=abs, reverse=True)
	ns = 1
	sg = 1
	for a in xrange(k):
	    ns *= v[a]
	    ns %= mod
	    sg *= sgn(v[a])

	if sg >= 0:
	    return ns

	if max(v) <= 0:
	    ns = 1
	    for a in xrange(-k,0):
	        ns *= v[a]
	        ns %= mod
	    return ns

	def helper_f(comp):
	    i = k-1
	    while i >= 0 and comp(v[i]): i -= 1
	    j = k
	    while j < n and not comp(v[j]): j += 1
	    if j == n: j = i
	    return i, j
	i, j = helper_f(lambda w: w >= 0)
	I, J = helper_f(lambda w: w <= 0)
	if I >= 0 and v[j] * v[I] < v[i] * v[J]:
	    i = I
	    j = J

	ns = v[j]
	for a in xrange(k):
	    if a != i:
	        ns *= v[a]
	        ns %= mod
	return ns

n, k = map(int, raw_input().strip().split())
v = map(int, raw_input().strip().split())
print(find_ans())

Submission status: Accepted

Solution code:
from fractions import Fraction as F
mod=10**9+7
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
ret=1
cnt=0
for x in a:
	if x<0:
		b.append((-x,0))
	else:
		b.append((x,1))
b.sort(reverse=True)
p=-1
m=-1
for i in range(k):
	ret*=b[i][0]
	ret%=mod
	if b[i][1]==0:
		cnt+=1
		m=i
	else:
		p=i
if cnt%2==0:
	print(ret)
	exit()
ret1=-1
ret2=-1
f1=f2=0
if p!=-1:
	ret1=ret*pow(b[p][0],mod-2,mod)%mod
	for i in range(k,n):
		if b[i][1]==0:
			ret1*=b[i][0]
			ret1%=mod
			f1=1
			val1=F(b[i][0],b[p][0])
			break
if m!=-1:
	ret2=ret*pow(b[m][0],mod-2,mod)%mod
	for i in range(k,n):
		if b[i][1]==1:
			ret2*=b[i][0]
			ret2%=mod
			f2=1
			val2=F(b[i][0],b[m][0])
			break
if f1==0:
	ret1=-1
if f2==0:
	ret2=-1
if ret1==ret2==-1:
	ret=-1
	for i in range(k):
		ret*=b[-i-1][0]
		ret%=mod
	print(ret%mod)
elif ret1==-1:
	print(ret2)
elif ret2==-1:
	print(ret1)
else:
	if val1>val2:
		print(ret1)
	else:
		print(ret2)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
s = []
f = []
z = 0
for ai in a:
  if ai > 0:
    s.append(ai)
  elif ai < 0:
    f.append(-ai)
  else:
    z += 1
p = len(s)
q = len(f)
l = max(0,k-p)
h = min(k,q)
mod = 10**9+7
if l > h:
  print(0)
  exit()
if l%2 == 0 or h-l >= 1:
  if l%2 == 0:
    c = l
  else:
    c = l+1
  s.sort(reverse=True)
  f.sort(reverse=True)
  while c+2 <= h:
    if f[c]*f[c+1] > s[k-c-1]*s[k-c-2]:
      c += 2
    else:
      break
  ans = 1
  for i in range(c):
    ans =(ans*f[i])%mod
  for i in range(k-c):
    ans = (ans*s[i])%mod
  print(ans)
  exit()
if z > 0:
  print(0)
  exit()
m = s + f
m.sort()
ans = 1
for i in range(k):
  ans = (ans*(m[i]))%mod
ans = (-ans)%mod
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect

N,K = map(int,input().split())
Ali = list(map(int,input().split()))
ans = 1
Ali.sort()
mod = 10**9+7

if K%2 == 1:
  ans = Ali.pop()
  K -= 1
  
Am = Ali[0:bisect(Ali,0)]
Ap = Ali[bisect(Ali,0):]

if ans>=0:
  Am.sort(reverse = True)
  Ap.sort()
else:
  Am.sort()
  Ap.sort(reverse = True)

mp = len(Am)-1
pp = len(Ap)-1

while K>0:
  mmax = -1
  pmax = -1
  if mp >= 1:
    mmax = Am[mp]*Am[mp-1]
  if pp >= 1:
    pmax = Ap[pp]*Ap[pp-1]
    
  if mmax == pmax == -1:
    ans *= Am[0]*Ap[0]
    print(ans%mod)
    exit()
    
  if mmax >= pmax:
    ans = ans * mmax % mod
    mp -= 2
    K -= 2
  else:
    ans = ans * pmax % mod
    pp -= 2
    K -= 2
  



print(ans%mod)

Submission status: Accepted

Solution code:
mod = 10**9+7
def func(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):
            # print(A[i])
            product = (product*A[i])%mod
        return product%mod
    i = 0
    j = n - 1
    if (k & 1):
        product = (product*A[j])%mod
        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 = (product*(left_product)%mod)%mod
            i += 2
        else:
            product = ((right_product%mod)*product)%mod
            j -= 2
    return product%mod 

n,k = list(map(int,input().split()))
arr = list(map(int,input().split()))
ans = func(arr,n,k)
print(ans)
# print(-6%mod)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
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 LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def cal(xx):
    res=1
    for x in xx:
        res=res*x%md
    return res

md=10**9+7
n,k=MI()
aa=LI()
if n==k:
    print(cal(aa))
    exit()
aa.sort(key=lambda x:-abs(x))
#print(aa)
pre=aa[:k]
pos=aa[k:]
mnp=mnn=md
mnpi=mnni=-1
neg=0
for i,a in enumerate(pre):
    if a==0:
        print(0)
        exit()
    if a<0:neg+=1
    if a>0 and a<mnp:
        mnp=a
        mnpi=i
    if a<0 and -a<mnn:
        mnn=-a
        mnni=i
if neg%2:
    mxp=mxn=0
    for a in pos:
        if a > 0 and a > mxp:
            mxp = a
        if a < 0 and -a > mxn:
            mxn = -a
    if (mnni!=-1 and mxp) or (mnpi!=-1 and mxn):
        if mnpi==-1 or mxp*mnp>mxn*mnn:pre[mnni]=mxp
        else:pre[mnpi]=-mxn
    else:
        pre=aa[-k:]

print(cal(pre))

Submission status: Accepted

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np

def main():
	n,k=MI()
	A=LI()
	p=[]
	m=[]
	mod=10**9+7

	for i in A:
		if i>=0:
			p.append(i)
		else:
			m.append(i)
	p.sort(reverse=True)
	m.sort()
	#print(p,m)

	ans=1
	if (p==[] and k%2==1):
		for i in range(k):
			ans*=m[-i-1]
			ans%=mod
			#print(k,ans)

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

	else:
		i=0
		j=0
		pl=len(p)
		ml=len(m)
		while k>=2:
			if i+2<=pl and j+2<=ml:
				pp=p[i]*p[i+1]
				mm=m[j]*m[j+1]
				if pp>mm:
					ans*=pp
					ans%=mod
					i+=2
				else:
					ans*=mm
					ans%=mod
					j+=2
			elif i+2<=pl:
				pp=p[i]*p[i+1]
				ans*=pp
				ans%=mod
				i+=2
			else:
				#print(i,j)
				mm=m[j]*m[j+1]
				ans*=mm
				ans%=mod
				j+=2
			k-=2

		if k==1:
			ans*=p[i]
			ans%=mod
	print(ans)



if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left, bisect_right
from collections import deque
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    idx1 = bisect_left(A, 0)
    idx2 = bisect_right(A, 0)
    A_minus = A[:idx1]
    A_zero = idx2 - idx1
    A_plus = A[idx2:]

    if N == K:
        ans = 1
        for a in A:
            ans *= a
            ans %= mod
        print(ans)
        return
    if N - A_zero < K:
        print(0)
        return
    if N - idx2 == 0 and K % 2 == 0:
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= mod
        print(ans)
        return
    if N - idx2 == 0 and K % 2 != 0:
        if A_zero != 0:
            print(0)
            return
        ans = 1
        for i in range(K):
            ans *= A[N - i - 1]
            ans %= mod
        print(ans)
        return

    if (N - idx2) < K and (K - (N - idx2)) % 2 == 0:
        pos_idx = 0
        neg_idx = K - (N - idx2)
    elif (N - idx2) < K and (K - (N - idx2)) % 2 != 0:
        pos_idx = 1
        neg_idx = K - (N - idx2) + 1
    else:
        pos_idx = (N - idx2) - K
        neg_idx = 0

    while pos_idx < N - idx2 - 1 and neg_idx < idx1 - 1:
        x = A_plus[pos_idx] * A_plus[pos_idx + 1]
        y = A_minus[neg_idx] * A_minus[neg_idx + 1]
        if x < y:
            pos_idx += 2
            neg_idx += 2
        else:
            break

    ans = 1
    for i in range(pos_idx, N - idx2):
        ans *= A_plus[i]
        ans %= mod
    for i in range(neg_idx):
        ans *= A_minus[i]
        ans %= mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def rev(i):
    ni = i
    ans = 1
    t = 10**9+5
    mod = 10**9+7
    while t > 0:
        if t&1:
            ans = (ans*ni)%mod
        t >>= 1
        ni = (ni**2)%mod
    return ans

def main():
    n,k = map(int,ipt().split())
    a = [(abs(int(i)),int(i)) for i in ipt().split()]
    Mi = 10**9
    Ma = -10**9
    mod = 10**9+7
    a.sort(reverse=True)
    if n == k:
        ans = 1
        for i in a:
            ans = (ans*i[1])%mod
        print(ans)
        exit()
    for i in a:
        if Ma < i[1]:
            Ma = i[1]
        if Mi > i[1]:
            Mi = i[1]
    if Ma < 0 and k&1:
        ans = 1
        for i,ai in enumerate(a[::-1]):
            ans = (ans*ai[0])%mod
            if i == k-1:
                break
        print((-ans)%mod)
        exit()
    pp = None
    pm = None
    ans = 1
    s = 1
    for i,ai in enumerate(a[:k:]):
        ans = ans*ai[0]%mod
        if ai[1] == 0:
            print(0)
            exit()
        elif ai[1] > 0:
            pp = ai[0]
        else:
            pm = ai[0]
            s *= -1
    if s == 1:
        print(ans)
        exit()
    np = 0
    nm = 0
    for ai in a[k::]:
        if ai[1] > 0 and not np:
            np = ai[0]
        elif ai[1] < 0 and not nm:
            nm = ai[0]
        if np and nm:
            break
    if pp == None:
        if np == None:
            print(0)
        else:
            print(ans*rev(pm)*np%mod)
    elif nm == None and np == None:
        print(0)
    elif nm == None:
        print(ans*rev(pm)*np%mod)
    elif np == None:
        print(ans*rev(pp)*nm%mod)
    else:
        if nm*pm < np*pp:
            print(ans*rev(pm)*np%mod)
        else:
            print(ans*rev(pp)*nm%mod)



    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations
mod=10**9+7
def solve(n,k,a):
  if min(a)>0:
    ans=1
    a.sort(reverse=1)
    for i in a[:k]:
      ans*=i
      ans%=mod
    return ans
  if max(a)<0:
    if k%2==0:
      a.sort()
      ans=1
      for i in a[:k]:
        ans*=i
        ans%=mod
      return ans
    else:
      a.sort(reverse=1)
      ans=1
      for i in a[:k]:
        ans*=i
        ans%=mod
      return ans
  if n==k:
    ans=1
    for i in a:
      ans*=i
      ans%=mod
    return ans
  if k==1:
    return max(a)
  if n-k==1:
    ans=1
    if a.count(0)>1:return 0
    p=[]
    m=[]
    for i in a:
      if i>0:p.append(i)
      elif i<0:m.append(i)
    if 0 in a:
      if len(m)%2==0:
        for i in a:
          if i==0:continue
          ans=(ans*i)%mod
      else:ans=0
    else:
      if len(m)%2==0:
        for i in sorted(p)[1:]+m:ans=(ans*i)%mod
      else:
        for i in p+sorted(m)[:-1]:ans=(ans*i)%mod
    return ans


  ans=1
  p=[]
  m=[]
  for i in a:
    if i<0:m.append(i)
    elif i>=0:p.append(i)
  p.sort()
  m.sort(reverse=1)

  while k>1:
    if k<=5:
      if len(p)>=10:p=p[-10:]
      if len(m)>=10:m=m[-10:]
      ans*=solve2(len(p)+len(m),k,m+p)
      ans%=mod
      k=0
      break
    if len(p)<2:
      ans*=m.pop()*m.pop()
      k-=2
    elif len(m)<2:
      ans*=p.pop()*p.pop()
      k-=2
    elif m[-1]*m[-2]>p[-1]*p[-2]:
      ans*=m.pop()*m.pop()
      k-=2
    else:
      ans*=p.pop()*p.pop()
      k-=2
    ans%=mod
  if k:
    ans*=p.pop()
  return ans
  print(ans%mod)

def solve2(n,k,a):
  ans=-10**20
  for c in combinations(range(n),k):
    anss=1
    for i in c:anss*=a[i]
    ans=max(ans,anss)
  return ans%mod

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

"""
from random import randint
for i in range(10000):
  n=randint(1,10)
  k=randint(1,n)
  a=sorted([randint(-10,10)for _ in range(n)])
  print(n,k,a)
  ans1=solve(n,k,a)
  ans2=solve2(n,k,a)
  if ans1==ans2:print("ok")
  else:
    print("error")
    print(n,k)
    print(*a)
    print(ans1,ans2)
    exit()
"""

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,K=map(int,input().split())
A=list(map(int,input().split()))
A_m=[x for x in A if x<0]
A_pz=[x for x in A if x>=0]
A_m.sort()
A_pz.sort(reverse=1)
if N==K:
    ans=1
    for x in A:
        ans*=x
        ans%=MOD
elif not A_pz and K%2==1:
    ans=1
    for x in A_m[::-1][:K]:
        ans*=x
        ans%=MOD
else:
    B=[]
    for i in range(len(A_m)//2):
        B.append(A_m[i*2]*A_m[i*2+1])
    B.sort(reverse=1)
    i,j=0,0
    ans=1
    while i+j*2<=K-2:
        if i<len(A_pz)-1 and j<len(B):
            if A_pz[i]*A_pz[i+1]>B[j]:
                ans*=A_pz[i]*A_pz[i+1]
                i+=2
            else:
                ans*=B[j]
                j+=1
        elif i<len(A_pz)-1:
            ans*=A_pz[i]*A_pz[i+1]
            i+=2
        else:
            ans*=B[j]
            j+=1
        ans%=MOD
    if i+j*2==K-2:
        if i<len(A_pz)-1 and j<len(B):
            ans*=max(A_pz[i]*A_pz[i+1],B[j])
        elif i<len(A_pz)-1:
            ans*=A_pz[i]*A_pz[i+1]
        else:
            ans*=B[j]
    elif i+j*2==K-1:
        if i<len(A_pz):
            ans*=A_pz[i]
        else:
            ans*=A_m[-1]
    ans%=MOD
ans%=MOD
print(ans)