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:
from bisect import bisect_left
N,K=map(int, input().split())
A=list(map(int, input().split()))
p=10**9+7
A=sorted(A)
thresh=bisect_left(A,0)
minus=A[:thresh]
plus=A[thresh:][::-1]

#print(plus, minus)
if len(plus)==0:
    ans=1
    if K%2!=0:
        minus=minus[::-1]
        for i in range(K):
            ans*=minus[i]
            ans%=p
    else:
        for i in range(K):
            ans*=minus[i]
            ans%=p
    print(ans)
    exit()

if len(minus)==0:
    ans=1
    for i in range(K):
        ans*=plus[i]
        ans%=p
    print(ans)
    exit()

midx=0
pidx=0
ans=1
while K>0 and (0<=midx<len(minus) or 0<=pidx<len(plus)):
    if 0<=midx<len(minus)-1:
        nexmin=minus[midx]*minus[midx+1]
    elif midx==len(minus)-1:
        nexmin=minus[midx]
    else:
        nexmin=-1


    if 0<=pidx<len(plus)-1:
        nexplus=plus[pidx]*plus[pidx+1]
    elif pidx==len(plus)-1:
        nexplus=plus[pidx]
    else:
        nexplus=-float("INF")

    if nexmin>nexplus and K>=2:
        ans*=nexmin
        ans%=p
        midx+=2
        K-=2
    else:
        ans*=nexplus
        ans%=p
        pidx+=1
        K-=1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict

# available on Google, not available on Codeforces
# import numpy as np
# import scipy


