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 math
n,k=list(map(int,input().split()))
l=list(map(int,input().split()))
lul = 10**9 + 7
if n==1:
	print(l[0])
else:
	pos = []
	neg = []
	for i in range(n):
		if l[i]<0:
			neg.append(-1*l[i])
		else:
			pos.append(l[i])
	pos.sort(); pos=pos[::-1]
	neg.sort();
	temp = list(neg)
	neg = neg[::-1]
	v = 1
	for i in range(len(pos)):
		v=(v*pos[i])%lul
		pos[i] = v
	v = 1
	for i in range(len(neg)):
		v=(v*neg[i])%lul
		neg[i] = v
	v = 0
	a = -1*math.inf
	# print('math.inf',-1*math.inf)
	# print(pos)
	# print(neg)
	while True:
		if(v>k):
			break
		if(v<=len(neg) and (k-v)<=len(pos)):
			ans = 1
			if((v-1) >= 0):
				ans = (ans*neg[v-1])%lul
			if((k-v-1) >= 0):
				ans = (ans*pos[k-v-1])%lul
			a = max(ans,a)
		v+=2
	# print(a)
	if(k<=len(neg) and a==(-1*math.inf)):
		# print("yo",neg[k-1])
		v = 1
		for i in range(k):
			v = v*((lul+(-1*temp[i]))%lul)
			v = v%lul
		# print(v)
		a = max(a,v)
	# print(a)
	print(a%lul)

Submission status: Wrong Answer

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

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

# 正に出来る場合：
# ・すべて正の数を選べる
# ・選べる数が奇数個で、負の数が偶数個と正の数が1個以上存在する
# ・選べる数が偶数個で、負の数が偶数個存在する
# 負になる場合：
# ・すべて負の数で且つ、選べる数が奇数個
# ・0が存在していれば、0のほうがマシ

# 開始時点で、絶対値が少ないほうを目指すか大きいほうを目指すか決まる
# 負の数を目指す場合、大きいほうからK個掛ければOK

# 大きいほうを目指す場合、
# 正の数の大きい順リスト [2,1]
# 負の数の絶対値大きい順リスト [-4,-3]
# の先頭から、2個のペアが大きくなるほうを貪欲に取っていく。
# 取れる数が奇数の場合は、まず正のほうの一番大きいのを取っちゃえばOK

pluslist = []
minuslist = []
zerocnt = 0
for i in range(len(A)):
  if A[i] > 0:
    pluslist.append(A[i])
  elif A[i] < 0:
    minuslist.append(A[i])
  else:
    zerocnt += 1
    
# 必ずゼロを選んでしまう場合
if N - zerocnt < K:
  print(0)
  exit(0)

if K % 2 == 1 and len(pluslist) == 0:
  # 負になる場合
  if zerocnt > 0:
    print(0)
    exit(0)
  # 絶対値が小さい状態を目指す
  minuslist = sorted(minuslist, reverse = True)
  ans = 1
  for i in range(K):
    ans *= minuslist[i]
    ans %= DIV
  print(ans)
  exit(0)
  
# 正の数を目指す
pluslist = sorted(pluslist, reverse = True)
minuslist = sorted(minuslist)
from collections import deque

plusq = deque(pluslist)
minusq = deque(minuslist)

ans = 1
if K % 2 == 1 and len(plusq) > 0:
  ans *= plusq.popleft() # 一番大きいものを取っておく
  K -= 1
  
