Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

We will choose exactly K of these elements. Find the maximum possible product of the chosen elements.

Then, print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Constraints

1 \leq K \leq N \leq 2\times 10^5

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

Print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

The possible products of the two chosen elements are 2, -3, -4, -6, -8, and 12, so the maximum product is 12.

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

The possible products of the three chosen elements are -24, -12, -8, and -6, so the maximum product is -6.

We print this value modulo (10^9+7), that is, 1000000001.

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

The possible products of the one chosen element are -1 and 1000000000, so the maximum product is 1000000000.

Sample Input 4

10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1

Sample Output 4

999983200

Be sure to print the product modulo (10^9+7).



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Wrong Answer

Solution code:
import sys

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
    for ai in A[:K]:
        if ai < 0:
            min_neg = ai
        else:
            min_pos = ai
        ans *= ai
        ans %= MOD
    
    if 0 <= ans:
        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
            print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from collections import deque

N,K = map(int,input().split())
A = deque(sorted(list(map(int,input().split()))))
ans = 1
mod = 10**9 + 7
if A[-1] < 0 and K % 2 == 1:
    for v in range(K):
        ans *= A[-1-v]
        ans %= mod
    print(ans)
    exit()
for i in range(0,K,2):
    if K-i == 1:
        ans *= A.pop()
        ans %= mod
        break

    if A[0] < 0:
        if A[0] * A[1] > A[-1]* A[-2]:
            a = A.popleft()
            b = A.popleft()
        else:
            a = A.pop()
            b = A.pop()
        ans *= a*b
        ans %= mod
    else:
        a = A.pop()
        b = A.pop()
        ans *= a * b
        ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

class ModInt(int):

    MOD = 10 ** 9 + 7

    def __add__(self, other):
        self = ModInt(int.__add__(self, other) % ModInt.MOD)
        return self

    def __mul__(self, other):
        self = ModInt(int.__mul__(self, other) % ModInt.MOD)
        return self

def mysplit(data):
    ps = [] # include 0
    ms = []
    for d in data:
        if d < 0:
            ms.append(ModInt(d))
        else:
            ps.append(ModInt(d))
    return list(reversed(sorted(ps))), sorted(ms)

def small_abs(ms, k):
    ans = ModInt(1)
    ms = list(reversed(ms))
    for i in range(k):
        ans *= ms[i]
    return ans

def take_p(ans, k, ps, pk):
    #print('ps[pk]', ps[pk]) # debug
    ans *= ps[pk]
    pk += 1
    return ans, k - 1, pk

def take_m(ans, k, ms, mk, sign_p):
    #print('ms[mk]', ms[mk]) # debug
    ans *= ms[mk]
    mk += 1
    return ans, k - 1, mk, sign_p

def take_all_p(ans, k, ps, pk):
    while k > 0:
        ans, k, pk = take_p(ans, k, ps, pk)
    return ans

def take_all_m(ans, k, ms, mk, sign_p):
    while k > 0:
        ans, k, mk, sign_p = take_m(ans, k, ms, mk, sign_p)
    return ans

def solve(data, k):
    if len(data) == k:
        ans = ModInt(1)
        for d in data:
            ans *= d
        return ans
    ps, ms = mysplit(data)
    if len(ps) == 0:
        return small_abs(ms, k)
    ans = ModInt(1)
    sign_p = True
    pk = 0
    mk = 0
    while k > 0:
        if pk == len(ps) - 1: # last p
            if k % 2 == 1:
                ans, k, pk = take_p(ans, k, ps, pk)
            return take_all_m(ans, k, ms, mk, sign_p)
        if mk == len(ms) - 1: # last m
            if sign_p:
                return take_all_p(ans, k, ps, pk)
        if mk >= len(ms) or ps[pk] > -1 * ms[mk]:
            ans, k, pk = take_p(ans, k, ps, pk)
        else:
            ans, k, mk, sign_p = take_m(ans, k, ms, mk, sign_p)
    return ans



if __name__ == '__main__':
    n, k = list(map(int, input().split()))
    data = list(map(int, input().split()))
    ans = solve(data, k)
    #print('ans') # debug
    print(ans)



    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
