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:
N, K = map(int, input().split())
A = list(map(int, input().split()))
m = 10**9+7
pos = [*filter(lambda x: x >= 0, A)]
neg = [*filter(lambda x: x < 0, A)]
pos.sort(reverse=True)
neg.sort()

ans = 1
i,j = 0,0# 使った数
while i+j < K:
    flag = True
    if i == len(pos):
        flag = False
    elif j == len(neg):
        flag = True
    elif pos[i] >= -neg[j]:
        flag = True
    else:
        flag = False

    if flag:
        ans = ans * pos[i] % m
        i += 1
    else:
        ans = ans * neg[j] % m
        j += 1
# print(i,j)
if j % 2 == 0 or N==K:
    print(ans)
elif len(pos) == 0:
    ans = 1
    for i in range(K):
        ans = ans * neg[len(neg)-1-i] % m
    print(ans)
else:
    flag2 = True
    if i == len(pos):
        flag2 = False
    elif j == len(neg):
        flag2 = True
    elif pos[i-1]*pos[i] >= neg[j-1]*neg[j]:
        flag2 = True
    else:
        flag2 = False

    if flag2:
        ans = ans * pow(neg[j-1],m-2,m) % m
        ans = ans * pos[i] % m
    else:
        ans = ans * pow(pos[i-1],m-2,m) % m
        ans = ans * neg[j] % m
    print(ans)

Submission status: Wrong Answer

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


def sgn(x):
    if x >= 0:
        return 0
    elif x < 0:
        return 1


pl = []
mn = []

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

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


b = [(abs(a[i]), sgn(a[i])) for i in range(n)]
b = sorted(b, reverse=True)

c = [0, 0]
for i in range(k):
    c[b[i][1]] += 1


def solve(c):
    ans = 1
    for i in range(c[0]):
        ans *= pl[i]
        ans %= mod
    for i in range(c[1]):
        ans *= mn[i]
        ans %= mod
    return ans


if c[1] % 2 == 0:
    print(solve(c))
    exit()

if len(mn) == n and k % 2:
    tmp = 1
    for i in range(k):
        tmp *= mn[-i-1]
        tmp %= mod
    ans = -tmp
    print(ans % mod)
    exit()

ans = 0

chk1 = False
chk2 = False

if c[0] <= len(pl) - 1:
    chk1 = True

if 0 < c[0] and c[1] <= len(mn)-1:
    chk2 = True

if chk1 and chk2:
    tmp1 = pl[c[0]]*pl[c[0]-1]
    tmp2 = mn[c[1]]*mn[c[1]-1]
    if tmp1 > tmp2:
        c[0] += 1
        c[1] -= 1
        print(solve(c))
    else:
        c[0] -= 1
        c[1] += 1
        print(solve(c))
elif chk1:
    c[0] += 1
    c[1] -= 1
    print(solve(c))
elif chk2:
    c[0] -= 1
    c[1] += 1
    print(solve(c))
else:
    print(solve(c))

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)
    else:
        is_zero = True
c=0
S=1
lim = 10**9+7

if len(Q) == 0 and k&1:
    if is_zero:
        print(0)
        sys.exit()
    for _ in range(k):
        S*=P.pop()
        S%=lim
    print(S)
    sys.exit()
    
while c < k:
    if len(P)>1:
        p = P[0]*P[1]
    elif len(P)==1:
        p = 0
    else:
        p = 0
        
    if len(Q)>1:
        q = Q[0]*Q[1]
    elif len(Q)==1:
        q = Q[0]
    else:
        q = 0
    #print(P,Q,p,q)  
    if p and q:
        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 and (not q):
        S*= P.popleft()
        S%= lim
        S*= P.popleft()
        S%= lim
        c+=2
    elif (not p) and q:
        S*= Q.popleft()
        S%= lim
        c+=1
    else:
        break
print(S)

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:
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
	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:
import copy
from sys import exit
n, k = map(int, input().split())
A = list(map(int, input().split()))

