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

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

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

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

n,k = m()

a = l()

a.sort()

mina = []

pra = []

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

lp = len(pra)

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

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


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

		else:
			break
	if cm % 2 != 0:
		if cp == lp-1:
			cp -= 1
			cm -= 1

		else:
			if cp != -1 and cm != lm:
				if pra[cp+1] != 0 and pra[cp]/-mina[cm-1] <= -mina[cm]/pra[cp+1]:
					cp += 1
					cm += 1
				else:
					cp -= 1
					cm -= 1
			elif cp != -1:
				cp -= 1
				cm -= 1
			elif cm != lm:
				cp += 1
				cm += 1

		

	#data.sort()
	co = 0

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


		
	print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9+7
a.sort()
mi = []
pl = []
zero = 0
for i in a:
    if i < 0:
        mi.append(i)
    elif i == 0:
        zero += 1
    else:
        pl.append(i)
pl = sorted(pl,reverse=True)
if pl == []:
    if k%2:
        if zero:
            print(0)
        else:
            ans = 1
            count = 0
            while count < k:
                ans *= a[-1-count]
                ans %= mod
                count += 1
            print(ans)
            
    else:
        ans = 1
        count = 0
        while count < k:
            ans *= a[count]
            ans %= mod
            count += 1
        print(ans)
        
    exit()

ip = 0
im = 0
if k%2:
    count = pl[0]
    k -= 1
    ip += 1
else:
    count = 1
while k > 0:
    check1 = True
    check2 = True
    if ip+2 <= len(pl):
        x = pl[ip]*pl[ip+1]
        
    else:
        x = 1
        check1 = False
    if im+2 <= len(mi):
        y = mi[im]*mi[im+1]
    else:
        y = 1
        check2 = False
    if x >= y:
        if check1:
            ip += 2
            count = (x*count)%mod
    else:
        if check2:
            im += 2
            count = (y*count)%mod
    if check1 == False and check2 == False:
        break
    k -= 2
if k:
    if ip == len(pl) and im == len(mi):
        print(0)
    elif ip < len(pl) and im < len(mi):
        if zero:
            print(0)
        else:
            count *= (pl[ip]*mi[ip])%mod
            print(count%mod)
    else:
        print(0)
else:
    print(count%mod)

Submission status: Wrong Answer

Solution code:
# WA
from itertools import accumulate
from collections import deque
import sys
input = sys.stdin.readline

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort(reverse = True, key = lambda x : abs(x))
Aneg = [1 if A[i] < 0 else 0 for i in range(len(A))]
cum = list(accumulate(Aneg)) + [0]
p = 10 ** 9 + 7

# que = deque(A)
ans = 1
if (cum[N - 1] == N and K % 2 == 1) or K == N:  # 絶対マイナス使わなくちゃいけない
    for i in range(N - 1, N - K - 1, -1):
        ans = ans * A[i] % p
    print(ans)
    sys.exit()

k = 0
neg = False
# avoid = 1
for i in range(N):
    if A[i] == 0:
        ans = 0
        break
    if k >= K: break
    if A[i] > 0:
        ans = ans * abs(A[i]) % p
        k += 1
    elif neg:
        ans = ans * abs(A[i]) % p
        k += 1
        neg = not neg
    else:
        if cum[N - 1] - cum[i - 1] < 2 or k + 2 > K:
            continue
        ans = ans * abs(A[i]) % p
        k += 1
        neg = not neg
if neg:
    ans = (-ans) % p
print(ans)

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)
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:
n,k=map(int,input().split())
a=[0]*n
a=list(map(int,input().split()))
a=sorted(a)
mod=10**9+7
ans=1

