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:
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

import heapq
import collections

class HeapQueue:

    def __init__(self, xs, mode):
        if   mode == "min": self.xs = [ x for x in xs]
        elif mode == "max": self.xs = [-x for x in xs]
        else              : raise NotImplementedError("HeapQueue.__init__: mode should be 'min' or 'max'")
        heapq.heapify(xs)
        self.mode = mode

    def __len__(self):
        return len(self.xs)

    def pop(self):
        if   self.mode == "min": return heapq.heappop(self.xs)
        elif self.mode == "max": return heapq.heappop(self.xs) * (-1)

    def push(self, x):
        if   self.mode == "min": return heapq.heappush(self.xs,  x)
        elif self.mode == "max": return heapq.heappush(self.xs, -x)


N, K = tuple(map(int, input().strip().split()))
As = list(map(int, input().strip().split()))

D = int(1E9 + 7)
r = 1

if K == N:
    for a in As:
        r = (r * (a % D)) % D
    print(r)

elif K % 2 == 1 and all(a < 0 for a in As):
    As = HeapQueue(As, "max")
    for k in range(K):
        a = As.pop()
        r = (r * (a % D)) % D
    print(r)

else:

    k = 0

    Ps = [a for a in As if a >= 0]
    Qs = [a for a in As if a <= 0]

    Ps = HeapQueue(Ps, "max")
    Qs = HeapQueue(Qs, "min")

    while k < K:
    
        if (K - k) == 1:
            p = Ps.pop()
            r = (r * p) % D
            k += 1

        elif len(Ps) <= 1:
            q1 = Qs.pop()
            q2 = Qs.pop()
            q  = q1 * q2
            r = (r * q) % D
            k += 2

        elif len(Qs) < 2:
            p = Ps.pop()
            r = (r * p) % D
            k += 1

        else:
            p1 = Ps.pop()
            p2 = Ps.pop()
            p  = p1 * p2
            q1 = Qs.pop()
            q2 = Qs.pop()
            q  = q1 * q2
            if p > q:
                r = (r * p1) % D
                Ps.push(p2)
                Qs.push(q1)
                Qs.push(q2)
                k += 1
            else:
                r = (r * q) % D
                Ps.push(p1)
                Ps.push(p2)
                k += 2

    print(r)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker

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,lm,2):
			if i == lm-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
	
	for _ in range(k):
		if cp != -1 and cm != lm:
			if abs(mina[cm]) <= pra[cp]:
				if cp == 0:
					if (k-lp) % 2 == 0:
						cp -= 1
					else:
						
						cm += 1

				else:
					
					cp -= 1
			else:
				if cm == lm-1:
					if lm % 2 == 0:
						
						cm += 1
					else:
						
						cp -= 1


				else:
					
					cm += 1
		elif cp != -1:
			cp -= 1
		elif cm != lm:
			cm += 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: 
					cp += 1
					cm += 1
				elif 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):
		if i == cm-1:
			continue
		ans *= (mina[i] * mina[i+1]) % mod
		ans %= mod
	ii = i
	for i in range(lp-1,cp,-1):
		ans *= pra[i] % mod
		ans %= mod
	if ii == cm-1:
		ans *= mina[ii]
		ans %= mod

		
	print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

def prod(X):
    ans = 1
    for x in X:
        ans = ans * x % M
    return ans

