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

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


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

		else:
			break

	#data.sort()
	co = 0

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

	"""
	while co <= k:
		if k - co >= 2:
			if data[co] * data[co+1] >= 0:
				ans *= (data[co] * data[co+1]) % mod
				ans %= mod
				co += 2
			else:
				ans *= data[co]
				ans %= mod
				ans *= data[co+1]
				ans %= mod
				co += 2
		elif k - co == 1:
			ans *= data[co]
			ans %= mod
			co += 1
		else:
			break
	"""

		
	print(ans)

Submission status: Wrong Answer

Solution code:
import sys, math,os
from io import BytesIO, IOBase
#data = BytesIO(os.read(0,os.fstat(0).st_size)).readline
# from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
# from decimal import Decimal
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write(' '.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
#sys.setrecursionlimit(100000 + 1)
INF = 10**9
mod = 10**9 + 7


n,k=mdata()
a=mdata()
n1,p=-1,-1
a1=[(abs(a[i]),a[i]) for i in range(n)]
a1.sort(reverse=True)
ans=1
c=1
for i in range(k):
    if a1[i][1]>0:
        p=i
    elif a1[i][1]<0:
        n1=i
        c*=-1
    else:
        c=0
    ans=(ans*a1[i][1])%mod
if c>=0:
    out(ans%mod)
else:
    ans1=ans
    for i in range(k,n):
        if a1[i][1]>=0:
            ans1=max(ans*(pow(a1[n1][1],mod-2,mod))*a1[i][1],ans)
            c=1
        if a1[i][1]<0 and p!=-1:
            ans1=max(ans*pow(a1[p][1],mod-2,mod)*a1[i][1],ans)
            c=1
    ans=ans1
    if c<0:
        ans=1
        for i in range(k):
            ans = (ans*a1[n-i-1][1])%mod
    out(ans%mod)

Submission status: Wrong Answer

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

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

pos = []
nag = []
pn = []
zero = 0

for i in range(N):
    if A[i] > 0:
        pos.append(A[i])
        pn.append((A[i], True))
    elif A[i] < 0:
        nag.append(A[i])
        pn.append((-A[i], False))
    else:
        zero += 1

pos.sort()
nag.sort(reverse=True)
pn.sort()

# hard case work
if N - zero < K:
    print(0)

elif N - zero == K:
    ans = 1
    if len(nag) & 1 == 0:
        for k in nag + pos:
            ans *= k
            ans %= MOD
    else:
        ans = 0
    print(ans)

elif N == K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)

elif not pos and zero > 0:
    print(0)

elif not pos:
    ans = 1
    if K & 1:
        for i in range(K):
            ans *= nag[i]
            ans %= MOD
    else:
        for i in range(K):
            ans *= nag[-i-1]
            ans %= MOD
    print(ans)



# nagative and positive
else:
    # large first
    arr = []

    for i in range(K):
        if not pos: break
        arr.append(pos.pop())

    while len(arr) < K:
        arr.append(1)

    ans = 1

    while arr:
        if len(arr) == 1:
            ans *= arr[0]
            ans %= MOD
            break

        a = arr.pop()
        b = arr.pop()
        if len(nag) < 2:
            ans *= a * b
            ans %= MOD
        else:
            x = nag.pop()
            y = nag.pop()
            ans *= max(x * y, a * b)
            ans %= MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def main():
    from collections import Counter
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    posi = [a for a in A if a > 0]
    nega = [a for a in A if a < 0]
    posi.sort(reverse=True)
    nega.sort(reverse=True)
    A.sort(reverse=True, key=abs)
    if len(posi) + len(nega) < K:
        # 0を含まなければいけないとき
        return print(0)

    ans = modint(1)
    if K % 2 == 1 and len(posi) < K:
        # 結果が負数
        # 絶対値が小さいやつをK個取ってくる
        A.sort(key=abs)
        for a in A[:K]:
            ans *= a
    else:
        # 結果が正になるように注意しなければいけない
        # skipしてかけるものがなくなったらこわい
        # 負数がK以下の奇数個しかないとハマる
        if sum(a < 0 for a in A[:K]) % 2 == 0:
            for a in A[:K]:
                ans *= a
        else:
            ans1 = modint(1)  # 正を取り除く
            ans2 = modint(1)  # 負を取り除く
            posi = [a for a in A[:K] if a > 0]
            nega = [a for a in A[:K] if a < 0]
            p_remove = False
            for a in A[:K][::-1]:
                if a > 0 and not p_remove:
                    p_remove = True
                    continue
                ans1 *= a
            n_remove = False
            for a in A[:K][::-1]:
                if a < 0 and not n_remove:
                    n_remove = True
                    continue
                ans2 *= a
            mul1 = 0  # 一番大きい正
            mul2 = 0  # 　一番大きい負
            for a in A[K:]:
                if mul1 == 0 and a > 0:
                    mul1 = a
                if mul2 == 0 and a < 0:
                    mul2 = a
                if mul1 != 0 and mul2 != 0:
                    break
            if len(posi) == 0 or mul2 == 0:
                ans = ans2 * mul1
            elif len(nega) == 0 or mul1 == 0:
                ans = ans1 * mul2
            else:
                ans = max(int(ans1*mul2), int(ans2*mul1))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
