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:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    plus = [A[i] for i in range(N) if A[i] >= 0]
    minus = [A[i] for i in range(N) if A[i] < 0]

    ans = 1

    id = 0
    id2 = 0
    P = len(plus)
    M = len(minus)
    plus.sort(reverse=True)

    mod = 10**9 + 7

    if P == 0:
        if K % 2 == 0:
            minus.sort()
            for i in range(K):
                ans *= minus[i]
                ans %= mod
        else:
            minus.sort(reverse=True)
            for i in range(K):
                ans *= minus[i]
                ans %= mod

    elif M == 0:
        for i in range(K):
            ans *= plus[i]
            ans %= mod
    elif K == 1:
        ans = plus[0]
    elif K == N:
        for x in A:
            ans *= x
            ans %= mod
    else:

        p = P // 2
        m = M // 2
        if K > (p+m)*2 and (K % 2 == 0 or (K % 2 == 1 and P % 2 == 0)):  # 絶対値が小さい方から貪欲
            A.sort(key=lambda x: abs(x))
            for i in range(K):
                ans *= A[i]
                ans %= mod

        else:  # 絶対値が大きい方から貪欲

            minus.sort()
            pp = [plus[i*2]*plus[i*2+1] for i in range(P // 2)]
            mm = [minus[i*2] * minus[i*2+1] for i in range(M//2)]

            id = 0
            id2 = 0

            pp.sort(reverse=True)
            mm.sort(reverse=True)
            pp.append(1)
            mm.append(1)
            for i in range((K // 2) - 1):
                if id == p - 1:
                    ans *= mm[id2]
                    id2 += 1
                elif id2 == m:
                    ans *= pp[id]
                    id += 1
                elif pp[id] >= mm[id2]:
                    ans *= pp[id]
                    id += 1
                else:
                    ans *= mm[id2]
                    id2 += 1

                ans %= mod

            if K % 2 == 1:
                if id >= p-1:
                    ans *= mm[id2]
                    ans *= plus[id*2]
                else:
                    if id2 < m - 1 and pp[id] >= mm[id2]:
                        ans *= pp[id]
                        id += 1
                    else:
                        ans *= mm[id2]
                    ans *= plus[id*2]
            else:
                if id >= p:
                    ans *= mm[id2]
                elif id2 >= m:
                    ans *= pp[id]
                elif pp[id] >= mm[id2]:
                    ans *= pp[id]
                else:
                    ans *= mm[id2]

    print(ans % mod)


main()

Submission status: Wrong Answer

Solution code:
def maxProductSubarrayOfSizeK(A, n, k): 
  
    MOD = 10**9+7
    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] 
            product %= MOD
        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 
            product %= MOD
            i += 2
          
        else : 
            product *= right_product 
            product %= MOD
            j -= 2
  
    return product

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

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
mod = 10**9+7
n, k = map(int, input().split())
a = [int(x) for x in input().split()]

pl = []
mn = []
zr = []

tmp = 1
cnt = 0

for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mn.append(-x)
    else:
        zr.append(x)

pl = sorted(pl, reverse=True)
mn = sorted(mn, reverse=True)

ans = 0

if len(mn) >= k and k % 2:
    tmp = 1
    for i in range(1, k+1):
        tmp *= mn[-i]
        tmp %= mod
    ans = -tmp

if len(pl) == 0 and len(mn) >= k:
    tmp = 1
    for i in range(1, k+1):
        tmp *= mn[-i]
        tmp %= mod
    ans = -tmp
    if len(zr) > 0:
        print(0)
    else:
        print(ans % mod)
    exit()

if len(zr) > 0:
    ans = max(0, ans)

pl_cum = [1]
for i, x in enumerate(pl):
    pl_cum.append(pl_cum[-1]*x % mod)

mn_cum = [1]
for i, x in enumerate(mn):
    mn_cum.append(mn_cum[-1]*x % mod)


for p in range(0, k+1, 2):
    if len(mn) < p:
        break
    first = False
    if len(pl) >= k-p:
        first = True
        pl_ind = k-p
        mn_ind = p
        break

if not first:
    print(ans % mod)
    exit()

while pl_ind-2 > -1 and mn_ind+1 < len(mn):
    if pl[pl_ind-1]*pl[pl_ind-2] <= mn[mn_ind]*mn[mn_ind+1]:
        pl_ind -= 2
        mn_ind += 2
    else:
        break

if pl_ind < 0:
    ans = mn_cum[mn_ind]
else:
    ans = pl_cum[pl_ind]*mn_cum[mn_ind]

print(ans % mod)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
#import numba

def run():
    N, K = list(map(int, input().split()))
    A = list(map(int, sysread().split()))
    mod = 10 ** 9 + 7
    INF = mod

    plus = [a for a in A if a >= 0]
    minus = [-a for a in A if a < 0]

    plus = sorted(plus, reverse=True)
    minus = sorted(minus, reverse=True)

    P, M  = [1], [1]
    for p in plus:
        P.append((P[-1] * p) % mod)
    for i, m in enumerate(minus):
        M.append(((M[-1] * (-m)) % mod))
    #print(P, M)


    max_ans = -1
    for i in range(0, K+1, 2):
        if i >= len(M) or K - i >= len(P):continue
        ans = M[i] * P[K-i] % mod
        if max_ans < ans:
            max_ans = ans
        #else:
        #    break

    if max_ans == -1:
        P, M = [1], [1]
        for p in plus[::-1]:
            P.append((P[-1] * p) % mod)
        for m in minus[::-1]:
            M.append(((M[-1] * (-m)) % mod))
        #print(P, M)

        for i in range(1, K + 1, 2):
            #print(i)
            if i >= len(M) or K - i >= len(P): continue
            ans = (M[i] * P[K - i]) % mod
            #print(ans)
            if max_ans < ans:
                max_ans = ans

    print(max_ans)






if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
def LI():return list(map(int,input().split()))
def I(): return int(input())
MOD=10**9+7

n,k=LI()
a=LI()
if k==1:
    a.sort()
    print(a[-1]%MOD)
    exit()
if n==k:
    ans=1
    for i in range(k):
        ans=ans*a[i]%MOD
    print(ans)
    exit()
b=[]    
for q in a:
    b.append(q%MOD)
b.sort(reverse=True)

ans=1
for i in range(k):
    ans=ans*b[i]%MOD
print(ans)

Submission status: Wrong Answer

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

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

mod = 10 ** 9 + 7

A_abs = sorted(A, key=lambda x: abs(x))

if K >= 3:
    ans = 1
    for a in A_abs[:K-2]:
        ans *= a
        ans %= mod

    # ++ or --
    if ans > 0:
        A_rest_abs = A_abs[K-2:]
        A_rest = sorted(A_abs)
        ans *= max(A_rest[-2] * A_rest[-1], A_rest[0] * A_rest[1])
        ans %= mod
    # +-
    else:
        A_rest_abs = A_abs[K-2:]
        A_rest = sorted(A_abs)
        ans *= A_rest[-1] * A_rest[0]
        ans %= mod

elif K == 2:
    A_rest = sorted(A_abs)
    ans = max(A_rest[-2] * A_rest[-1], A_rest[0] * A_rest[1])
    ans %= mod

else:
    A_rest = sorted(A_abs)
    ans = A_rest[-1]


print(ans)

Submission status: Wrong Answer

Solution code:
import math
from numba import jit
x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a=input()
al=[int(i) for i in a.split()]
al.sort()
plus=sum([1 for x in al if x>0])
minus=sum([1 for x in al if x<0])
zero=n-plus-minus
f=0
if n==minus and round(k/2)-k/2!=0:
    f=1
if zero==0 and round(minus/2)-minus/2!=0 and n==k:
    f=1
a=1
if f==0:
    @jit
    def aaa(al,k):
        a=1
        for i in range(math.floor(k/2)):
            a1=al[0]*al[1]
            a2=al[-1]*al[-2]
            if a1>=a2:
                a*=a1
                del al[0]
                del al[0]
            else:
                a*=a2
                del al[-1]
                del al[-1]
            a=a%(10**9+7)
        if math.floor(k/2)-k/2!=0:
                a*=max(al)
        return(a%(10**9+7))
    print(aaa(al,k))
else:
    def checkio(al):
        return sorted(al, key=abs)
    al=checkio(al)
    for i in range(k):
        a*=al[i]
        a=a%(10**9+7)
    print(a)

Submission status: Wrong Answer

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

A.sort(reverse=True)

mod=(10**9+7)
p=1
t=0
if k<n:
    for i in range(k//2):
        if A[k-1-2*i]*A[k-1-2*i-1]<A[-2*i-1]*A[-2*i-2]:
            t+=1


for i in range(k-2*t):
    p=p*A[i]%mod
for i in range(2*t):
    p=p*A[-i-1]%mod


print(p)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=sorted(a)[::-1]
c = []
x = 1
if k % 2 == 0:
    for i in b:
        if i < 0:
            c.append(i * -1)
        else:
            c.append(i)
    c = sorted(c)[::-1]
    for i in range(k):
        x *= c[i]
else:
    for i in range(k):
        x *= b[i]
print(x % 1000000007)

Submission status: Wrong Answer

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(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
    exit()


A_abs = [abs(a) for a in A]
A_is_negative = [a < 0 for a in A]

# A_abs の大きい順にソート
A_abs, A_is_negative, A = zip(*sorted(zip(A_abs, A_is_negative, A), key=lambda x: x[0], reverse=True))

ans = 1
ans_is_negative = 0

for i in range(K-1):
    ans *= A[i]
    ans %= MOD
    if A_is_negative[i]:
        # A_sign が False なら A は負なので ans_is_negative を反転
        ans_is_negative = 1 - ans_is_negative
        last_negative = i

# 最後の 1 つの判定
if ans_is_negative and A_is_negative[K-1]:
    # 現時点での ans が - で 次が - なら
    ans *= A[K-1]
    ans %= MOD
    print(ans)
elif ans_is_negative and not A_is_negative[K-1]:
    # 現時点での ans が - で 次が + なら
    # 基本的に 次の A_is_negative を探す
    cand1 = 1
    cand2 = 1
    cand_times_count = 0
    negative_found = 0
    for i in range(K, N):
        if not negative_found and A_is_negative[i]:
            # 次の A_is_negative があったとき、これが候補1
            cand1 *= A[i]
            negative_found = 1
        else:
            # 候補 2 として、直前の negative を取り除き positive を 2 つ見つける
            if cand_times_count < 2:
                cand2 *= A[i]
                cand_times_count += 1
    if negative_found:
        tar = A[last_negative]
        tar_inv = pow(tar, MOD-2, MOD)
        if cand1*tar > cand2:
            ans *= cand1
        else:
            ans *= tar_inv * cand2
        ans %= MOD
        print(ans)
    else:
        # 最後まで見つからない場合
        # negative は必ず以前にあるので、直前の negative まで戻って取り除き、 positive を大きい順に 2 つ見つける
        tar = A[last_negative]
        tar_inv = pow(tar, MOD-2, MOD)
        ans *= tar_inv * A[K-1] * A[K]
        ans %= MOD
        print(ans)
elif not ans_is_negative and A_is_negative[K-1]:
    # 現時点での ans が + で 次が - なら
    # 基本的に 次の not A_is_negative を探す
    for i in range(K, N):
        if not A_is_negative[i]:
            ans *= A[K-1]
            ans %= MOD
            print(ans)
            exit()
    # 最後まで見つからない場合
    # どうがんばっても negative を偶数個にはできないのであきらめ、小さいほうから K こ掛けて答えとする
    ans = 1
    for i in range(1, K+1):
        ans *= A[-i]
        ans %= MOD
    print(ans)
else:
    # 現時点での ans も + で 次の要素も + なら
    ans *= A[K-1]
    ans %= MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
 
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
q=[]
for i in range(n):
  if arr[i]>0:
    heapq.heappush(q,(-arr[i],1))
  elif arr[i]<0:
    heapq.heappush(q,(arr[i],-1))
  else:
    heapq.heappush(q,(0,0))
pick=[]
prev=0
cnt=0
for i in range(k):
  tmp,flag=heapq.heappop(q)
  tmp*=-1
  if flag==0:
    print(0)
    exit()
  if flag==1:
    pick.append(tmp)
  if flag==-1:
    if cnt==0:
      prev=tmp
      cnt+=1
    else:
      cnt=0
      pick.append(prev)
      pick.append(tmp)
if cnt==0:
  ans=1
  for i in range(k):
    ans*=pick[i]
    ans%=mod
  print(ans%mod)
else:
  cand_plus=0
  cand_minus=0
  while len(q)!=0:
    tmp,flag=heapq.heappop(q)
    tmp*=-1
    if flag==1 and cand_plus==0:
      cand_plus=tmp
    if flag==-1 and cand_minus==0:
      cand_minus=tmp
  if k%2==1 and cand_plus==0:
    if arr.count(0)!=0:
      print(0)
      exit()
    else:
      q=[]
      for i in range(n):
        heapq.heappush(q,abs(arr[i]))
      ans=1
      for _ in range(k):
        ans*=heapq.heappop(q)
        ans%=mod
      print((-ans)%mod)
  else:
    if pick[-1]*cand_plus>=prev*cand_minus:
      pick.append(cand_plus)
    else:
      pick=pick[:-1]
      pick.append(prev)
      pick.append(cand_minus)
    ans=1
    for i in range(k):
      ans*=pick[i]
      ans%=mod
    print(ans%mod)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

mod = int(10e8+7)

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

a_ = np.abs(a)
isN = (a!=a_).astype(int)

a = a[np.argsort(a_)[::-1]]
isN = isN[np.argsort(a_)[::-1]]
a_ = np.sort(a_)[::-1]

numN = np.sum(isN)
numP = n-numN

if k==1:
    print(np.max(a))
    sys.exit()

if np.sum(isN[:k])%2==0:
    ans = 1
    for i in range(k):
        ans *= a_[i]
        ans %= mod
    print(int(ans))
    sys.exit()

if not numP:
    ans = 1
    for i in range(1, k+1)[::-1]:
        ans *= -a_[-i]
        ans %= mod

    print(int(ans))
    sys.exit()

maxN = 0
maxP = 0

for i in range(k, n):
    if isN[i]:
        maxN = i
        break

for i in range(k, n):
    if not isN[i]:
        maxP = i
        break

minN = n
minP = n

for i in range(k)[::-1]:
    if isN[i]:
        minN = i
        break

for i in range(k)[::-1]:
    if not isN[i]:
        minP = i
        break

ans_1 = 1

for i in range(k):
    if i == minP:
        if maxN:
            ans_1 *= a_[maxN]
            ans_1 %= mod
        continue

    ans_1 *= a_[i]
    ans_1 %= mod

ans_2 = 1

for i in range(k):
    if i == minN:
        if maxP:
            ans_2 *= a_[maxP]
            ans_2 %= mod
        continue

    ans_2 *= a_[i]
    ans_2 %= mod

print(int(max(ans_1, ans_2)))

Submission status: Wrong Answer

Solution code:

def maxProductSubarrayOfSizeK(A, n, k): 

	# sorting given input array 
	A.sort() 

	# variable to store final product of 
	# all element of sub-sequence of size k 
	product = 1

	# CASE I 
	# If max element is 0 and 
	# k is odd then max product will be 0 
	if (A[n - 1] == 0 and (k & 1)): 
		return 0

	# CASE II 
	# If all elements are negative and 
	# k is odd then max product will be 
	# product of rightmost-subarray of size k 
	if (A[n - 1] <= 0 and (k & 1)) : 
		for i in range(n - 1, n - k + 1, -1): 
			product *= A[i] 
		return product 

	# else 
	# i is current left pointer index 
	i = 0

	# j is current right pointer index 
	j = n - 1


	if (k & 1): 
		product *= A[j] 
		j-= 1
		k-=1

	k >>= 1

	for itr in range( k) : 

		# product from left pointers 
		left_product = A[i] * A[i + 1] 

		# product from right pointers 
		right_product = A[j] * A[j - 1] 

		if (left_product > right_product) : 
			product *= left_product 
			i += 2
		
		else : 
			product *= right_product 
			j -= 2

	# Finally return product 
	return product 

# Driver Code 
if __name__ == "__main__": 
	
	n,k = map(int,input().split())
	l = list(map(int,input().split()))
	ans = maxProductSubarrayOfSizeK(l, n, k)
	ans = ans%1000000007
	print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
    from bisect import bisect_left
    n,k=map(int,input().split())
    a=sorted(list(map(int,input().split())))
    m=bisect_left(a,0)
    MOD=10**9+7
    if m==0:
        ans=1
        for i in a[-k:]:
            ans=(ans*i)%MOD
    elif m==n:
        ans=1
        if k%2==0:
            for i in a[:k]:
                ans=(ans*i)%MOD
        else:
            for i in a[-k:]:
                ans=(ans*i)%MOD
    else:
        cal=1
        i=(m//2)*2
        for j in a[:i]:
            cal=(cal*j)%MOD
        if k-i>0:
            for j in a[-(k-i):]:
                cal=(cal*j)%MOD
        ans=cal
        for i in range((m//2)*2-2,-2,-2):
            if k-i>n-m:
                break
            for j in a[i-2:i]:
                cal=(cal*pow(j,MOD-2,MOD))%MOD
            if k-i>=0:
                if -(k-i)+2==0:
                    for j in a[-(k-i):]:
                        cal=(cal*j)%MOD
                else:
                    for j in a[-(k-i):-(k-i)+2]:
                        cal=(cal*j)%MOD
            ans=max(ans,cal)
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    a = LI()
    a.sort(key = lambda x:-abs(x))
    c = 0
    p = 0
    m = 0
    for i in a:
        if i != 0:
            c += 1
            if i > 0:
                p += 1
            if i < 0:
                m += 1
    if c < k:
        print(0)
        return
    f = 1
    for x in range(p+1):
        y = k-x
        if y < 0 or y > m:
            continue
        if not y&1:
            f = 0
            break
    if f:
        a.sort(key = lambda x:abs(x))
        ans = 1
        for i in a[:k]:
            ans *= i
            ans %= mod
        print(ans)
        return
    minus = []
    a.sort()
    s = 1
    s2 = 1
    k1 = 0
    k2 = 0
    ind = [None]*2
    ind2 = [None]*2
    for j in range(n):
        i = a[j]
        if i != 0:
            if i < 0:
                ind[k1] = j
                k1 ^= 1
                s *= -i
                if not k1:
                    minus.append((s,[i for i in ind]))
                    s = 1
            else:
                ind2[k2] = j
                k2 ^= 1
                s2 *= i
                if not k2:
                    minus.append((s2,[i for i in ind2]))
                    s2 = 1
    ans = 1
    x = k>>1
    minus.sort(reverse = True)
    f = [1]*n
    for i in range(x):
        m,indi = minus[i]
        for j in indi:
            f[j] = 0
        ans *= m
        ans %= mod
    if (k-2*x)&1:
        b = [a[i] for i in range(n) if f[i]]
        p = max(b)
        ans *= p
    print(ans%mod)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

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

ans = 1
mod = 10 ** 9 + 7

minus_cnt = 0
for a in A:
    if a < 0:
        minus_cnt += 1

if K == 1:
    print(max(A))
elif K == N:
    for a in A:
        ans *= abs(a)
        ans %= mod
    if minus_cnt % 2 == 1:
        ans *= (-1)
    print(ans % mod)
else:
    minus_cnt = 0
    new_A = []
    select_ls = []

    for a in A:
        new_A.append([abs(a), 0 if a >= 0 else -1])
    new_A.sort(reverse=True)

    for i in range(K):
        select_ls.append(new_A[i])
        minus_cnt += new_A[i][1]

    if minus_cnt % 2 == 0:
        for s in select_ls:
            ans *= s[0]
            ans %= mod
        print(ans)
    else:
        ok = False
        for i in range(K, N):
            if new_A[i][1] == 0:
                ok = True
                ans *= new_A[i][0]
                select_ls.sort()
                skip = False
                for j in range(len(select_ls)):
                    if select_ls[j][1] == -1:
                        if skip:
                            ans *= select_ls[j][0]
                        else:
                            skip = True
                            continue
                    else:
                        ans *= select_ls[j][0]
                    ans %= mod
            break
        if not ok:
            if 0 in A:
                print(0)
                exit()
            new_A.sort()
            for i in range(K):
                ans *= new_A[i][0]
                ans %= mod
            ans *= (-1)
        print(ans % mod)

Submission status: Wrong Answer

Solution code:
import sys, bisect


if(__name__ == "__main__"):

    N, K = map( int, input().strip().split() )
    divisor = 10**9+7

    list_a = list( map(int, input().strip().split()) )

    """
    left, right側の2項の積で大きい方を選択
    選べるのが残り1項ならright側を選択
    """
    multiplies = 1

    if(N==K):
        for i in range(N):
            multiplies = multiplies * list_a[i] % divisor
        print(multiplies)
    else:
        list_a.sort()
        N_negative_numbers = bisect.bisect_left(list_a, 0)
        N_select_negatives = K + N_negative_numbers -N
        flag_overzero = True
        if(N_select_negatives > 0 and N_select_negatives % 2 != 0):
            flag_overzero = False
        if(flag_overzero == True):
            left = 0
            right = N-1

            multiply_right = list_a[right] * list_a[right-1]
            flag_left = True
            while(K>0):
                if(K>1):
                    K -= 2
                    if(flag_left==True):
                        multiply_left = list_a[left] * list_a[left+1]
                    else:
                        multiply_right = list_a[right] * list_a[right-1]

                    if(multiply_left > multiply_right):

                        multiply_left %= divisor
                        multiplies = multiplies * multiply_left % divisor
                        left += 2
                        flag_left=True

                    else:
                        multiply_right %= divisor
                        multiplies = multiplies * multiply_right % divisor
                        right -= 2
                        flag_left=False

                else:
                    multiplies = multiplies * list_a[right] % divisor
                    K =0
            print(multiplies)
        else:
            list_a = [ abs(list_a[i]) for i in range(N)]
            list_a.sort()
            for i in range(K):
                multiplies = multiplies * list_a[i] % divisor
            multiplies = -multiplies +divisor

            print(multiplies)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

mod = 10 ** 9 + 7

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

if N == K:
    ans = 1
    for i in range(N):
        ans *= A[i]
        ans %= mod
    print(ans)
    sys.exit()

A = np.array(A)

plus = A[A>0]
minus = A[A<0]
zero = A[A==0]

if len(zero) > N - K:
    print(0)
    sys.exit()

if len(plus) == 0:
    if K % 2 == 0:
        minus = np.sort(minus)
        ans = 1
        for i in range(K):
            ans *= minus[i]
            ans %= mod
        print(ans)
    else:
        print(0)
    sys.exit()

plus = np.sort(plus)[::-1]
minus *= -1
minus = np.sort(minus)[::-1]

if K % 2 == 1:
    ans = plus[0]
    K -= 1
    p = (len(plus)-1) // 2
    m = len(minus) // 2
    
    n_p = [plus[2*i+1] * plus[2*i+2] for i in range(p)]
    n_m = [minus[2*i] * minus[2*i+1] for i in range(m)]
else:
    ans = 1
    p = len(plus) // 2
    m = len(minus) // 2
    
    n_p = [plus[2*i] * plus[2*i+1] for i in range(p)]
    n_m = [minus[2*i] * minus[2*i+1] for i in range(m)]

K //= 2

p_index = 0
m_index = 0
for i in range(K):
    if p_index == len(n_p):
        ans *= n_m[m_index]
        ans %= mod
        m_index += 1
    elif m_index == len(n_m):
        ans *= n_p[p_index]
        ans %= mod
        p_index += 1
    else:
        if n_p[p_index] > n_m[m_index]:
            ans *= n_p[p_index]
            ans %= mod
            p_index += 1
        else:
            ans *= n_m[m_index]
            ans %= mod
            m_index += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import operator

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

pos = [a for a in A if a > 0]
neg = [a for a in A if a < 0]
LP = len(pos)
LN = len(neg)
zer = N - LP - LN

MOD = 10 ** 9 + 7


def solve():
    global N, K, pos, neg, LP, LN, zer, MOD
    # ZERO
    if LP + LN < K:
        return 0

    # 全部使い切るとき
    if LP + LN == K and LP != 0:
        ans = 1
        for n in pos:
            ans *= n
            ans %= MOD
        for n in neg:
            ans *= n
            ans %= MOD

        return ans

    # negative にしかならない
    # 正がなくて、負の数を奇数回使う
    if LP == 0 and K % 2 == 1:
        if zer > 0:
            return 0
        else:
            neg.sort(reverse=True)
            ans = 1
            for n in neg:
                if K == 0:
                    break
                ans *= n
                ans %= MOD
                K -= 1

            return ans

    # positiveにできるなら
    # 2個ずつ比較
    pos.sort()
    neg.sort(reverse=True)

    ans = 1

    while K > 0 and len(neg) >= 2 and len(pos) >= 2:
        # 2個を比べる
        p = pos[-1] * pos[-2]
        n = neg[-1] * neg[-2]

        if n >= p:
            neg.pop()
            neg.pop()

            ans *= n
            ans %= MOD
            K -= 2
        else:
            ans *= pos[-1]
            ans %= MOD
            pos.pop()

            K -= 1

    # あとK個使う必要がある
    if K > 0:
        # negが1個以下
        if len(neg) <= 1:
            # posから取る
            for p in pos:
                ans *= p
                ans %= MOD
                K -= 1
                if K == 0:
                    break
        # posが1個以下
        else:
            while K >= 2:
                ans *= neg[-1]
                ans %= MOD
                ans *= neg[-2]
                ans %= MOD
                K -= 2
                neg.pop()
                neg.pop()

            if K == 1:
                ans *= pos[-1]
                ans %= MOD

    return ans


print(solve())

Submission status: Wrong Answer

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

    plus = [A[i] for i in range(N) if A[i] >= 0]
    minus = [A[i] for i in range(N) if A[i] < 0]

    ans = 1

    id = 0
    id2 = 0
    P = len(plus)
    M = len(minus)
    plus.sort(reverse=True)

    mod = 10**9 + 7

    if P == 0:
        if K % 2 == 0:
            minus.sort()
            for i in range(K):
                ans *= minus[i]
                ans %= mod
        else:
            minus.sort(reverse=True)
            for i in range(K):
                ans *= minus[i]
                ans %= mod

    elif M == 0:
        for i in range(K):
            ans *= plus[i]
            ans %= mod
    elif K == 1:
        ans = plus[0]

    else:

        p = P // 2
        m = M // 2
        if K > (p+m)*2 and (K % 2 == 0 or (K % 2 == 1 and P % 2 == 0)):  # 絶対値が小さい方から貪欲
            A.sort(key=lambda x: abs(x))
            for i in range(K):
                ans *= A[i]
                ans %= mod

        else:  # 絶対値が大きい方から貪欲

            minus.sort()
            pp = [plus[i*2]*plus[i*2+1] for i in range(P // 2)]
            mm = [minus[i*2] * minus[i*2+1] for i in range(M//2)]

            id = 0
            id2 = 0

            pp.sort(reverse=True)
            mm.sort(reverse=True)
            pp.append(1)
            mm.append(1)
            for i in range((K // 2) - 1):
                if id == p - 1:
                    ans *= mm[id2]
                    id2 += 1
                elif id2 == m:
                    ans *= pp[id]
                    id += 1
                elif pp[id] >= mm[id2]:
                    ans *= pp[id]
                    id += 1
                else:
                    ans *= mm[id2]
                    id2 += 1

                ans %= mod

            if K % 2 == 1:
                if id >= p-1:
                    ans *= mm[id2]
                    ans *= plus[id*2]
                else:
                    if id2 < m - 1 and pp[id] >= mm[id2]:
                        ans *= pp[id]
                        id += 1
                    else:
                        ans *= mm[id2]
                    ans *= plus[id*2]
            else:
                if id >= p:
                    ans *= mm[id2]
                elif id2 >= m:
                    ans *= pp[id]
                elif pp[id] >= mm[id2]:
                    ans *= pp[id]
                else:
                    ans *= mm[id2]

    print(ans % mod)


main()