def solve():
    # Case 1: N == K
    if N == K:
        return prod(A)

    # Case 2: ans is negative
    if all(a < 0 for a in A) and K % 2 == 1:
        return prod(sorted(A)[-K:])

    # Case 3: ans is positive
    posA = np.int64(sorted([a for a in A if a >= 0]))
    negA = np.int64(sorted([a for a in A if a < 0]))

    ans = 1
    if K % 2 == 1: # keep the largest positive
        ans = ans * posA[-1] % M
        posA = posA[:-1]
    
    # Rest
    if len(posA) % 2 == 1:
        posA = posA[1:]
    if len(negA) % 2 == 1:
        negA = negA[:-1]
    
    pos_pairs = posA[0::2] * posA[1::2]
    neg_pairs = negA[0::2] * negA[1::2]
    pairs = np.concatenate([pos_pairs, neg_pairs], axis=0)
    pairs = np.sort(pairs)[-(K//2):].tolist()
    ans = ans * prod(pairs) % M
    return ans

print(solve())

Submission status: Wrong Answer

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

P = []
M = []
zero = 0
for a in A:
    if a > 0:
        P.append(a)
    elif a < 0:
        M.append(a)
    else:
        zero += 1

# 0 を選ぶしかない場合
if len(P) + len(M) < K:
    print(0)
    exit()
elif len(P) + len(M) == K:
    ans = 1
    for p in P:
        ans *= p
        ans %= MOD
    for m in M:
        ans *= m
        ans %= MOD
    if len(M) % 2 == 0:
        print(ans)
    else:
        if zero > 0:
            print(0)
        else:
            print(ans)
    exit()

P.sort(reverse=True)
M.sort()

# a >= 0 のとき
if len(M) == 0:
    ans = 1
    for k in range(K):
        ans *= P[k]
        ans %= MOD
    print(ans)
    exit()

# a <= 0 のとき
if len(P) == 0:
    ans = 1
    if K % 2 == 0:
        for k in range(K):
            ans *= M[k]
            ans %= MOD
        print(ans)
    else:
        if zero > 0:
            print(0)
        else:
            M.sort(reverse=True)
            for k in range(K):
                ans *= M[k]
                ans %= MOD
            print(ans)
    exit()

# a に正・負両方含まれる場合
cur_p = 0
cur_m = 0
ans = 1
for k in range(K):
    if cur_p == len(P):
        ans *= M[cur_m]
        cur_m += 1
    elif cur_m == len(M):
        ans *= P[cur_p]
        cur_p += 1
    else:
        if P[cur_p] < abs(M[cur_m]):
            ans *= M[cur_m]
            cur_m += 1
        else:
            ans *= P[cur_p]
            cur_p += 1
    ans %= MOD

if cur_m % 2 == 0:
    print(ans)
else:
    if cur_p != len(P) and cur_m != len(M):
        m1 = M[cur_m - 1]
        p1 = P[cur_p]
        m2 = M[cur_m]
        p2 = P[cur_p - 1]
        if abs(p1 * p2) > abs(m1 * m2):
            ans *= p1
            ans *= pow(m1, MOD - 2, MOD)
            ans %= MOD
        else:
            ans *= m2
            ans *= pow(p2, MOD - 2, MOD)
            ans %= MOD
    elif cur_p == len(P):
        ans *= M[cur_m]
        ans *= pow(P[cur_p - 1], MOD - 2, MOD)
        ans %= MOD
    elif cur_m == len(M):
        ans *= P[cur_p]
        ans *= pow(M[cur_m - 1], MOD - 2, MOD)
        ans %= MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
import bisect
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,K = LI()
AS=LI()
AS.sort(reverse=True)
res = 1
if AS[0] >= 0 and AS[N-1] >= 0:
    for i in range(K):
        res *= AS[i]
        res %= DVSR
elif AS[0] > 0:
    if N != K:
        AS.reverse()
        POS = bisect.bisect_left(AS, 1)
        AS2 = AS[POS:N]
        AS2.reverse()
        ACC = [1] * (len(AS2) + 1)
        for i in range(len(AS2)):
            ACC[i+1] = ACC[i]*AS2[i]
            ACC[i+1] %= DVSR

        BS = []
        for i in range(0, POS//2):
            BS.append(AS[i]*AS[i+1])
        BS.sort(reverse=True)

        BCC = [1]*(len(BS)+1)
        res = 1
        for i in range(len(BS)):
            BCC[i+1] = BS[i]*BCC[i]
            BCC[i+1] %= DVSR

        for i in range(min(K//2+1, len(BCC))):
            if K-2*i < len(ACC):
                res = max(BCC[i]*ACC[K-2*i]%DVSR, res)
        # print(ACC)
        # print(BCC)
    else:
        for i in range(N):
            res *= AS[i]
            res %= DVSR

else: # AS[0] <= 0
    if K % 2:
        v1 = 1
        v2 = 1
        for i in range(K):
            v1 *= AS[i]
            v1 %= DVSR
        for i in range(N-K, N):
            v2 *= AS[i]
            v2 %= DVSR
        if v1 == 0:
            res = v1
        else:
            res = v2
    else:
        res = 1
        for i in range(N-K, N):
            res *= AS[i]
            res %= DVSR


print(res)

Submission status: Wrong Answer

Solution code:
import random
from collections import deque
import sys
n,k =map(int,input().split())
A=[int(i) for i in input().split()]
A.sort()
P=deque()
Q=deque()
is_zero = False
for a in A:
    if a<0:
        P.append(a)
    elif a>=0:
        Q.appendleft(a)
c=0
S=1
lim = 10**9+7

if len(Q) == 0 and k&1:
    for _ in range(k):
        S*=P.pop()
        S%=lim
    print(S)
    sys.exit()
    
K=10**20
while c < k:
    if len(P)>1:
        p = P[0]*P[1]
    elif len(P)==1:
        p = K
    else:
        p = K
        
    if len(Q)>1:
        q = Q[0]*Q[1]
    elif len(Q)==1:
        q = Q[0]
    else:
        q = K
    #print(P,Q,p,q,c) 
    if p !=K and q!=K:
        if p<q or c == k-1:
            S*= Q.popleft()
            S%= lim
            c+=1
        else:
            S*= P.popleft()
            S%= lim
            S*= P.popleft()
            S%= lim
            c+=2
    elif p!=K and (q==K):
        S*= P.popleft()
        S%= lim
        S*= P.popleft()
        S%= lim
        c+=2
    elif (p==K) and (q!=K):
        S*= Q.popleft()
        S%= lim
        c+=1
    else:
        break
print(S)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def mod_div(x, y, mod=10 ** 9 + 7):
    return x * pow(y, mod - 2, mod) % mod


def solve():
    N, K = map(int, rl().split())
    A = list(map(int, rl().split()))
    MOD = 10 ** 9 + 7
    
    if K == N:
        ans = 1
        for ai in A:
            ans *= ai
            ans %= MOD
        print(ans)
        return

    A.sort(key=lambda num: abs(num), reverse=True)
    if all(ai < 0 for ai in A) and K % 2 == 1:
        ans = 1
        for ai in A[-K:]:
            ans *= ai
            ans %= MOD
        print(ans)
        return
    
    ans = 1
    min_pos, min_neg = 0, 0
    cnt_neg = 0
    for ai in A[:K]:
        if ai < 0:
            min_neg = ai
            cnt_neg += 1
        else:
            min_pos = ai
        ans *= ai
        ans %= MOD
    
    if cnt_neg % 2 == 0:
        print(ans)
    else:
        INF = 10 ** 10
        n_pos, n_neg = INF, INF
        for ai in A[K:]:
            if n_pos != INF and n_neg != INF:
                break
            if ai < 0 and n_neg == INF:
                n_neg = ai
            elif 0 <= ai and n_pos == INF:
                n_pos = ai
        if n_pos != INF and n_neg != INF:
            if abs(min_pos * n_pos) <= abs(min_neg * n_neg):
                ans = mod_div(ans, min_pos) * n_neg % MOD
            else:
                ans = mod_div(ans, min_neg) * n_pos % MOD
        elif n_pos != INF:
            ans = mod_div(ans, min_neg) * n_pos % MOD
        else:
            ans = mod_div(ans, min_pos) * n_neg % MOD
        print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    a.sort(key=abs, reverse=True)
    ans = 1
    if n - a.count(0) < k:
        print(0)
        return
    t = 0
    L = None
    R= inf
    for ai in a[:k]:
        if ai < 0:
            t ^= 1
            L = ai
        if ai > 0:
            R = ai
        ans *= ai
        ans %= mod
    if k == n:
        print(ans)
        return
    if max(a) < 0:
        ans = 1
        for i in range(k):
            ans *= a[-i - 1]
            ans %= mod
        print(ans)
        return
    if t:
        A = min(a[k:])
        B = max(a[k:])
        if A >= 0:
            ans *= pow(L, mod - 2, mod)
            ans *= B
        else:
            if A * L > B * R:
                ans *= pow(R, mod - 2, mod)
                ans *= A
            else:
                ans *= pow(L, mod - 2, mod)
                ans *= B
        print(ans % mod)
    else:
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,K = IL()
A = IL()
A = sorted(A,key= lambda x:-abs(x))

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

if max(A)<0 and K%2==1:
  ans = 1
  for i in range(K):
    ans *= A[N-1-i]
    ans %= MOD
  print(ans)
  exit()

count_M = 0
last_M = None
last_P = None
for i in range(K):
  if A[i] < 0:
    last_M = i
    count_M += 1
  else:
    last_P = i

if count_M%2 == 0:
  ans = 1
  for i in range(K):
    ans *= A[i]
    ans %= MOD
  print(ans)
  exit()

else:
  ANS1 = -INF
  ANS2 = -INF
  if last_M!=None:
    for i in range(K,N):
      if A[i] >= 0:
        ans = A[i]%MOD
        for ii in range(K):
          if ii != last_M:
            ans *= A[ii]
            ans %= MOD
        ANS1 = ans
        break
  if last_P!=None:
    for i in range(K,N):
      if A[i] <= 0:
        ans = A[i]%MOD
        for ii in range(K):
          if ii != last_P:
            ans *= A[ii]
            ans %= MOD
        ANS2 = ans
        break
  print(max(ANS1,ANS2))

Submission status: Wrong Answer

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

A = sorted(A, key=abs, reverse=True)
# print('A',A)

#全て負か確認
huflag=0
for i in range(N):
    if A[i]>=0:
        huflag=1
        break

dammy=1
for i in range(K):
    dammy = A[i]*dammy
# print('dammy', dammy)

if K==N:
    out=dammy

elif huflag==0 and K%2==1:
    out=1
    for i in range(K):
        out=out*A[-1*(i+1)]

else:
    out=1
    for i in range(K):
        out=out*A[i]

    if out<0:
        outkoho=[]
        outori=out


print(out%(10**9+7))

Submission status: Wrong Answer

Solution code:
"""
    Satwik_Tiwari ;) .
    4th july , 2020  - Saturday
"""

#===============================================================================================
#importing some useful libraries.
from __future__ import division, print_function

from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase


import bisect
from heapq import *
from math import *
from collections import deque
from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
from itertools import combinations as comb # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
from itertools import permutations as permutate
from bisect import bisect_left as bl
#If the element is already present in the list,
# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect
#If the element is already present in the list,
# the right most position where element has to be inserted is returned

#==============================================================================================

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")

#===============================================================================================
#some shortcuts

mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") #for fast input
def out(var): sys.stdout.write(str(var))  #for fast output, always take string
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())
# def graph(vertex): return [[] for i in range(0,vertex+1)]
def zerolist(n): return [0]*n
def nextline(): out("\n")  #as stdout.write always print sring.
def testcase(t):
    for p in range(t):
        solve()
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(a,b):
    ans = 1
    while(b>0):
        if(b%2==1):
            ans*=a
        a*=a
        b//=2
    return ans
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) : # Check Prime Number or not
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True

#===============================================================================================
# code here ;))
def bs(a,l,h,x):
    while(l<h):
        # print(l,h)
        mid = (l+h)//2
        if(a[mid] == x):
            return mid
        if(a[mid] < x):
            l = mid+1
        else:
            h = mid
    return l

def sieve(a): #O(n loglogn) nearly linear
    #all odd mark 1
    for i in range(3,((10**6)+1),2):
        a[i] = 1
    #marking multiples of i form i*i 0. they are nt prime
    for i in range(3,((10**6)+1),2):
        for j in range(i*i,((10**6)+1),i):
            a[j] = 0
    a[2] = 1 #special left case
    return (a)


def bfs(g,st):
    visited = [-1]*(len(g))
    visited[st] = 0
    queue = []
    queue.append(st)
    new = []
    while(len(queue) != 0):
        s = queue.pop()
        new.append(s)
        for i in g[s]:
            if(visited[i] == -1):
                visited[i] = visited[s]+1
                queue.append(i)
    return visited


def dfsusingstack(v,st):
    d = deque([])
    visited = [0]*(len(v))
    d.append(st)
    new = []
    visited[st] = 1
    while(len(d) != 0):
        curr = d.pop()
        new.append(curr)
        for i in v[curr]:
            if(visited[i] == 0):
                visited[i] = 1
                d.append(i)
    return new


def solve():
    n,k =sep()
    a = lis()
    pos= []
    neg = []
    for i in range(n):
        if(a[i]>=0):
            pos.append(a[i])
        else:
            neg.append(a[i])
    pos = sorted(pos)[::-1]
    neg = sorted(neg)
    cnt = k
    st1 = 0
    st2 = 0
    ans = 1
    end2 = len(neg)-1
    while(cnt>0):
        if(cnt>1):
            if(st1>=len(pos)-1 and st2>=len(neg)-1):
                ans = (ans*((neg[st2]*pos[st1])%mod))%mod
                st1+=1
                st2+=1
                cnt-=2
                continue
            if(st1>=len(pos)-1):
                ans = (ans*((neg[st2]*neg[st2+1])%mod))%mod
                st2+=2
                cnt-=2
                continue
            if(st2>=len(neg)-1):
                ans = (ans*((pos[st1]*pos[st1+1])%mod))%mod
                st1+=2
                cnt-=2
                continue
            if(cnt==3 and st1 == len(pos)-2):
                ans = (ans*((neg[st2]*neg[st2+1])%mod))%mod
                st2+=2
                cnt-=2
                continue
            if(pos[st1]*pos[st1+1] > neg[st2]*neg[st2+1]):
                ans = (ans*((pos[st1]*pos[st1+1])%mod))%mod
                st1+=2
                cnt-=2
            else:
                ans = (ans*((neg[st2]*neg[st2+1])%mod))%mod
                st2+=2
                cnt-=2
        else:
            if(st1>len(pos)-1):
                if(end2 > st2):
                    ans = (ans*(neg[end2]))%mod
                    end2-=1
                    cnt-=1
                    continue
                ans = (ans*neg[st2])%mod
                st2+=1
                cnt-=1
                continue
            ans = (ans*pos[st1])%mod
            st1+=1
            cnt-=1
    print(ans%mod)





testcase(1)
# testcase(int(inp()))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    a.sort(key=abs, reverse=True)
    ans = 1
    if n - a.count(0) < k:
        print(0)
        return
    t = 0
    L = None
    R= inf
    for ai in a[:k]:
        if ai < 0:
            t ^= 1
            L = ai
        if ai > 0:
            R = ai
        ans *= ai
        ans %= mod
    if k == n:
        print(ans)
        return
    if R == inf:
        ans = 1
        for i in range(k):
            ans *= a[-i - 1]
            ans %= mod
        print(ans)
        return
    if t:
        A = min(a[k:])
        B = max(a[k:])
        if A >= 0:
            ans *= pow(L, mod - 2, mod)
            ans *= B
        else:
            if A * L > B * R:
                ans *= pow(R, mod - 2, mod)
                ans *= A
            else:
                ans *= pow(L, mod - 2, mod)
                ans *= B
        print(ans % mod)
    else:
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()