for i in range(K // 2):
  p = 0
  m = 0
  if len(plusq) >= 2:
    p1 = plusq.popleft()
    p2 = plusq.popleft()
    p = p1 * p2
  if len(minusq) >= 2:
    m1 = minusq.popleft()
    m2 = minusq.popleft()
    m = m1 * m2
  if m == 0:
    ans *= p % DIV
    ans %= DIV
    continue
  if p == 0:
    ans *= m % DIV
    ans %= DIV
    continue
  if p > m:
    ans *= (p1 * p2) % DIV
    ans %= DIV
    minusq.appendleft(m2)
    minusq.appendleft(m1)
  else:
    ans *= (m1 * m2) % DIV
    ans %= DIV
    plusq.appendleft(p2)
    plusq.appendleft(p1)

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N ,K = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
mod = 10 ** 9 + 7
# ans = 0
if A.count(0) > (N - K):
  print(0)
  quit()
  
# ans = minus
plus = bisect.bisect_right(A, 0)
minus = bisect.bisect_left(A, 0) 
if N == K:
  ans = 1
  for i in range(N):
    ans *= A[i]
    ans %= mod
  print(ans % mod)
  quit()
  
if minus == N:
  ans = 1
  for i in range(1, K + 1):
    ans *= A[-i]
    ans %= mod
  print(ans % mod)
  quit()
  
ans = 1

count = 0
i = 0
j = -1
aa, bb = 0, 0
while count < K:
  
  if K - count >= 2:
    if aa == 1:
      fo = -10 ** 20
    else:
      fo = A[i] * A[i + 1]
      
    if bb == 1:
      re = -10 ** 20
    else:
      re = A[j] * A[j - 1]
    #print(fo, re)
    if fo > re:
      ans *= (fo % mod) 
      ans %= mod
      i += 2
      if i >= plus - 1 :
        aa = 1
    #elif (A[j - 1] < 1) or (A[j - 2] < 1):
    #  ans *= (fo % mod) 
    #  ans %= mod
    #  i += 2      
    else:
      ans *= (re % mod)
      ans %= mod
      j -= 2
      if -j >= minus:
        bb = 1
    count += 2  
  else:
    count += 1
    ans *= A[j]
      
  #print(ans)
print(ans % mod)

Submission status: Wrong Answer

Solution code:
from bisect import bisect

N,K = map(int,input().split())
Ali = list(map(int,input().split()))
ans = 1
Ali.sort()
mod = 10**9+7

if K%2 == 1:
  ans = Ali.pop()
  K -= 1
  
Am = Ali[0:bisect(Ali,0)]
Ap = Ali[bisect(Ali,0):]

Am.sort(reverse = True)
Ap.sort()

mp = len(Am)-1
pp = len(Ap)-1

while K>0:
  mmax = -1
  pmax = -1
  if mp >= 1:
    mmax = Am[mp]*Am[mp-1]
  if pp >= 1:
    pmax = Ap[pp]*Ap[pp-1]
    
  if mmax == pmax == -1:
    ans *= Am[0]*Ap[0]
    print(ans%mod)
    exit()
    
  if mmax >= pmax:
    ans = ans * mmax % mod
    mp -= 2
    K -= 2
  else:
    ans = ans * pmax % mod
    pp -= 2
    K -= 2
  



print(ans%mod)

Submission status: Wrong Answer

Solution code:
import heapq
mod = 10**9+7

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=0)
cnt_zero = a.count(0)
a = [i for i in a if i!=0]
if n-k < cnt_zero:
    print(0)
    exit()

neg = [i for i in a if i<0]
heapq.heapify(neg)

sneg = [-i for i in a if i<0]
heapq.heapify(sneg)

pos = [i for i in a if i>0]
heapq.heapify(pos)