from functools import reduce
n, k = map(int, input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
cross = reduce(lambda a, b: a*b, a[:k])
asw = cross % 1000000007
print(asw)

Submission status: Wrong Answer

Solution code:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, k = MAP()

a = LIST()

pos = []
neg = []
zero = []

for el in a:
    if(el<0):
        neg.append(el)
    elif(el>0):
        pos.append(el)
    else:
        zero.append(el)

pos = sorted(pos)[::-1]
neg = sorted(neg)[::-1]

ans = 1

if(k==n):
    for el in a:
        ans = (ans%mod*el%mod)%mod
else:

    if(len(pos)==0):
        if(k%2==0):
            temp = 0
            for i in range(len(neg)-1, -1, -1):
                if(temp==k):
                    break
                ans = (ans%mod*neg[i]%mod)%mod
                temp+=1
            if(temp<k):
                ans = 0
        else:
            temp = 0
            for i in range(len(neg) - 1):
                if (temp == k):
                    break
                ans = (ans%mod * neg[i]%mod) % mod
                temp += 1
            if (temp < k):
                ans = 0
    else:

        left = k

        i,j = 0, len(neg)-1

        while(left>1):
            temp, temp1 = 0, 0
            if(i<len(pos)-1):
                temp = pos[i]*pos[i+1]
                # i+=2
            if(j>=1):
                temp1 = neg[j]*neg[j-1]
                # j-=2
            if(temp==0 and temp1==0):
                break
            if(temp1>temp):
                ans = (ans*(temp1%mod))%mod
                j-=2
            else:
                ans = (ans*(temp%mod))%mod
                i+=2
            left -= 2
        # print(ans,i,j)
        if(left>1):
            ans = 0
        elif(left==1):
            if(i<len(pos)):
                ans = ((ans%mod)*pos[i])%mod
            else:
                ans1 = 1
                for b in range(i-1):
                    ans1 = (ans1%mod*(pos[b]))%mod
                for c in range(len(neg)-1, j-2,-1):
                    ans1 = (ans1%mod*neg[c])%mod
                ans = max(ans, ans1)

                if(i+2<len(pos)-1 and j+2<len(neg)-1):
                    ans1 = 1
                    for b in range(i + 1):
                        ans1 = (ans1 % mod * (pos[b])) % mod
                    for c in range(len(neg) - 1, j + 2, -1):
                        ans1 = (ans1 % mod * neg[c]) % mod
                    ans = max(ans, ans1)

                print(ans, ans1)
                ans = max(ans, ans1)
print(ans)

Submission status: Wrong Answer

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

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

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

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

n,k = m()

a = l()

a.sort()

mina = []

pra = []

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

lp = len(pra)

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

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


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

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

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

		

	#data.sort()
	co = 0

	for i in range(0,cm,2):
		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:
"""
    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)[::-1]
    cnt = k
    st1 = 0
    st2 = 0
    ans = 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(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):
                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:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True, key = lambda x: abs(x))
mod = 10**9+7
nega = 0
posi = 0
zero = 0
for i in range(n):
    if a[i] > 0:
        posi += 1
    elif a[i] == 0:
        zero += 1
    else:
        nega += 1

if n == k:
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod
    if nega%2 == 1:
        ans *= -1

elif posi == 0:

    if k % 2 == 0:
        ans = 1
        for i in range(k):
            ans *= abs(a[i])
            ans %= mod

    else:
        if zero > 0:
            ans = 0
        else:
            a.reverse()
            ans = 1
            for i in range(k):
                ans *= abs(a[i])
                ans %= mod

            ans *= -1


else:
    posi = 0
    nega = 0
    zero = 0
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod

    for i in range(k):
        if a[i] > 0:
            posi += 1
        elif a[i] < 0:
            nega += 1
        else:
            zero += 1

    if zero > 0:
        ans = 0

    elif nega % 2 != 0:
        minposi = 0
        minnega = 0
        for i in range(k-1, -1, -1):
            if a[i] > 0:
                if minposi == 0:
                    minposi = a[i]
            else:
                if minnega == 0:
                    minnega = a[i]

        maxposi = 0
        maxnega = 0
        flag = 0
        for i in range(k, n):
            if a[i] > 0:
                if maxposi == 0:
                    maxposi = a[i]
            elif a[i] < 0:
                if maxnega == 0:
                    maxnega = a[i]

        if minposi == 0:
            if maxnega == 0:
                pp

        if abs(minposi*maxposi) <= abs(minnega*maxnega):
            ans *= pow(abs(minposi), mod-2, mod)
            ans *= abs(maxnega)

        else:
            ans *= pow(abs(minnega), mod-2, mod)
            ans *= abs(maxposi)



print(ans % mod)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True, key = lambda x: abs(x))
mod = 10**9+7
nega = 0
posi = 0
zero = 0
for i in range(n):
    if a[i] > 0:
        posi += 1
    elif a[i] == 0:
        zero += 1
    else:
        nega += 1

if n == k:
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod
    if nega%2 == 1:
        ans *= -1

elif posi == 0:

    if k % 2 == 0:
        ans = 1
        for i in range(k):
            ans *= abs(a[i])
            ans %= mod

    else:
        if zero > 0:
            ans = 0
        else:
            a.reverse()
            ans = 1
            for i in range(k):
                ans *= abs(a[i])
                ans %= mod

            ans *= -1


else:
    posi = 0
    nega = 0
    zero = 0
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod

    for i in range(k):
        if a[i] > 0:
            posi += 1
        elif a[i] < 0:
            nega += 1
        else:
            zero += 1

    if zero > 0:
        ans = 0

    elif nega % 2 != 0:
        minposi = 0
        minnega = 0
        for i in range(k-1, -1, -1):
            if a[i] > 0:
                if minposi == 0:
                    minposi = a[i]
            else:
                if minnega == 0:
                    minnega = a[i]

        maxposi = 0
        maxnega = 0
        flag = 0
        for i in range(k, n):
            if a[i] > 0:
                if maxposi == 0:
                    maxposi = a[i]
            elif a[i] < 0:
                if maxnega == 0:
                    maxnega = a[i]

        if minposi == 0:
            if maxposi == 0:
                pp 

        if abs(minposi*maxposi) <= abs(minnega*maxnega):
            ans *= pow(abs(minposi), mod-2, mod)
            ans *= abs(maxnega)

        else:
            ans *= pow(abs(minnega), mod-2, mod)
            ans *= abs(maxposi)



print(ans % mod)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

class ModInt(int):

    MOD = 10 ** 9 + 7

    def __add__(self, other):
        self = ModInt(int.__add__(self, other) % ModInt.MOD)
        return self

    def __mul__(self, other):
        self = ModInt(int.__mul__(self, other) % ModInt.MOD)
        return self

def mysplit(data):
    ps = [] # include 0
    ms = []
    for d in data:
        if d < 0:
            ms.append(ModInt(d))
        else:
            ps.append(ModInt(d))
    return list(reversed(sorted(ps))), sorted(ms)

def small_abs(ms, k):
    ans = ModInt(1)
    ms = list(reversed(ms))
    for i in range(k):
        ans *= ms[i]
    return ans

def take_p(ans, k, ps, pk):
    #print('ps[pk]', ps[pk]) # debug
    ans *= ps[pk]
    pk += 1
    return ans, k - 1, pk

def take_m(ans, k, ms, mk, sign_p):
    #print('ms[mk]', ms[mk]) # debug
    ans *= ms[mk]
    mk += 1
    return ans, k - 1, mk, sign_p

def take_all_m(ans, k, ms, mk, sign_p):
    while k > 0:
        ans, k, mk, sign_p = take_m(ans, k, ms, mk, sign_p)
    return ans

def solve(data, k):
    if len(data) == k:
        ans = ModInt(1)
        for d in data:
            ans *= d
        return ans
    ps, ms = mysplit(data)
    if len(ps) == 0:
        return small_abs(ms, k)
    ans = ModInt(1)
    sign_p = True
    pk = 0
    mk = 0
    while k > 0:
        if pk == len(ps) - 1: # last p
            if k % 2 == 1:
                ans, k, pk = take_p(ans, k, ps, pk)
            return take_all_m(ans, k, ms, mk, sign_p)
        if mk >= len(ms) or ps[pk] > -1 * ms[mk]:
            ans, k, pk = take_p(ans, k, ps, pk)
        else:
            ans, k, mk, sign_p = take_m(ans, k, ms, mk, sign_p)
    return ans



if __name__ == '__main__':
    n, k = list(map(int, input().split()))
    data = list(map(int, input().split()))
    ans = solve(data, k)
    #print('ans') # debug
    print(ans)



    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

class ModInt(int):

    MOD = 10 ** 9 + 7

    def __add__(self, other):
        self = ModInt(int.__add__(self, other) % ModInt.MOD)
        return self

    def __mul__(self, other):
        self = ModInt(int.__mul__(self, other) % ModInt.MOD)
        return self

def mysplit(data):
    ps = [] # include 0
    ms = []
    for d in data:
        if d < 0:
            ms.append(ModInt(d))
        else:
            ps.append(ModInt(d))
    return list(reversed(sorted(ps))), sorted(ms)

def small_abs(ms, k):
    ans = ModInt(1)
    ms = list(reversed(ms))
    for i in range(k):
        ans *= ms[i]
    return ans

def take_p(ans, k, ps, pk):
    print('ps[pk]', ps[pk]) # debug
    ans *= ps[pk]
    pk += 1
    return ans, k - 1, pk

def take_m(ans, k, ms, mk, sign_p):
    print('ms[mk]', ms[mk]) # debug
    ans *= ms[mk]
    mk += 1
    return ans, k - 1, mk, sign_p

def take_all_m(ans, k, ms, mk, sign_p):
    while k > 0:
        print('k') # debug
        print(k) # debug
        ans, k, mk, sign_p = take_m(ans, k, ms, mk, sign_p)
    return ans

def solve(data, k):
    if len(data) == k:
        ans = ModInt(1)
        for d in data:
            ans *= d
        return ans
    ps, ms = mysplit(data)
    if len(ps) == 0:
        return small_abs(ms, k)
    ans = ModInt(1)
    sign_p = True
    pk = 0
    mk = 0
    while k > 0:
        if pk == len(ps) - 1: # last p
            if k % 2 == 1:
                ans, k, pk = take_p(ans, k, ps, pk)
            return take_all_m(ans, k, ms, mk, sign_p)
        if mk >= len(ms) or ps[pk] > -1 * ms[mk]:
            ans, k, pk = take_p(ans, k, ps, pk)
        else:
            ans, k, mk, sign_p = take_m(ans, k, ms, mk, sign_p)
    return ans



if __name__ == '__main__':
    n, k = list(map(int, input().split()))
    data = list(map(int, input().split()))
    ans = solve(data, k)
    #print('ans') # debug
    print(ans)



    #print('\33[32m' + 'end' + '\033[0m') # debug