if (k%2==0 or a[-1]>=0):
    mlt1=a[0]*a[1]
    mlt2=a[-2]*a[-1]
    l=0
    r=-1
    for i in range(k//2):
        if (mlt1>=mlt2):
            ans*=mlt1%mod
            l+=2
            if (l<=n-2):
                mlt1=a[l+1]*a[l]
        else:
            ans*=mlt2%mod
            r-=2
            if (r>=-n+1):
                mlt2=a[r-1]*a[r]
            ans%=mod
    if (k%2==1):
        ans*=a[r]
        ans%=mod
    
else:
    for i in range(k):
        ans*=a[n-1-i]
        ans%=mod
        
print(ans)

Submission status: Wrong Answer

Solution code:
import copy

n, k = map(int, input().split())
a = list(map(int, input().split()))
d = []
for i in range(n):
    d.append([abs(a[i]), i])
d = sorted(d, reverse=True, key=lambda x: x[0])

b = sorted(a, reverse=True)
frag = True
ans = 1
for i in range(n):
    if(a[i] > 0):
        frag = False
if(frag and k % 2 == 1):
    for i in range(k):
        ans *= b[i]
else:
    for i in range(k):
        ans *= a[d[i][1]]
    if(ans < 0):
        ans = ans // b[0]
        ans *= b[n-1]
MOD = 1000000007

ans = ans % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(key=lambda x: abs(x), reverse=True)
ans = 1
if N == K:
    for i in range(K):
        ans *= A[i]
        if abs(ans) > mod:
            ans %= mod
elif len([v for v in A if v <= 0]) == N:
    for i in range(K):
        ans *= A[-(i + 1)]
        if abs(ans) > mod:
            ans %= mod
else:
    num_hu = len([v for v in A[:K] if v < 0])
    if num_hu % 2 == 0:
        for i in range(K):
            ans *= A[i]
            if abs(ans) > mod:
                ans %= mod
    else:
        if len([v for v in A[K:] if v >= 0]) == N - K:
            min_hu_idx = K - 1
            while True:
                if A[min_hu_idx] < 0:
                    break
                min_hu_idx -= 1
            max_sei_idx = K
            for i in range(K):
                if i == min_hu_idx:
                    ans *= A[max_sei_idx]
                else:
                    ans *= A[i]
                if abs(ans) > mod:
                    ans %= mod
        elif len([v for v in A[K:] if v <= 0]) == N - K:
            print('aaa')
            min_sei_idx = K - 1
            while True:
                if A[min_sei_idx] > 0:
                    break
                min_sei_idx -= 1
            max_hu_idx = K
            for i in range(K):
                if i == min_sei_idx:
                    ans *= A[max_hu_idx]
                else:
                    ans *= A[i]
                if abs(ans) > mod:
                    ans %= mod
        else:
            ans_1 = 1
            ans_2 = 1
            # ans_1
            min_hu_idx = K - 1
            while True:
                if A[min_hu_idx] < 0:
                    break
                min_hu_idx -= 1
            max_sei_idx = K
            while True:
                if A[max_sei_idx] > 0:
                    break
                max_sei_idx += 1
            for i in range(K):
                if i == min_hu_idx:
                    ans_1 *= A[max_sei_idx]
                else:
                    ans_1 *= A[i]
                if abs(ans_1) > mod:
                    ans_1 %= mod
            # ans_2
            min_sei_idx = K - 1
            while True:
                if A[min_sei_idx] > 0:
                    break
                min_sei_idx -= 1
            max_hu_idx = K
            while True:
                if A[max_hu_idx] < 0:
                    break
                max_hu_idx += 1
            for i in range(K):
                if i == min_sei_idx:
                    ans_2 *= A[max_hu_idx]
                else:
                    ans_2 *= A[i]
                if abs(ans_2) > mod:
                    ans_2 %= mod
            ans = max(ans_1, ans_2)
print(ans % mod)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9+7
a.sort()
mi = []
pl = []
zero = 0
for i in a:
    if i < 0:
        mi.append(i)
    elif i == 0:
        zero += 1
    else:
        pl.append(i)
pl = sorted(pl,reverse=True)
if n-zero < k:
    print(0)
    exit()

if pl == []:
    if k%2:
        if zero:
            print(0)
        else:
            ans = 1
            count = 0
            while count < k:
                ans *= a[-1-count]
                ans %= mod
                count += 1
            print(ans)
            
    else:
        ans = 1
        count = 0
        while count < k:
            ans *= a[count]
            ans %= mod
            count += 1
        print(ans)
        
    exit()

ip = 0
im = 0
if k%2:
    count = pl[0]
    k -= 1
    ip += 1
else:
    count = 1
while k > 0:
    check1 = True
    check2 = True
    if ip+2 <= len(pl):
        x = pl[ip]*pl[ip+1]
        
    else:
        x = 1
        check1 = False
    if im+2 <= len(mi):
        y = mi[im]*mi[im+1]
    else:
        y = 1
        check2 = False
    if x >= y:
        if check1:
            ip += 2
            count = (x*count)%mod
    else:
        if check2:
            im += 2
            count = (y*count)%mod
    if check1 == False and check2 == False:
        break
    k -= 2
if k:
    if ip == len(pl) and im == len(mi):
        print(0)
    elif ip < len(pl) and im < len(mi):
        if zero:
            print(0)
        else:
            count *= (pl[ip]*mi[ip])%mod
            print(count%mod)
    else:
        print(0)
else:
    print(count%mod)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left,bisect_right
p=10**9+7
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
pi=1
ni=0
ans=1
for _ in range(k//2):
  if a[ni]*a[ni+1]>a[-pi]*a[-pi-1]:
    ans=ans*a[ni]*a[ni+1]%p
    ni+=2
  else:
    ans=ans*a[-pi]*a[-pi-1]%p
    pi+=2
if k%2==1:
  ans=ans*a[-pi]%p
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,k = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=True,key=lambda x: abs(x))

def main(n,k,a):
    a = np.array(a)
    if (a<0).all() and k%2==1 : return np.prod(a[-1*k:])
    prod_idx = list(range(k))
    if np.prod(2*(a[prod_idx]>0)-1)>0:
        prod = 1
        for i in prod_idx:
            prod = (prod*a[i])%1000000007
        return prod
    else:
        p_1 = prod_idx
        p_1_new = []
        for i in range(k-1,-1,-1):
            if a[i]<0:
                p_1.remove(i)
                p_1_new.append(i)
                break
        for i in range(k,len(a)):
            if a[i]>0:
                p_1.append(i)
                p_1_new.append(i)
                break
        p_2 = prod_idx
        p_2_new = []
        for i in range(k-1,-1,-1):
            if a[i]>0:
                p_2.remove(i)
                p_2_new.append(i)
                break
        for i in range(k,len(a)):
            if a[i]<=0:
                p_2.append(i)
                p_2_new.append(i)
                break
        if len(p_1_new)==2 and len(p_2_new)==2:
            if abs(p_1_new[0]*p_2_new[1]) <= abs(p_2_new[0]*p_1_new[1]):
                prod = 1
                for i in p_2:
                    prod = (prod*a[i])%1000000007
                return prod
            else:
                prod = 1
                for i in p_1:
                    prod = (prod*a[i])%1000000007
                return prod
        if len(p_1_new)==2:
            prod = 1
            for i in p_1:
                prod = (prod*a[i])%1000000007
            return prod
        else:
            prod = 1
            for i in p_2:
                prod = (prod*a[i])%1000000007
            return prod


        


print(main(n,k,a)%1000000007)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
input=sys.stdin.readline

def fact(arr):
  ans = 1
  for s in arr:
    ans *= s
    ans = ans % (int(10**9+7))
  return ans

def main():
  N, K = map(int, input().split(' '))
  A = list(map(int, input().split(' ')))
  Aplus = []
  Aminus = []
  for a in A:
    if(a >= 0):
      Aplus.append(a)
    else:
      Aminus.append(a)
  Aplus= sorted(Aplus, reverse=True)
  Aminus= sorted(Aminus)
  Aabs = sorted(A, key=lambda x:abs(x), reverse=True)
  plusnum=0
  minusnum=0
  for i in range(K):
    if(Aabs[i] >= 0):
      plusnum+=1
    else:
      minusnum += 1
  if(minusnum % 2 == 1):
    if(minusnum > 0 and plusnum > 0):
      if minusnum < len(Aminus):
        if (plusnum < len(Aplus)):
          if(abs(Aplus[plusnum] * Aminus[minusnum - 2]) > abs(Aplus[plusnum - 2] * Aminus[minusnum])):
            plusnum+=1
            minusnum-=1
          else:
            plusnum-=1
            minusnum+=1
        else:
          plusnum+=1
          minusnum-=1
      else:
        plusnum-=1
        minusnum+=1
  if(plusnum == 0):
    print(int(fact(Aminus[::-1][:minusnum])))
  else:    
    print(int(fact(Aplus[:plusnum]+Aminus[:minusnum])))

if __name__=='__main__':
  main()

Submission status: Wrong Answer

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

zeros = []
pluss = []
minuss = []

for i in range(N):
    if A[i]>0:
        pluss.append(A[i])
    elif A[i]==0:
        zeros.append(A[i])
    else:
        minuss.append(A[i])

pluss = sorted(pluss, reverse = True)
minuss = sorted(minuss)


if len(pluss) + (min(len(minuss), K)//2)*2 >= K:
    answer_type = 1
elif len(zeros) > 0:
    answer_type = 2
else:
    answer_type = 3

rest = K
if answer_type == 1:
    plus_now = 0
    minus_now = 0
    minus_counter = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = -1000000000000
        
        if minus_now < len(minuss):
            minus_target = minuss[minus_now]
        else:
            minus_target = 1000000000000
        
        if plus_target >= -minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
            minus_counter += 1
            
            
    
    if minus_counter%2 == 1:
        if minus_now >= len(minuss):
            answer = answer * pow(minuss[minus_now-1],mod-2,mod)
            answer = answer * pluss[plus_now]
        elif plus_now >= len(pluss):
            answer = answer * pow(pluss[plus_now-1],mod-2,mod)
            answer = answer * minuss[minus_now]
        elif pluss[plus_now]/(-1*minuss[minus_now-1]) > -1*minuss[minus_now]/(pluss[plus_now-1]):
            answer = answer * pow(minuss[minus_now-1],mod-2,mod)
            answer = answer * pluss[plus_now]

elif answer_type == 2:
    answer = 0
elif answer_type == 3:
    minuss = sorted(minuss, reverse = True)
    pluss = sorted(pluss, reverse = True)
    plus_now = 0
    minus_now = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = 10000000000000
        
        if minus_now < len(minuss):
            minus_target = minuss[minus_now]
        else:
            minus_target = -1000000000000  
        
        if plus_target <= -minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
print(answer%mod)

Submission status: Wrong Answer

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

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

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

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

n,k = m()

a = l()

a.sort()

mina = []

pra = []

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

lp = len(pra)

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

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


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

		else:
			break
	if cm % 2 != 0:
		if cp == 0:
			cp += 1
			cm += 1

		else:

			if cp-1 != -1 and cm + 1 != lm:
				if pra[cp] != 0 and pra[cp-1]/-mina[cm] <= -mina[cm+1]/pra[cp]:
					cp -= 1
					cm -= 1
				else:
					cp += 1
					cm += 1
			elif cp-1 != -1:
				cp -= 1
				cm -= 1
			elif cm + 1 != lm:
				cp += 1
				cm += 1

		

	#data.sort()
	co = 0

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


		
	print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A, key=abs,reverse=True)
B=[0]*N
for i in range(N):
  if A[i]>=0:
    B[i]=1
  else:
    B[i]=-1

ans=1

p1=-1
for i in range(K):
  if B[i]==1:
    p1=i

p2=-1
for i in reversed(range(K,N)):
  if B[i]==1:
    p2=i

n1=-1
for i in range(K):
  if B[i]==-1:
    n1=i

n2=-1
for i in reversed(range(K,N)):
  if B[i]==-1:
    n2=i

if B[:K].count(-1)%2==0:
  for i in range(K):
    ans=(ans*A[i])%(10**9+7)
elif K%2==1 and sum(B)==-len(B):
  for i in range(N-K,N):
    ans=(ans*A[i])%(10**9+7)
elif n1>=0 and p2>=0:
  if p1>=0 and n2>=0:
    if A[p2]/A[n1] >= A[n2]/A[p1]:
      for i in range(K):
        if i ==n1:
          ans=(ans*A[p2])%(10**9+7)
        else:
          ans=(ans*A[i])%(10**9+7)
    else:
      for i in range(K):
        if i ==p1:
          ans=(ans*A[n2])%(10**9+7)
        else:
          ans=(ans*A[i])%(10**9+7)
  else:
    for i in range(K):
      if i ==n1:
        ans=(ans*A[p2])%(10**9+7)
      else:
        ans=(ans*A[i])%(10**9+7)
elif p1>=0 and n2>=0:
  for i in range(K):
    if i ==p1:
      ans=(ans*A[n2])%(10**9+7)
    else:
      ans=(ans*A[i])%(10**9+7)
else:
  for i in range(K):
    ans=(ans*A[i])%(10**9+7)
print(ans)

Submission status: Wrong Answer

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

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

if sgn>0:
  print(answer)
else:
  pos_absmax=0
  neg_absmax=0
  for i in reversed(range(K,N)):
    aa,a=aalist[i]
    if a>0:
      pos_absmax=a
    else:
      neg_absmax=a
      
  if abs(pos_absmin*neg_absmax)>abs(pos_absmax*neg_absmin):
    answer*=neg_absmax
    answer*=pow(pos_absmin,MOD-2,MOD)
    answer%=MOD
  else:
    answer*=pos_absmax
    answer*=pow(neg_absmin,MOD-2,MOD)
    answer%=MOD
  
  print(answer)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
li_a = list(map(int, input().split()))
mod = 10**9+7
li = []
lll = 0
for i in li_a:
    if i < 0:
        li.append((abs(i), -1))
        lll += 1
    else:
        li.append((i, 1))
li.sort()
if lll == n:
    ans = 1
    if k %2 ==1:
        for i in range(k):
            ans *= -li[i][0]
            ans %= mod
        print(ans)
        exit()
    else:
        for i in range(k):
            ans *= li[n-1-i][0]
            ans %= mod
        print(ans)
        exit()
ans = 1
guki = 1
for i in range(n-1, n-k-1, -1):
    ans *= li[i][0]
    ans %= mod
    guki *= li[i][1]
if guki > 0:
    print(ans)
else:
    P, M, p, m = 10**6, 1000000, 1000000, 1000000
    P1, M1, p1, m1 = True, True, True, True
    for i in range(n-k, n):
        if li[i][1] > 0:
            Plus = li[i][0]
            P = i
            P1 = False
            break
    for i in range(n-k, n):
        if li[i][1] < 0:
            Mini = li[i][0]
            M = i
            M1 = False
            break
    if n-k-1 >= 0:
        for i in range(n-k-1, -1, -1):
            if li[i][1] > 0:
                plus = li[i][0]
                p = i
                p1 = False
                break
        for i in range(n-k-1, -1, -1):
            if li[i][1] < 0:
                mini = li[i][0]
                m = i
                m1 = False
                break
    ans1 = 1
    ans2 = 1
    if (not P1) and (not m1):
        for i in range(n-1, n-k-1, -1):
            if i == P:
                continue
            ans1 *= li[i][0]
            ans1 %= mod
        ans1 *= li[m][0]
        ans1 %= mod
    if (not p1) and (not M1):
        for i in range(n-1, n-k-1, -1):
            if i == M:
                continue
            ans2 *= li[i][0]
            ans2 %= mod
        ans2 *= li[p][0]
        ans2 %= mod
    if (not p1) and (not P1) and (not M1) and (not m1):
        if mini/Plus > plus/Mini:
            print(ans1)
        else:
            print(ans2)
    elif (not p1) and (not M1):
        print(ans2)
    elif (not m1) and (not P1):
        print(ans1)
    else:
        ans = 1
        for i in range(k):
            ans *= -li[i][0]
            ans %= mod
        print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
mod = 10 ** 9 + 7

n, k = map(int, input().split())
a = list(map(int, input().split()))
a_abs = list(map(abs, a))
a_sign = list(map(np.sign, a))
a_sort_idx = np.argsort(-np.array(a_abs))

plus = 0
minus = 0
zero = 0
for sign in a_sign:
    if sign == 0:
        zero += 1
    if sign == 1:
        plus += 1
    if sign == -1:
        minus += 1

def modinv(a):
    b = mod
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= mod
    if u < 0:
        u += m
    return u

def is_plus_possible():
    minus_div2 = minus // 2
    return (k - minus_div2 <= plus)

if is_plus_possible():
    flag = 1
    ans = 1
    last_sign_idx = [-1, -1]
    for i in range(k):
        flag *= a_sign[a_sort_idx[i]]
        ans = ans * a[a_sort_idx[i]] % mod
        if a_sign[a_sort_idx[i]] == 1:
            last_sign_idx[0] = i
        else:
            last_sign_idx[1] = i
    if flag == 1:
        print(ans)
        exit()
    else:
        last_sign = a_sign[a_sort_idx[k - 1]]
        rev_sign = last_sign * -1
        if last_sign == -1:
            if last_sign_idx[0] == -1:
                ans = ans * modinv(a[a_sort_idx[k - 1]]) % mod
                for i in range(k, n):
                    if a_sign[a_sort_idx[i]] == rev_sign:
                        ans = ans * a[a_sort_idx[i]] % mod
                        break
            print(ans)
            exit()
        else:
            big1 = a[a_sort_idx[k - 1]]
            big2 = a[a_sort_idx[last_sign_idx[0]]]
            if rev_sign == -1:
                big2 = a[a_sort_idx[last_sign_idx[1]]]
            small1, small2 = 10 ** -10, 10 ** -10
            for i in range(k, n):
                if a_sign[a_sort_idx[i]] == rev_sign:
                    small1 = a[a_sort_idx[i]]
                    break
            for i in range(k, n):
                if a_sign[a_sort_idx[i]] == last_sign:
                    small2 = a[a_sort_idx[i]]
                    break
            big, small = big1, small1
            if big1 / small1 >= big2 / small2:
                big, small = big2, small2
            ans = ans * modinv(big) % mod * small % mod
            print(ans)
            exit()
else:
    if zero > 0:
        print(0)
    else:
        a_abs.sort()
        ans = -1 % mod
        for i in range(k):
            ans = ans * a_abs[i] % mod
        print(ans)