if len(pos) < k:
    if len(pos) + len(neg) >= k:
        # negから補充できる
        if (k - len(pos))%2 == 0:
            # プラスになるように補充できる
            for i in range((k-len(pos))//2):
                neg1 = heapq.heappop(neg)
                neg2 = heapq.heappop(neg)
                heapq.heappush(pos, neg1)
                heapq.heappush(pos, neg2)
        else:
            # プラスにならない、せめて0を目指す
            if cnt_zero > 0:
                print(0)
                exit()
            else:
                # negを使うしかない。せめて絶対値の小さいのを使う
                for i in range(k-len(pos)):
                    neg1 = -heapq.heappop(sneg)
                    heapq.heappush(pos, neg1)
    else:
        # 0を使うしかない
        print(0)
        exit()
else:
    # posから弱いペアを抜いて、negの強いペアを入れ替える
    while len(pos) > 1 and len(neg) > 1:
        pos1 = heapq.heappop(pos)
        pos2 = heapq.heappop(pos)
        neg1 = heapq.heappop(neg)
        neg2 = heapq.heappop(neg)
        if pos1*pos2 < neg1*neg2:
            heapq.heappush(pos, neg1)
            heapq.heappush(pos, neg2)
        else:
            # もう入れ替えても強くならない
            heapq.heappush(pos, pos1)
            heapq.heappush(pos, pos2)
            break
ans = 1
for p in pos:
    ans = (ans*p)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
MOD = 10**9 + 7
def main(N, K, A):
    negative = sorted([a for a in A if a < 0])
    neg = len(negative)
    zero = [a for a in A if a == 0]
    positive = sorted([a for a in A if a > 0])
    pos = len(positive)

    if N - K < len(zero):
        return 0
    N -= len(zero)
    A = sorted([a for a in A if a != 0], key=lambda x: abs(x))

    ans = Mint(1)
    if ((neg & (~1)) + pos < K) or (neg & 1 and K == N) or (pos == 0 and K & 1):
        # マイナスになっちゃう
        for i in range(K):
            ans *= abs(A[i])
        ans = -ans
    else:
        # プラスにできる
        A.reverse()
        neg_cnt = 0
        last_pos = 0
        last_cnt = 0
        for i in range(K):
            ans *= abs(A[i])
            if A[i] < 0: neg_cnt += 1
            if neg_cnt & 1 == 0:
                last_pos = ans.value
                last_cnt = i + 1
        remain = K - last_cnt
        if remain != 0:
            pospos = 1
            negneg = 1
            pos_rem = remain
            neg_rem = remain
            for i in range(last_cnt, N):
                if A[i] > 0 and pos_rem > 0:
                    pospos *= A[i]
                    pos_rem -= 1
                if A[i] < 0 and neg_rem > 0:
                    negneg *= A[i]
                    neg_rem -= 1
                if pos_rem == neg_rem == 0:
                    break
            ans = Mint(last_pos * max(pospos, negneg))

    return ans

class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % MOD
        return self

    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other)) % MOD
        if self.value < 0: self.value += MOD
        return self

    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj

    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self

    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self

    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj

    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    input = sys.stdin.readline
    N, K = map(int, input().split())
    *A, = map(int, input().split())
    print(main(N, K, A))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,K=mi()
    A=list(mi())
    MOD = 10**9+7

    B = []
    zeros = 0
    for a in A:
        if a == 0:
            zeros += 1
            continue

        is_neg = a < 0
        B.append((abs(a),is_neg))
        

    if N-zeros < K:
        print(0)
        exit()

    NB = len(B)
    v = [(0,0)] * (NB+1) # (mult, neg_count)
    v[0] = (1,0)
    B.sort()
    for i in range(NB):
        b,is_neg = B[i]
        v[i+1] = (v[i][0] * b % MOD, v[i][1] + is_neg)
    
    j = 0
    ans = 0
    # print(v)
    U = []
    while j+K<=NB:
        mult = (v[j+K][0]//v[j][0]) % MOD
        if (v[j+K][1]-v[j][1]) % 2 == 1: # is negative sum
            mult *= -1

        U.append(mult)
        j += 1

    U.sort(reverse=True)
    print(U[0] % MOD)



    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
p=1000000007
product = 1
t=0
if A[n - 1] == 0 and (k & 1):
      print(0)
if A[n - 1] <= 0 and (k & 1):
        for i in range(n - 1, n - k - 1, -1):
            product *= A[i]
        print(product%p)
        t+=1



i = 0
j = n - 1
if k & 1:
            product *= A[j]
            j -= 1
            k -= 1

k >>= 1
for itr in range(k):

            left_product = A[i] * A[i + 1]

            right_product = A[j] * A[j - 1]

            if left_product > right_product:
                product *= left_product
                i += 2

            else:
                product *= right_product
                j -= 2
if t==0:
    print(product%p)

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(k):
			i = -(1+i)
			ans *= mina[i]
		print(ans % mod)
	else:
		for i in range(k):
			ans *= mina[i]
		print(ans % mod)
elif lp == 1:
	if n == k:
		mina.append(pra[0])
		mina.sort()
		for i in range(k):
			i = -(1+i)
			ans *= mina[i]
		print(ans % mod)
	else:
		if k % 2 == 0:
			for i in range(k):
				ans *= mina[i]
			print(ans % mod)
		else:
			ans *= pra[0] 
			for i in range(k-1):
				ans *= mina[i]
			print(ans % mod)
else:
	cp = lp-1
	cm = 0
	count = 0
	#data = []
	
	while count < 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 != lp:
			#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

	#data.sort()
	co = 0

	for i in range(0,cm,2):
		ans *= (mina[i] * mina[i+1]) % mod
		ans %= mod
	for i in range(lp-1,cp,-1):
		ans *= pra[i] % mod
		ans %= mod

	"""
	while co <= k:
		if k - co >= 2:
			if data[co] * data[co+1] >= 0:
				ans *= (data[co] * data[co+1]) % mod
				ans %= mod
				co += 2
			else:
				ans *= data[co]
				ans %= mod
				ans *= data[co+1]
				ans %= mod
				co += 2
		elif k - co == 1:
			ans *= data[co]
			ans %= mod
			co += 1
		else:
			break
	"""

		
	print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
A.sort()
B = []
flag = False
F = False
tmp = 0
num = -1
ans = 1
tmp_ = -1
for i, a in enumerate(A):
    if a < 0:
        if flag:
            B.append(tmp * a)
            flag = False
        else:
            tmp = a
            flag = True
    elif a == 0:
        F = True
    else:
        tmp_ = tmp
        num = i
        break

if num == -1:
    if K % 2 == 1:
        for i, a in enumerate(A[::-1]):
            ans *= a
            ans %= mod
            if i == K-1:
                print(ans)
                exit()

A = A[num:]
A.sort(reverse=True)
if K % 2 == 1:
    ans = A[0]
    A = A[1:]
    K -= 1
ans %= mod
flag = False
for a in A:
    if flag:
        B.append(tmp * a)
        flag = False
    else:
        tmp = a
        flag = True
K //= 2
if len(B) < K:
    if F:
        print(0)
        exit()
    else:
        ans *= tmp_

B.sort(reverse=True)
for i, b in enumerate(B):
    if K == i:
        break
    ans *= b
    ans %= mod

print(ans % mod)

Submission status: Wrong Answer

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

num_plus, num_zero, num_minus = 0, 0, 0
for i in range(N):
  if A[i] < 0:
    num_minus += 1
  elif A[i] == 0:
    num_zero += 1
  else:
    num_plus += 1

if num_plus == N:	# すべてプラスの場合
  A.sort(reverse=True)
  ans = 1
  for i in range(K):
    ans *= A[i]
  print(ans%(10**9+7))
elif num_minus == N:	# すべてマイナスの場合
  A.sort(reverse=True)
  ans = 1
  for i in range(K):
    ans *= A[i]
  print(ans%(10**9+7))
elif K > num_plus+num_minus:	# 0が含まれる場合
  print(0)
else:
  B = abs(np.array(A))
  B_idx = np.argsort(B)
  ans = 1
  for i in range(K):
    idx = B_idx[N-1-i]
    ans *= A[idx]
  print(ans)

Submission status: Wrong Answer

Solution code:

n, k = map(int,input().split())


arr = [ int(i) for i in input().split() ]


mod = (10**9)+7

pre = [ 0 for i in range(n) ]
suff = [ 0 for i in range(n+1) ]

pre[0] = arr[0]

for i in range(1, n):
	pre[i] = pre[i-1] * arr[i]
	pre[i] %= mod 

suff[n] = 1
suff[n-1] = arr[n-1]

for i in range(n-2,-1,-1):
	suff[i] = suff[i+1] * arr[i]
	suff[i] %= mod

max_ans = suff[n-k]


for i in range(k):
	fromLeft = k - i 
	ans = pre[i] * suff[n-fromLeft + 1]
	max_ans = max(max_ans, ans)

max_ans %= mod
print(max_ans)

Submission status: Wrong Answer

Solution code:
import sys
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def Main():
    n,k = IL()
    a = list(IL())
    a.sort()
    mod = int(1e9+7)
    ans = 1
    if k%2:
        for i in range(n-1,n-k-1,-1):
            ans = ans*min(a[i],a[i]%mod)
            ans = min(ans,ans%mod)
    else:
        l = r = 1
        for i in range(0,k):
            l = l*min(a[i],a[i]%mod)
            r = r*min(a[n-i-1],a[n-i-1]%mod)
            l = min(l,l%mod)
            r = min(r,r%mod)
            if abs(l)<abs(r):
                ans = r
            else:
                ans = l
    print(ans%mod)
    return

if __name__=='__main__':
    Main()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
P=[]
Z=[]
N=[]
for i in range(n):
  if a[i]>0:
    P.append(a[i])
  elif a[i]==0:
    Z.append(a[i])
  else:
    N.append(-a[i])
P.sort()
P3=[1]
for i in range(len(P)):
  P3.append(P3[-1]*P[i]%mod)
P.reverse()
P2=[1]
for i in range(len(P)):
  P2.append(P2[-1]*P[i]%mod)
N.sort()
N3=[1]
for i in range(len(N)):
  N3.append(N3[-1]*N[i]%mod)
N.reverse()
N2=[1]
for i in range(len(N)):
  N2.append(N2[-1]*N[i]%mod)

if len(P)+len(N)<k:
  print(0)
  exit()

if len(N)==0:
  print(P2[k])
  exit()

if len(P)+len(N)==k:
  if len(N)%2==0:
    print(P2[-1]*N2[-1]%mod)
    exit()
  else:
    print(-P2[-1]*N2[-1]%mod)
    exit()

if k%2==0:
  ans=1
  xp=0
  xn=0
  for i in range(k//2):
    if xp+1<len(P):
      xa=P[xp]*P[xp+1]
    else:
      xa=0
    if xn+1<len(N):
      xb=N[xn]*N[xn+1]
    else:
      xb=0
    if xa<xb:
      xn+=2
      ans*=xb
      ans%=mod
    else:
      xp+=2
      ans*=xa
      ans%=mod
  print(ans)

else:
  ans=1
  xp=0
  xn=0
  ctP=0
  ctN=0
  for i in range(k//2):
    if xp+1<len(P):
      xa=P[xp]*P[xp+1]
    else:
      xa=0
    if xn+1<len(N):
      xb=N[xn]*N[xn+1]
    else:
      xb=0
    if xa<xb:
      xn+=2
      ans*=xb
      ans%=mod
      ctN+=1
    else:
      xp+=2
      ans*=xa
      ans%=mod
      ctP+=1
  if ctP*2+1<=len(P):
    ans*=P[ctP*2]
    ans%=mod
    print(ans)
  else:
    N.reverse()
    P.reverse()
    ans=1
    xp=0
    xn=0
    ctP=0
    ctN=0
    for i in range(k//2):
      if xp+1<len(P):
        xa=P[xp]*P[xp+1]
      else:
        xa=0
      if xn+1<len(N):
        xb=N[xn]*N[xn+1]
      else:
        xb=0
      if xa<xb:
        xn+=2
        ans*=xb
        ans%=mod
        ctN+=1
      else:
        xp+=2
        ans*=xa
        ans%=mod
        ctP+=1
    ans*=N[ctN*2]
    ans%=mod
    print(-ans%mod)

Submission status: Wrong Answer

Solution code:
def resolve():
    def addans(i, ans):
        return ans * i % mod
    import sys
    import bisect
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    inf = float("inf")
    n, k = map(int, input().split())
    a = sorted(list(map(int, input().split())))
    l = bisect.bisect_left(a, 0)
    r = bisect.bisect_right(a, 0)
    if n - k < r - l:
        print(0)
        return
    if r == n:
        ans = 1
        for i in range(k):
            ans = addans(a[-i - 1], ans)
        print(ans)
        return
    ans = 1
    minus = a[::-1]
    plus = a
    if k % 2 == 1:
        ans = plus.pop()
        k -= 1
    try:
        m = minus.pop() * minus.pop()
    except:
        m = -inf
    try:
        p = plus.pop() * plus.pop()
    except:
        p = -inf
    for _ in range(k // 2):
        if p >= m:
            ans = addans(p, ans)
            try:
                p = plus.pop() * plus.pop()
            except:
                p = -inf
        else:
            ans = addans(m, ans)
            try:
                m = minus.pop() * minus.pop()
            except:
                m = -inf
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from functools import total_ordering

MOD = 1000000007  # type: int


def solve(N: int, K: int, A: "List[int]"):
    B = [Num(A[i]) for i in range(N)]
    B.sort(reverse=True)
    sign = 1
    ret = 1
    for i in range(K):
        sign *= B[i].getSign()
        ret *= B[i].getNum()
        ret %= MOD
    if sign > 0:
        print(ret)
        return
    elif sign < 0:
        minP = -1
        minP_i = 0
        minM = 1
        minM_i = 0
        for i in range(K - 1, -1, -1):
            if B[i].getSign() > 0:
                minP = B[i].getNum()
                minP_i = i
                break
        else:
            minP = 10 ** 10
        for i in range(K - 1, -1, -1):
            if B[i].getSign() < 0:
                minM = B[i].getNum()
                minM_i = i
                break
        else:
            minM = 10 ** 10
        maxP = -1
        maxP_i = 0
        maxM = 1
        maxM_i = 0
        for i in range(K, N):
            if B[i].getSign() > 0:
                maxP = B[i].getNum()
                maxP_i = i
                break
        else:
            maxP = 0
        for i in range(K, N):
            if B[i].getSign() < 0:
                maxM = B[i].getNum()
                maxM_i = i
                break
        else:
            maxM = 0
        x = abs(maxM) / abs(minP)   
        y = abs(maxP) / abs(minM)
        ret_new = 1
        if x > y:
            for i in range(K):
                if i != minP_i:
                    ret_new *= B[i].getNum()
                    ret_new %= MOD
            ret_new *= B[maxM_i].getNum()
            ret_new %= MOD
        else:
            for i in range(K):
                if i != minM_i:
                    ret_new *= B[i].getNum()
                    ret_new %= MOD
            ret_new *= B[maxP_i].getNum()
            ret_new %= MOD
        print(ret_new)
    else:
        print(0)
        return


@total_ordering
class Num:
    def __init__(self, num):
        self.num = num
        self.sign = (num > 0) - (num < 0)
    
    def __eq__(self, value):
        return abs(self.num) == abs(value.num)
    
    def __lt__(self, value):
        return abs(self.num) < abs(value.num)

    def getNum(self):
        return self.num

    def getSign(self):
        return self.sign

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    target_list = list(map(int, input().split()))
    normal_list = sorted(target_list)
    reverse_list = sorted(target_list, reverse=True)

    normal_max = 1
    reverse_max = 1
    for i in range(K):
        normal_max = normal_max * normal_list[i]
        reverse_max = reverse_max * reverse_list[i]
    if normal_max < reverse_max:
        ans_max = reverse_max
    else:
        ans_max = normal_max

    amari = ans_max % 1000000007
    print(amari)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq

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

MOD=10**9+7

ans=1
if L[-1]<=0:#全部負
    if K%2==1:
        #小さい方からKこ
        for l in L[-K:]:
            ans*=l
            ans%=MOD
    else:
        #大きい方からKこ
        for l in L[:K]:
            ans*=l
            ans%=MOD
elif L[0]>=0:#全部生
    for l in L[-K:]:
        ans*=l
        ans%=MOD
else:#生徒ふが入り混じり
    print(ans)
    exit()
    cand=[]
    poss=[]
    negs=[]
    replace=[]
    if K%2==1:#奇数個
        K-=1
        cand.append(L[-1])
        for l in L[:-1]:
            if l>0:
                heapq.heappush(poss,l)
                if len(poss)>K:
                    heapq.heappop(poss)#正の数でK番目より小さいやつは捨てる
            else:
                heapq.heappush(negs,l)
        #N-1こ(偶数を選んでから)追加で、正の(一番大きいやつを取っておく?)怪しい
    else:
        for l in L:
            if l>0:
                heapq.heappush(poss,l)
                if len(poss)>K:
                    heapq.heappop(poss)#正の数でK番目より小さいやつは捨てる
            else:
                heapq.heappush(negs,l)
    while len(negs)>=2:
        a = heapq.heappop(negs)
        b = heapq.heappop(negs)
        heapq.heappush(replace,-a*b)

    #print("poss=>",poss)
    #print("negs=>",negs)
    #print("rep=>",replace)
    #print("cand=>",cand)
    added=0

    while len(replace)>0:
        if len(poss)>=2:
            a = heapq.heappop(poss)
            b = heapq.heappop(poss)
            rep= - heapq.heappop(replace)
            if a*b<rep:#possのした二つを置き換える
                added+=2
                cand.append(rep)
        elif len(poss)+added<K:#possの長さが足りないから無条件で負の方から追加する
            rep= - heapq.heappop(replace)
            added+=2
            cand.append(rep)
    
    #print("last.poss=>",poss)
    #print("last can=>",cand)
    for p in poss:
        ans*=p
        ans%=MOD
    for r in cand:
        ans*=r
        ans%=MOD
print(ans%MOD)

Submission status: Wrong Answer

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

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

pos = []
nag = []
pn = []
zero = 0

for i in range(N):
    if A[i] > 0:
        pos.append(A[i])
        pn.append((A[i], True))
    elif A[i] < 0:
        nag.append(A[i])
        pn.append((-A[i], False))
    else:
        zero += 1

pos.sort()
nag.sort(reverse=True)
pn.sort()

# hard case work
if N - zero < K:
    print(0)

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

elif not pos and zero > 0:
    print(0)

elif not pos:
    ans = 1
    if K & 1:
        for i in range(K):
            ans *= nag[i]
            ans %= MOD
    else:
        for i in range(K):
            ans *= nag[-i-1]
            ans %= MOD
    print(ans)



# nagative and positive
else:
    # large first
    arr = []

    for i in range(K):
        if not pos: break
        arr.append(pos.pop())

    while len(arr) < K:
        arr.append(1)

    ans = 1

    while arr:
        if len(arr) == 1:
            ans *= arr[0]
            ans %= MOD
            break

        a = arr.pop()
        b = arr.pop()
        if len(nag) < 2:
            ans *= a * b
            ans %= MOD
        else:
            x = nag.pop()
            y = nag.pop()
            ans *= max(x * y, a * b)
            ans %= MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
def task():
    n,k=[int(i) for i in input().split()]
    arr=[int(i) for i in input().split()]
    arr.sort()
    mini=-999999999999999999999999999999999
    for i in range(0,n-k+1):
        temp=1
        for j in range(i,i+k):
            temp=temp*arr[j]
        mini=max(temp,mini)
    print(mini%1000000007)
def default():
    t=1
    while(t):
        t-=1
        task()
if(__name__=="__main__"):
    default()