M = 10**9 + 7
N, K = list(map(int,input().split()))
A = list(map(int,input().split()))
B = [] # 1以上
C = [] # -1以下

for x in A:
  if (x == 0):
    N-=1
  elif x > 0:
    B.append(x)
  elif x < 0:
    C.append(-x)

if N < K:
  print(0)
  exit(0)

if K%2 == 1 and len(B) == 0:
  AN = 1
  C.sort()
  for i,x in enumerate(C):
    if i == K:
      break
    AN *= x
    AN %= M
  AN *= -1; AN %= M; AN += M; AN %= M;
  print(AN)
  exit(0)

AN = 1
if K%2 == 1:
  AN *= max(B)
  B.remove(max(B))
  K -= 1

B.sort(reverse=True)
C.sort(reverse=True)

for i in range(len(B), K):
  B.append(1)
for i in range(len(C), K):
  C.append(1)
for i in range(K):
  AN *= B[i]
MA = AN
# print(AN)
for i in range(0,K,2):
  AN //= B[K-1-i] * B[K-2-i]
  AN *= C[i] * C[i+1]
  MA = max(AN, MA)
  # print(AN)

# print(B)
# print(C)
# print(K)
print(MA%M)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun May  3 16:22:00 2020

@author: neb0123
"""

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

if __name__ == "__main__":
    N,K = map(int, input().split(' '))
    A = list(map(int,input().split(' ')))
    print(maxProductSubarrayOfSizeK(A,N,K) % (10**9 + 7))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
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))
cum = list(accumulate([1 if A[i] < 0 else 0 for i in range(len(A))])) + [0]
p = 10 ** 9 + 7

ans = 1
if cum[N - 1] == N:  # 全部マイナス
    for i in range(N - 1, N - K - 1, -1):
        ans = ans * A[i] % p
    print(ans)
    sys.exit()

k = 0
neg = False
for i in range(N):
    if i == 0 and A[i] == 0:
        ans = 0
        break
    if A[i] == 0 or 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:
            continue
        ans = ans * abs(A[i]) % p
        k += 1
        neg = not neg

print(ans)

Submission status: Wrong Answer

Solution code:

def main():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    A = sorted(A)

    mod = 10**9+7
    fst = 0
    lst = N-1

    if K==1:
        print(A[lst])
        return

    elif A[N-1]<=0:
        ans =A[N-1]
        lst = N-2
        for i in range(K-1):
            ans *= A[lst]
            # print(ans,A[lst])
            lst -= 1
            ans %= mod
        print(ans)
        # print( (((-1)%mod)*((-2)%mod)*((-3)%mod))%mod)
        return


    if A[lst]*A[lst-1] >= A[fst]*A[fst+1]:
        ans = A[lst]*A[lst-1]
        lst -= 2
    else:
        ans = A[fst]*A[fst+1]
        fst += 2

    cnt = 2
    while(cnt<K):
        if abs(A[lst])>=abs(A[fst]):
            ans *= abs(A[lst])
            lst -= 1
            cnt += 1
            
        elif A[lst]*A[lst-1] <= A[fst]*A[fst+1] and K-cnt>=2:
            ans *= A[fst]*A[fst+1]
            fst += 2
            cnt += 2
        
        else:
            ans *= abs(A[lst])
            lst -= 1
            cnt += 1
        # print(fst,lst)
        ans %= mod
    print(ans)
    return
        


main()

Submission status: Wrong Answer

Solution code:
def maxProduct(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
    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 
    
n,k=map(int,input().split())
lst=list(map(int,input().strip().split()))[:n]
print((maxProduct(lst,n,k))%1000000007)

Submission status: Wrong Answer

Solution code:
MOD = int(1e9+7)
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
flag = 0
for a in A:
    if a>0:
        flag = 1
        break
#すべてマイナスか0
if flag == 0 and K%2==1:
    A.sort(reverse = True)
    ans = 1
    for i in range(K):
        ans = (ans*A[i]) % MOD
    print(ans)
#それ以外
else:
    A = sorted(A, key=abs, reverse = True)
    last_pos = -1
    last_neg = -1
    count_neg = 0
    is_zero = 0
    ans = 1
    for i in range(K):
        ans = (ans*A[i]) % MOD
        if A[i]>0:
            last_pos = i
        elif A[i]<0:
            last_neg = i
            count_neg += 1
        else:
            is_zero = 1
            break
    if is_zero == 1:
        print(0)
    elif count_neg%2 == 0:
        print(ans)
    else:
        flag_pos = 0
        flag_neg = 0
        new_pos = -1
        new_neg = -1
        for i in range(K,N):
            if A[i]>0 and flag_pos==0:
                flag_pos = 1
                new_pos = i
            elif A[i]<0 and flag_neg==0:
                flag_neg = 1
                new_neg = i
            if flag_pos == 1 and flag_neg == 1:
                break

        if last_pos > -1 and last_neg > -1 and new_pos > -1 and new_neg > -1:
            f1 = - A[new_pos] / A[last_neg]
            f2 = - A[new_neg] / A[last_pos]
            if f1>f2:
                ans = 1
                for i in range(K):
                    if i != last_neg:
                        ans = (ans*A[i]) % MOD
                ans = (ans*A[new_pos]) % MOD
            else:
                ans = 1
                for i in range(K):
                    if i != last_pos:
                        ans = (ans*A[i]) % MOD
                ans = (ans*A[new_neg]) % MOD
        elif last_pos > -1 and new_neg > -1:
            ans = 1
            for i in range(K):
                if i != last_pos:
                    ans = (ans*A[i]) % MOD
            ans = (ans*A[new_neg]) % MOD
        elif last_neg > -1 and new_pos > -1:
            ans = 1
            for i in range(K):
                if i != last_neg:
                    ans = (ans*A[i]) % MOD
            ans = (ans*A[new_pos]) % MOD
        else:
            print("something wrong")
            print(last_pos, last_neg, new_pos, new_neg)
            
        print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
mod = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 1
a.sort()
if n > k:
    if a[0] < 0:
        cnt = 0
        for x in a:
            if x < 0:
                cnt += 1
        if cnt%2 == 1:
            a.pop(cnt - 1)
            n -= 1
if k%2 == 1 and a[n - 1] < 0:
    if 0 in a:
        print(0)
        sys.exit()
    for i in range(k):
        ans = (ans * a[n - 1 - i])%mod
    print(ans%mod)
    sys.exit()
for _ in range(k - 1):
    if abs(a[n - 1]) >= abs(a[0]):
        ans = (ans * a[n - 1])
        #print(a[n-1])
        a.pop(n - 1)
    else:
        ans = (ans * a[0])
        #print(a[0])
        a.pop(0)
    if ans > 0: ans %= mod
    n -= 1
if ans < 0:
    ans = (ans * a[0])%mod
    #print('a0', a[0])
else:
    ans = (ans * a[n - 1])%mod
    #print('an', a[n-1])
print(ans%mod)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jul  5 21:33:15 2020

"""