mod = 10**9 + 7

plus = []
minus = []
is_zero = False
for a in A:
    if a > 0:
        plus.append(a)
    if a < 0:
        minus.append(a)
    if a == 0:
        is_zero = True
plus.sort()
minus.sort(reverse=True)
plus_rev = plus[::-1]
minus_rev = minus[::-1]

#print(plus)
#print(minus)

def bad_case():
    ans = 1
    plus = plus_rev
    minus = minus_rev
    num_pair = k // 2
    for i in range(num_pair):
        if len(plus) >= 2 or len(minus) >= 2:
            pair_plus = float("inf")
            pair_minus = float("inf")
            try:
                pair_plus = plus[-1] * plus[-2]
            except:
                pass
            try:
                pair_minus = minus[-1] * minus[-2]
            except:
                pass
            #rint(pair_minus, pair_plus)
            if pair_minus < pair_plus:
                ans *= pair_minus
                minus.pop()
                minus.pop()
            else:
                ans *= pair_plus
                plus.pop()
                plus.pop()
            #print(ans)
            ans %= mod
    else:
        ans *= minus[-1]
    return ans



ans = 1
if len(plus) + len(minus) < k:
    print(0)
    exit()

if k % 2 == 0:
    num_pair = k // 2
    for i in range(num_pair):
        if len(plus) >= 2 or len(minus) >= 2:
            pair_plus = 0
            pair_minus = 0
            try:
                pair_plus = plus[-1] * plus[-2]
            except:
                pass
            try:
                pair_minus = minus[-1] * minus[-2]
            except:
                pass
            #print(pair_minus, pair_plus)
            if pair_minus > pair_plus:
                ans *= pair_minus
                minus.pop()
                minus.pop()
            else:
                ans *= pair_plus
                plus.pop()
                plus.pop()
            #print(ans)
        elif len(plus) == 1 and len(minus) == 1:
            if is_zero:
                ans = 0
                print(0)
                exit()
            else:
                ans *= plus[0] * minus[0]
            plus.pop()
            minus.pop()
        ans %= mod
else:
    num_pair = k // 2
    for i in range(num_pair):
        if len(plus) >= 2 or len(minus) >= 2:
            pair_plus = -float("inf")
            pair_minus = -float("inf")
            try:
                pair_plus = plus[-1] * plus[-2]
            except:
                pass
            try:
                pair_minus = minus[-1] * minus[-2]
            except:
                pass
            #print(pair_minus, pair_plus)
            if pair_minus > pair_plus:
                ans *= pair_minus
                minus.pop()
                minus.pop()
            else:
                ans *= pair_plus
                plus.pop()
                plus.pop()
            #print(ans)
        elif len(plus) == 1 and len(minus) == 1:
            if is_zero:
                ans = 0
                print(0)
                exit()
            else:
                ans *= plus[0] * minus[0]
            plus.pop()
            minus.pop()
        ans %= mod
    else:
        if len(plus) >= 1:
            ans *= plus[-1]
        elif is_zero:
            print(0)
            exit()
        else:
            ans = bad_case()
        ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
import math
import fractions
import collections
import itertools
import pprint
from collections import deque
N,K=map(int,input().split())
A=list(map(int,input().split()))
plist=[]
mlist=[]
ans=1
p=10**9+7
ab=[]
for i in range(N):
    ab.append([abs(A[i]),i])
ab.sort(key=lambda x:x[0],reverse=True)
micount=0
ans=1
for i in range(K):
    if A[ab[i][1]]<0:
        micount=micount+1
    ans=(ans*ab[i][0])%p
if micount%2==0:
    print(ans)
else:
    ans=(-ans)%p
    divind=0
    for i in range(K-1,-1,-1):
        if A[ab[i][1]]<0:
            divind=i
            break
    mulind=0
    for i in range(K,N):
        if A[ab[i][1]]>=0:
            mulind=i
            break
    ans=(ans*modinv(A[divind],p))%p
    ans=(ans*A[mulind])%p
    print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