def solve(lst,k):  # fix inputs here
    console("----- solving ------")

    MOD = 10**9 + 7

    lst = lst[:len(lst)//2] + lst[len(lst)//2:]
    lst = sorted(lst, key=lambda x: abs(x))[::-1]
    sign = [0 if x == 0 else x//abs(x) for x in lst]

    console(lst)
    console(sign)

    # no choice negative
    if all([x == -1 for x in sign]) and k%2 == 1:
        res = 1
        for i in lst[::-1][:k]:
            res = (res*i)%MOD 
        return res

    # no choice take all
    if k == len(lst):
        res = 1
        for i in lst:
            res = (res*i)%MOD 
        return res

    # not enough nonzeros
    if lst[k-1] == 0:
        return 0

    # if hangover
    if abs(lst[k]) == abs(lst[k-1]):
        val = abs(lst[k])
        c = Counter(lst)
        if c[val] == 0 or c[-val] == 0:   # no choice anyway
            pass
        else:
            initial_sign = 1
            for i in sign[:k]:
                initial_sign = initial_sign*i
            if initial_sign == 1:
                res = 1
            else:
                res = -1
            for i in lst[:k]:
                res = (res*i)%MOD
            return res


    pos = max(lst[k-1:])
    neg = min(lst[k-1:])

    initial_sign = 1
    for i in sign[:k-1]:
        initial_sign = initial_sign*i

    if initial_sign == 1:
        res = pos
        for i in lst[:k-1]:
            res = (res*i)%MOD
        return res

    if initial_sign == -1:
        res = neg
        for i in lst[:k-1]:
            res = (res*i)%MOD
        return res

    # return a string (i.e. not a list or matrix)
    return 0


def console(*args):  # the judge will not read these print statement
    print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return


for case_num in [1]:
    # read line as a string
    # strr = input()

    # read line as an integer
    # k = int(input())
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
    _,k = list(map(int,input().split()))
    lst = list(map(int,input().split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    # grid = []
    # for _ in range(nrows):
    #     grid.append(list(map(int,input().split())))

    res = solve(lst,k)  # please change
    
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
    print(res)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=sorted(list(map(int,input().split())))
t=1
for i in range(n):
    if(l[i]>=0):
       l[i]=l[i]%(1000000007)
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
  
    # CASE III 
    # if k is odd and rightmost element in 
    # sorted array is positive then it 
    # must come in subsequence 
    # Multiplying A[j] with product and 
    # correspondingly changing j 
    if (k & 1): 
        product *= A[j] 
        j-= 1
        k-=1
  
    # CASE IV 
    # Now k is even. So, Now we deal with pairs 
    # Each time a pair is multiplied to product 
    # ie.. two elements are added to subsequence  
    # each time. Effectively k becomes half 
    # Hence, k >>= 1 means k /= 2 
    k >>= 1
  
    # Now finding k corresponding pairs to get 
    # maximum possible value of product 
    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] 
  
        # Taking the max product from two  
        # choices. Correspondingly changing 
        # the pointer's position 
        if (left_product > right_product) : 
            product *= left_product 
            i += 2
          
        else : 
            product *= right_product 
            j -= 2
  
    # Finally return product 
    return product 
k=maxProductSubarrayOfSizeK(l,n,k)
print(k%1000000007)

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

Submission status: Wrong Answer

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

ans = 1
sei = 0
for i in a:
    if i>0:
        sei += 1

if max(0,k-sei)%2==0:
    b = sorted(a, key=lambda x: abs(x),reverse=True)
    cnt = 0
    sei = []
    hu = []
    for i in b:
        if i>0:
            sei.append(i)
        else:
            hu.append(i)
    hu_seki = []
    for i in range(len(hu)//2):
        hu_seki.append(hu[i*2]*hu[i*2+1]%mod)

    for i in range(min(k,len(sei))):
        ans = ans*sei[i]%mod
    index = 0
    if k>len(sei):
        for i in range(min(len(hu_seki),(k-len(sei))//2)):
            ans = ans*hu_seki[i]%mod
            index += 1
    sei.sort()
    while index<len(hu_seki) and len(sei)-k+index*2+1<len(sei):
        if sei[len(sei)-k+index*2]*sei[len(sei)-k+index*2+1]<hu_seki[index]:
            ans = ans//(sei[index*2]*sei[index*2+1])
            ans = ans*hu_seki[index]%mod
            index += 1
        else:
            break
else:
    b = sorted(a, key=lambda x: abs(x))
    for i in range(k):
        ans *= b[i]
        ans %= mod
print(ans%mod)

Submission status: Wrong Answer

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

result = 1
if a[0] > 0:
    for i in range(k):
        result = result * a[n - i - 1] % modular
elif a[-1] < 0:
    if k % 2 == 0:
        for i in range(k):
            result = result * a[i] % modular
    else:
        for i in range(k):
            result = result * a[n - i - 1] % modular
else:
    pass
print(result)

Submission status: Wrong Answer

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]


def solve(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 

M = 10**9+7
n,k = ip()
x = ip()
if k == 1:
    print(max(x)%M)
    exit()
if k&1:
    k += 2
print(solve(x,n,k)%M)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, K = LI()
A = LI()

def abssort(A):
    return sorted(A, key = lambda x:abs(x), reverse= True)

tmps = []
A_abs = abssort(A)
for i in range(K):
    # tmp *= A_abs[i]
    tmps.append(A_abs[i])

cnt = 0
for i in range(K):
    if tmps[i] < 0:
        cnt += 1
if cnt % 2 == 0:
    ans = 1
    for i in range(K):
        ans *= tmps[i]
        ans = ans % mod
    print(ans)
    sys.exit()
else:
    tmp_1 = copy.deepcopy(tmps)
    tmp_2 = copy.deepcopy(tmps)
    tmp_1.reverse()
    tmp_2.reverse()
    tmp_2_ = 0
    tmp_1_ = 0
    # -を一つ消す
    for i in range(K):
        if tmp_1[i] < 0:
            tmp_1.remove(tmp_1[i])
            break
    # + を一つたす
    for i in range(K, N):
        if A_abs[i] > 0:
            tmp_1.append(A_abs[i])
            tmp_1_ = 1
            break
    else:
        # +がなかった時
        tmp_1 = []
        tmp_1_ = -1 
        A_abs.reverse()
        for i in range(K):
            tmp_1.append(A_abs[i])

    # +を消して-を追加
    cnt = 0
    for i in range(K):
        if tmp_2[i] > 0:
            tmp_2.remove(tmp_2[i])
            cnt += 1
            break
    if cnt == 1:
        for i in range(K, N):
            if A_abs[i] < 0:
                tmp_2.append(A_abs[i])
                tmp_2_ = 1
                break
        else:
            tmp_2_ = 0
    else:
        tmp_2_ = -1
# print(tmp_1, tmp_2)



tmp_1_m = 1
tmp_2_m = 1
for i in range(K):
    tmp_1_m *= tmp_1[i]
    tmp_1_m = tmp_1_m % mod

if tmp_2_ == 0:
    pass
else:
    for i in range(K):
        tmp_2_m *= tmp_2[i]
        tmp_2_m = tmp_2_m % mod

# print(tmp_1_, tmp_2_)
if tmp_2_ == 0:
    print(tmp_1_m)
elif tmp_1_ == 1 and tmp_2_ == -1:
    print(tmp_1_m)
elif tmp_1_ == -1 and tmp_2_ == 1:
    print(tmp_2_m)
elif tmp_1_ == 1 and tmp_2_ == 1:
    for i in range(K):
        if tmp_1[i] == tmp_2[i]:
            pass
        elif abs(tmp_1[i]) > abs(tmp_2[i]):
            print(tmp_1_m)
            sys.exit()
        else:
            print(tmp_2_m)
            sys.exit()
else:
    for i in range(K):
        if tmp_1[i] == tmp_2[i]:
            pass
        elif abs(tmp_1[i]) > abs(tmp_2[i]):
            print(tmp_2_m)
            sys.exit()
        else:
            print(tmp_1_m)
            sys.exit()

Submission status: Wrong Answer

Solution code:
def hugo(k):
  h=0
  for i in k:
    if i>=0:
      h+=1
  if h==0:
    return True
  else:
    return False
n,k=map(int,input().split())
mod=10**9+7
a=list(map(int,input().split()))
s=sorted(a,key=abs)
s.reverse()
e=sorted(a)
e.reverse()
a=list(map(abs,a))
a.sort()
a.reverse()
x=1
o=0
m=1
if n==k:
  for t in e:
    x*=t
    x%=mod
  print(x)
else:
  if k%2==1 and hugo(s):
    s.reverse()
    if k>1:
      for i in s[0:k]:
        m*=i
        o+=1
        if o%2==0:
          x=(x*m)%mod
          m=1
      x*=m
      x%=mod
      print(x) 
    else:
      print(s[0]%mod)
  else:
    if k>1:
      for i in s[0:k-1]:
        if i>=0:
          x=(x*i)%mod
        else:
          m*=i
          o+=1
          if o%2==0:
            x=(x*m)%mod
            m=1
      if m<0:
        y=0
        z=1
        l=0
        for i in s[k-1:]:
          if i<0:
            y=i
            break
        for i in s[k-1:]:
          if i>=0:
            z*=i
            l+=1
            if l==2:
              break
        m*=y
        if z>=m:
          x=(x*z)%mod
        else:
          x=(x*m)%mod
      print(x)
    else:
      for i in s:
        if i>=0:
          print(i)
          break

Submission status: Wrong Answer

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

def checkio(numbers_array):
    return sorted(numbers_array, key=lambda x: abs(x))

INF = 10 ** 9 + 7

B = sorted(A)[::-1]
ans1 = 1
for i in range(K):
    if B[i] >= 0:
        ans1 *= B[i]
        ans1 %= INF
    else:
        ans1 = -INF
        break
    
ans2 = 1
C = checkio(A)[::-1]
hu = []
ind = []
for i in range(N):
    if C[i] < 0:
      hu.append(C[i])

i = 0
while(i < K):
    if C[i] >= 0:
        ans2 *= C[i]
        ans2 %= INF
    else:
        if i != K - 1 and C[i] in hu:
            ans2 *= C[i]
            del hu[0]
            if len(hu) > 0:
                ans2 *= hu[0]
                ans2 %= INF
                del hu[0]
            else:
                break
            i += 1
    i += 1
            
print(max(ans1, ans2))

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 = []  # 正を取り除く
            ans2 = []  # 負を取り除く
            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.append(a)
            n_remove = False
            for a in A[:K][::-1]:
                if a < 0 and not n_remove:
                    n_remove = True
                    continue
                ans2.append(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
            ans1.append(mul2)
            ans2.append(mul1)
            s1 = sum(abs(a) for a in ans1)
            s2 = sum(abs(a) for a in ans2)

            if mul2 == 0:
                for a in ans2:
                    ans *= a
            elif mul1 == 0:
                for a in ans1:
                    ans *= a
            else:
                if s1 < s2:
                    for a in ans2:
                        ans *= a
                elif s1 > s2:
                    for a in ans1:
                        ans *= a
                else:
                    from random import randint
                    if randint(0, 1) == 0:
                        for a in ans2:
                            ans *= a
                    else:
                        for a in ans1:
                            ans *= a
    print(int(ans) % MOD)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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



flg = 0
plus_num = 0
for i in a:
    if i>0:
        plus_num+=1
minus_num = n-plus_num


if minus_num ==1 and k==n:
    flg = 1
if minus_num >=2 and plus_num>=1 and n-plus_num%2==1 and k==n:
    flg = 1
if  minus_num >=2  and plus_num==0 and k%2==1:
    flg = 2



if flg == 1:
    ans = 1
    for i in a:
        ans*=i
        ans %= (10**9+7)
        
if flg ==2:
    abs_a = sorted(a, key=abs)
    ans = 1
    for i in range(k):
        ans*=abs_a[i]
        ans %= (10**9+7)
        ans = 1
else:
    abs_a = sorted(a, key=abs)
    abs_a.reverse()
    min_minus = 0
    ans = 1
    for i in range(k):
        if abs_a[i]>=0:
            ans*=abs_a[i]
            ans %= (10**9+7)
        else:
            ans *= abs_a[i]
            ans %= (10**9+7)
            min_minus = abs_a[i]
    if ans <0:
        ans /=min_minus
        while True:
            for i in range(k,n):
                if abs_a[i]>=0:
                    ans*=abs_a[i]
                    ans %= (10**9+7)
                    break
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, K, XS):
    "void()"

    posi = [x for x in XS if x >= 0]
    nega = [x for x in XS if x < 0]

    nega.sort(reverse=True)
    posi.sort()

    if K == N:
        # no choice
        ret = 1
        for i in range(N):
            ret *= XS[i]
            ret %= MOD
        return ret

    if not posi and K % 2:
        # negative answer
        # find smallest abs
        ret = 1
        for i in range(K):
            ret *= nega[i]
            ret %= MOD
        return ret

    ret = 1
    while K:
        # debug(": K, nega, posi", K, nega, posi)
        if K >= 2:
            if len(posi) >= 2:
                v = posi[-1] * posi[-2]
                if len(nega) >= 2:
                    w = nega[-1] * nega[-2]
                else:
                    w = -INF
                if v > w:
                    posi.pop()
                    posi.pop()
                    ret *= v
                    ret %= MOD
                else:
                    nega.pop()
                    nega.pop()
                    ret *= w
                    ret %= MOD

            else:
                w = nega[-1] * nega[-2]
                nega.pop()
                nega.pop()
                ret *= w
                ret %= MOD

            K -= 2
        else:
            if posi:
                ret *= posi[-1]
            else:
                ret *= nega[0]
            K -= 1
    return ret


def main():
    N, K = map(int, input().split())
    XS = list(map(int, input().split()))
    print(solve(N, K, XS))


T1 = """
4 2
1 2 -3 -4
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    12
    """


T2 = """
4 3
-1 -2 -3 -4
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    1000000001
    """


T3 = """
2 1
-1 1000000000
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    1000000000
    """


T4 = """
10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    999983200
    """


def _test():
    import doctest
    doctest.testmod()


T5 = """
3 2
1 1 -1
"""


def test_T5():
    """
    >>> as_input(T5)
    >>> main()
    1
    """


T6 = """
3 2
1 -1 -1
"""


def test_T6():
    """
    >>> as_input(T6)
    >>> main()
    1
    """


T7 = """
3 2
2 -1 -1
"""


def test_T7():
    """
    >>> as_input(T7)
    >>> main()
    1
    """


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, K = input_ints()
    A = input_int_list_in_line()

    Ap = []
    An = []
    Az = []
    for a in A:
        if a == 0:
            Az.append(a)
        elif a > 0:
            Ap.append(a)
        else:
            An.append(a)

    if len(An) == N and K % 2 == 1:
        An.sort(reverse=True)
        prod = 1
        for i in An[:K]:
            prod *= i

        print_ans(prod)
        exit()

    if len(Ap) == 0 and K % 2 == 1:
        print(0)
        exit()

    if N - len(Az) < K:
        print(0)
        exit()

    if N == K:
        prod = 1
        for i in A:
            prod *= i

        print_ans(prod)
        exit()

    if K == 1:
        print_ans(max(A))
        exit()

    prod = 1

    An.sort(reverse=False)

    if len(An) % 2 == 1:
        An.pop(-1)

    An2 = []

    for i in range(len(An) // 2):
        An2.append(An[i*2] * An[i*2 + 1])

    i = 0
    j = 0

    while K > 0:
        if j not in range(len(An2)):
            prod = (prod * Ap[i]) % (10**9 + 7)
            i += 1
            K -= 1
            continue

        if i not in range(len(Ap)):
            prod = (prod * An2[j]) % (10**9 + 7)
            j += 1
            K -= 2
            continue

        if K >= 2 and Ap[i] < An2[j]:
            prod = (prod * An2[j]) % (10**9 + 7)
            j += 1
            K -= 2
            continue
        else:
            prod = (prod * Ap[i]) % (10**9 + 7)
            i += 1
            K -= 1
            continue

    print_ans(prod)


def print_ans(n: int):
    print(n % (10**9 + 7))


def input_ints():
    line_list = input().split()

    if len(line_list) == 1:
        return int(line_list[0])
    else:
        return map(int, line_list)


def input_int_list_in_line():
    return list(map(int, input().split()))


def input_int_tuple_list(n: int):
    return [tuple(map(int, input().split())) for _ in range(n)]


main()

Submission status: Wrong Answer

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

p_list = []
n_list = []
z_count = 0

for A in map(int, input().split()):
	if A < 0:
		n_list.append(A)
	elif A > 0:
		p_list.append(A)
	else:
		z_count += 1

p_list.sort()
n_list.sort()

#print(p_list)
#print(n_list)

if len(p_list) + len(n_list) < K:
	print(0)
else:
	values = []
	
#	print(len(p_list) >= K ,  (K - len(p_list)) % 2 == 0 ,  ((K - len(p_list)) % 2 == 1 and len(p_list) >= 1 and K - len(p_list) + 1 <= len(n_list)))
	if len(p_list) >= K or (K - len(p_list)) % 2 == 0 or ((K - len(p_list)) % 2 == 1 and len(p_list) >= 1 and K - len(p_list) + 1 <= len(n_list)):
		p_list.reverse()
		i_p = 0
		i_n = 0
		if len(p_list) >= K:
			for i in range(K):
				values.append(p_list[i_p])
				i_p += 1
		elif (K - len(p_list)) % 2 == 0:
			for i in range(len(p_list)):
				values.append(p_list[i_p])
				i_p += 1
			while len(values) < K:
				values.append(-n_list[i_n])
				i_n += 1
		elif K - len(p_list) + 1 <= len(n_list):
			for i in range(len(p_list) - 1):
				values.append(p_list[i_p])
				i_p += 1
			while len(values) < K:
				values.append(-n_list[i_n])
				i_n += 1
		values.sort()
		values.reverse()
		i = K - 1
		while i >= 1 and i_n < len(n_list) - 1:
			if values[i] * values[i - 1] < n_list[i_n] * n_list[i_n + 1]:
				values[i] = n_list[i_n]
				values[i - 1] = n_list[i_n + 1]
				i -= 2
				i_n += 2
			else:
				break
	else:
		n_list.reverse()
		i_p = 0
		i_n = 0
		for i in range(min(len(n_list), K)):
			values.append(n_list[i_n])
			i_n += 1
		while len(values) < K:
			values.append(p_list[i_p])
			i_p += 1
	
#	print(values)
	total = 1
	for v in values:
		total = (total * v) % M
	print(total)