N, K = map(int,input().split())
A = list(map(int, input().split())) 
A = sorted(A, key=abs, reverse=True)
mod = 10**9+7
ans = 1
lp = 10**6
lm = 10**6
lpflag = 0
lmflag = 0
rp = 10**6
rm = 10**6
rpflag = 0
rmflag = 0
ans1 = 0
ans2 = 0
minus = 0
for i in range(K):
    if A[i] < 0:
        minus = (minus+1)%2
    ans = ans * A[i] % mod
if not minus:
    print(ans)
else:
    for i in range(K-1,-1,-1):
        if lp < 10**6 and lm < 10**6:
            break
        if A[i] > 0 and lpflag == 0:
            lpflag = 1
            lp = i
        elif A[i] < 0 and lmflag == 0:
            lmflag = 1
            lm = i
    for i in range(K,N):
        if rp < 10**6 and rm < 10**6:
            break
        if A[i] > 0 and rpflag == 0:
            rpflag = 1
            rp = i
        elif A[i] < 0 and rmflag == 0:
            rmflag = 1
            rm = i
    if lpflag*rmflag == 1:
        ans = 1
        for i in range(K):
            if not i == lp:
                ans = ans * A[i] % mod
        ans = ans * A[rm] % mod
        ans1 = ans
    if lmflag*rpflag == 1:
        ans = 1
        for i in range(K):
            if not i == lm:
                ans = ans * A[i] % mod
        ans = ans * A[rp] % mod    
        ans2 = ans
    if lpflag*rmflag == 0 and lmflag*rpflag == 0:
        ans = 1
        for i in range(N-1,N-1-K,-1):
            ans = ans * A[i] % mod
        print(ans)
    else:
        print(max(ans1,ans2))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

N , K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
MN = 1000000007