list = list(map(int,input().split()))
list.sort(reverse=True)
#print(list)
seki = 1
if (list[0] >= 0) or (N == K):
    for i in range(K):
        seki *= list[i]
elif (list[-1] < 0) and (K % 2 !=0):
    for i in range(K):
        #print(-N+i)
        seki *= list[i]
        #print(list[i])
elif (list[-1] < 0) and (K % 2 ==0):
    list.sort()
    for i in range(K):
        seki *= list[i]
else:
    for i in range(K):
        seki *= list[i]
    count = 1
    if seki < 0:
        while seki < 0:
            seki = seki / list[count] * list[N-count+1]
            count -= 1
#print(seki)
print(seki%((10**9)+7))

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
	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:
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()
for a in A:
    if a<0:
        P.append(a)
    else:
        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()
    
while c < k:
    if len(P)>1:
        p = P[0]*P[1]
    elif len(P)==1:
        p = 0
    else:
        p = 0
        
    if len(Q)>1:
        q = Q[0]*Q[1]
    elif len(Q)==1:
        q = Q[0]
    else:
        q = 0
    #print(P,Q,p,q)  
    if p and q:
        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 and (not q):
        S*= P.popleft()
        S%= lim
        S*= P.popleft()
        S%= lim
        c+=2
    elif (not p) and q:
        S*= Q.popleft()
        S%= lim
        c+=1
    else:
        break
print(S)

Submission status: Wrong Answer

Solution code:
import sys

if(__name__ == "__main__"):

    N, K = map( int, input().strip().split() )
    divisor = 10**9+7
    list_a = list( map( int, input().strip().split() ) )
    multiplies = 1
    if(N==K):
        for i in range(N):
            multiplies = multiplies * list_a[i] % divisor
    else:
        list_a.sort()
        """
        解が負になるのはN>Kの時には
        正の項が1つもなく、Kが奇数の時
        """
        if(list_a[-1] < 0 and K % 2 != 0):
            """
            全て負の項
            list_a = [-5, -3, -1]のようにソートされている
            末尾の項から選んでいく
            """
            for i in range(K):
                multiplies = multiplies * list_a[N-1-i] % divisor
        else:
            left = 0
            right = N-1

            multiply_right = list_a[right] * list_a[right-1]
            flag_left = True
            for s in range(K//2):
                if(flag_left == True):
                    multiply_left = list_a[left] * list_a[left+1]
                else:
                    multiply_right = list_a[right] * list_a[right-1]
                if(multiply_left < multiply_right):
                    multiply_right %= divisor
                    multiplies = multiplies * multiply_right % divisor
                    right -= 2
                else:
                    multiply_left%=divisor
                    multiplies = multiplies * multiply_left % divisor
                    left += 2
            if(K%2!=0):
                multiplies = multiplies * list_a[right] % divisor

    print(multiplies)

Submission status: Wrong Answer

Solution code:
import copy
from sys import exit
n, k = map(int, input().split())
A = list(map(int, input().split()))

mod = 10**9 + 7

plus = []
minus = []
is_zero = False
for a in A:
    if a > 0:
        plus.append(a)
    if a < 0:
        minus.append(a)
    if a == 0:
        is_zero = True
plus.sort()
minus.sort(reverse=True)
plus_rev = plus[::-1]
minus_rev = minus[::-1]

#print(plus)
#print(minus)

def bad_case():
    ans = 1
    plus = plus_rev
    minus = minus_rev
    num_pair = k // 2
    for i in range(num_pair):
        if len(plus) >= 2 or len(minus) >= 2:
            pair_plus = float("inf")
            pair_minus = float("inf")
            try:
                pair_plus = plus[-1] * plus[-2]
            except:
                pass
            try:
                pair_minus = minus[-1] * minus[-2]
            except:
                pass
            #rint(pair_minus, pair_plus)
            if pair_minus < pair_plus:
                ans *= pair_minus
                minus.pop()
                minus.pop()
            else:
                ans *= pair_plus
                plus.pop()
                plus.pop()
            #print(ans)
            ans %= mod
    else:
        ans *= minus[-1]
    return ans



ans = 1
if len(plus) + len(minus) < k:
    print(0)
    exit()

if k % 2 == 0:
    num_pair = k // 2
    for i in range(num_pair):
        if len(plus) >= 2 or len(minus) >= 2:
            pair_plus = 0
            pair_minus = 0
            try:
                pair_plus = plus[-1] * plus[-2]
            except:
                pass
            try:
                pair_minus = minus[-1] * minus[-2]
            except:
                pass
            #print(pair_minus, pair_plus)
            if pair_minus > pair_plus:
                ans *= pair_minus
                minus.pop()
                minus.pop()
            else:
                ans *= pair_plus
                plus.pop()
                plus.pop()
            #print(ans)
        elif len(plus) == 1 and len(minus) == 1:
            if is_zero:
                ans = 0
                print(0)
                exit()
            else:
                ans *= plus[0] * minus[0]
            plus.pop()
            minus.pop()
        ans %= mod
else:
    num_pair = k // 2
    for i in range(num_pair):
        if len(plus) >= 2 or len(minus) >= 2:
            pair_plus = -float("inf")
            pair_minus = -float("inf")
            try:
                pair_plus = plus[-1] * plus[-2]
            except:
                pass
            try:
                pair_minus = minus[-1] * minus[-2]
            except:
                pass
            print(pair_minus, pair_plus)
            if pair_minus > pair_plus:
                ans *= pair_minus
                minus.pop()
                minus.pop()
            else:
                ans *= pair_plus
                plus.pop()
                plus.pop()
            #print(ans)
        elif len(plus) == 1 and len(minus) == 1:
            if is_zero:
                ans = 0
                print(0)
                exit()
            else:
                ans *= plus[0] * minus[0]
            plus.pop()
            minus.pop()
        ans %= mod
    else:
        if len(plus) >= 1:
            ans *= plus[-1]
        elif is_zero:
            print(0)
            exit()
        else:
            ans = bad_case()
        ans %= mod

print(ans)

Submission status: Wrong Answer

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

plus=[]
minus=[]
zero=0

for i in li:
  if i>0:
    plus.append(i)
  elif i==0:
    zero+=1
  else:
    minus.append(abs(i))
plus.sort()
minus.sort()

#print(minus)

res=1

if K>N-zero:
  res=0
  
elif len(plus)==0:
  if K%2==1 and zero>0:
    res==0
  elif K%2==1:
    for i in range(K):

      res=(res*minus[i])
      res=res%(10**9+7)
    res=-res
  else:
      for i in range(K):
        res=(res*minus[-i-1])
        res=res%(10**9+7)
    
else:
  while K>1:
    if len(plus)>1 and len(minus)>1:
      if plus[-1]*plus[-2] > minus[-1]*minus[-2]:
          res=res*plus[-1]*plus[-2]
          del plus[-2:]
          K-=2
      else:
        res=res*minus[-1]*minus[-2]
        del minus[-2:]
        K-=2

    elif len(plus)<2 and len(minus)>=2:
      res=res*minus[-1]*minus[-2]
      del minus[-2:]
      K-=2
      
    elif len(plus)>=2 and len(minus)<2:
      res=res*plus[-1]*plus[-2]
      del plus[-2:]
      K-=2
    
    res=res%(10**9+7)
    
  if K==0:
    res=res
  elif len(plus)>0:
    res=res*plus[-1]
  else:
    res=res*minus[-1]*(-1)
  
print(res%(10**9+7))

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
        res = max(v1, v2)
    else:
        res = 1
        for i in range(N-K, N):
            res *= AS[i]
            res %= DVSR


print(res)