tA = [abs(a) for a in A]
num = tA
indices = [*range(len(num))]
sorted_indices = sorted(indices, key=lambda i: -num[i])
sorted_num = [num[i] for i in sorted_indices]
#print(sorted_num)      # ==> [9, 7, 6, 5, 1]
target = [0]*N
for i,j in enumerate(sorted_indices):
    target[i] = A[j]
#print(target)

if all([i < 0 for i in target]):
    ans = 1
    for s, t in enumerate(reversed(target)):
        if s < K:
            ans = ans * t  % MN
        else:
            break

else:
    ans = 1
    for s, t in enumerate(target):
        if s < K-1:
            ans = ans * t  % MN
        else:
            if ans * t  % MN > 0:
                ans = ans * t  % MN
                break
            else:
                continue
print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7

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

alst.sort()

if k == 1:
    print(alst[-1] % MOD)
    exit()

if alst[0] >= 0:
    ans = 1
    alst.sort(reverse = True)
    for i in range(k):
        ans *= alst[i]
        ans %= MOD
    print(ans)
    exit()

if alst[-1] <= 0:
    ans = 1
    if k % 2 == 1:
        alst.sort(reverse = True)
    for i in range(k):
        ans *= alst[i]
        ans %= MOD
    print(ans)
    exit()

blst = []
for num in alst:
    try:
        blst.append([abs(num), abs(num) // num])
    except ZeroDivisionError:
        blst.append([abs(num), 0])
blst.sort(reverse = True,key = lambda x:x[0])
if blst[k - 1] == 0:
    print(0)
    exit()
    
minus = 0
last_minus = 0
last_plus = 0
ans_lst = []
for i in range(k):
    if blst[i][1] == -1:
        minus += 1
        last_minus = blst[i][0]
    else:
        last_plus = blst[i][0]
    ans_lst.append(blst[i][0])

next_minus = 0
next_plus = 0
flg_minus = False
flg_plus = False

for i in range(k, n):
    if blst[i][1] == -1 and (not flg_minus):
        next_minus = blst[i][0]
        flg_minus = True
    if blst[i][1] == 1 and (not flg_plus):
        next_plus = blst[i][0]
        flg_plus = True
    if (flg_plus and flg_minus) or blst[i][1] == 0:
        break

if minus % 2 == 0:
    ans = 1
    for num in ans_lst:
        ans *= num
        ans %= MOD
    print(ans)

else:
    minus_s = last_minus * next_minus
    plus_s = last_plus * next_plus
    ans = 1
    if minus == k:
        ans_lst.remove(last_minus)
        ans_lst.append(next_plus)
    elif minus_s == plus_s == 0:
        if last_minus == 0:
            ans_lst.remove(last_plus)
            ans_lst.append(next_minus)
        else:
            ans_lst.remove(last_minus)
            ans_lst.append(next_plus)
        
    elif minus_s > plus_s:
        ans_lst.remove(last_plus)
        ans_lst.append(next_minus)
    else:
        ans_lst.remove(last_minus)
        ans_lst.append(next_plus)
    for num in ans_lst:
        ans *= num
        ans %= MOD
    print(ans)

Submission status: Wrong Answer

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

mod = 10**9 + 7

import collections
import bisect
index = bisect.bisect_right(A, 0)

# print(A[:index])
# print(A[index:])

plus_list = collections.deque(A[index:])
minus_list = collections.deque(A[:index])


count = 0
ans = 1
while count < K:
    if K - count == 1:
        ans *= plus_list.pop() % mod
        count += 1
    else:
        if not plus_list:
            if ans > 0 and (K - count) % 2 == 0:
                for i in range(K - count):
                    ans *= minus_list.popleft() % mod
                    count += 1
            else:
                for i in range(K - count):
                    ans *= minus_list.pop() % mod
                    count += 1
            continue

        if len(minus_list) < 2:
            for i in range(K - count):
                ans *= plus_list.pop() % mod
                count += 1
            continue

        if plus_list[-1] >= minus_list[0] * minus_list[1]:
            ans *= plus_list.pop() % mod
            count += 1
        else:
            ans *= minus_list.popleft() * minus_list.popleft() % mod
            count += 2
print(ans % mod)

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
    for i in range(k):
        ans *= -li[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-1):
        if li[i][1] > 0:
            Plus = li[i][0]
            P = i
            P1 = False
            break
    for i in range(n-k, n-1):
        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
            ans1 *= li[i][0]
            ans1 %= mod
        ans2 *= li[p][0]
        ans2 %= mod
    if p1 or P1 or M1 or m1:
        print(max(ans1, ans2))
    else:
        ans = 1
        for i in range(k):
            ans *= -li[i][0]
            ans %= mod
        print(ans)