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()))

A.sort(reverse=True)

mod=(10**9+7)
p=1
t=0
if k<n:
    if A[0]>=0 or k%2==0:
        for i in range(k//2):
            if A[k-1-2*i]*A[k-1-2*i-1]<A[-2*i-1]*A[-2*i-2]:
                t+=1


for i in range(k-2*t):
    p=p*A[i]%mod
for i in range(2*t):
    p=p*A[-i-1]%mod


print(p)

Submission status: Wrong Answer

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

if N - A.count(0) < K:
    print(0)
    exit(0)

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

    print(ans)
    exit(0)


plus = []
minus = []
for a in A:
    if a > 0:
        plus.append(a)
    elif a < 0:
        minus.append(a)

if K % 2 == 1 and len(plus) == 0:
    minus.sort(reverse=True)
    for i in range(K):
        ans *= minus[i]
        ans %= MOD
    print(ans)
    exit(0)

plus.sort(reverse=True)
minus.sort()

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

i = 0
j = 0

if K % 2 == 1:
    ans = plus[0]
    K -= 1
    plus = plus[1:]

for _ in range(K//2):
    if i+1 >= len(plus):
        ans *= (minus[j] * minus[j+1])
        ans %= MOD
        j += 2
        continue
    elif j+1 >= len(minus):
        ans *= (plus[i] * plus[i+1])
        ans %= MOD
        i += 2
        continue

    a = plus[i] * plus[i+1]
    b = minus[j] * minus[j+1]
    if a > b:
        ans *= a
        i += 2
    else:
        ans *= b
        j += 2
    ans %= MOD

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 != 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
	if cm % 2 != 0:
		anss = 1

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

		

	#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


		
	print(ans)

Submission status: Wrong Answer

Solution code:
import math
import collections
import bisect
from copy import copy, deepcopy

MOD = 1000000007


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    sortedA = sorted(A)
    n_neg = bisect.bisect_left(sortedA, 1)
    n_0 = n_neg - bisect.bisect_left(sortedA, 0)
    n_pos = N - n_neg - n_0

    ans = 1
    if (n_pos + n_neg <= K or n_pos == 0) and (K - n_pos) % 2 == 1:
        if n_0 != 0:
            ans = 0
        else:
            print(sortedA)
            absA = sorted(map(abs, sortedA))
            for i in range(K):
                ans *= absA[i]
                ans %= MOD
            ans *= -1
            ans %= MOD
    else:
        l = 0
        r = 0
        while(l + r < K):
            if sortedA[l] >= 0 or sortedA[l + 1] >= 0:
                ans *= sortedA[N - 1 - r]
                ans %= MOD
                r += 1
            elif sortedA[N - 1 - r] <= 0 or sortedA[N - 1 - r - 1] <= 0:
                ans *= sortedA[l]
                ans %= MOD
                ans *= sortedA[l + 1]
                ans %= MOD
                l += 2
            elif abs((sortedA[l] * sortedA[l + 1])) >= abs(sortedA[N - 1 - r] * sortedA[N - 1 - r - 1]):
                ans *= sortedA[l]
                ans %= MOD
                ans *= sortedA[l + 1]
                ans %= MOD
                l += 2
            else:
                ans *= sortedA[N - 1 - r]
                ans %= MOD
                r += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = sorted(A, key=lambda x: abs(x), reverse=True)
    Bp = [x for x in B if x > 0]
    Bm = [x for x in B if x < 0]
    Bpm = [x for x in B if x != 0]
    Bmm = []
    for i in range(0, len(Bm)-1, 2):
        Bmm.append(Bm[i]*Bm[i+1])

    q = 10**9 + 7

    n_plus, n_zero, n_minus = 0, 0, 0
    for a in A:
        if a > 0:
            n_plus += 1
        elif a < 0:
            n_minus += 1
        else:
            n_zero += 1

    if K > n_plus + n_minus:
        return 0

    # ans != 0
    rest = K
    ans = 1
    if K > n_plus and ((n_plus == 0 and K % 2 == 1) or (K == n_plus+n_minus and (K-n_plus) % 2 == 1)):
        # ans < 0
        for i in range(K):
            ans = (ans * Bpm[len(Bpm)-1-i]) % q
        return ans
    else:
        # ans > 0
        i, j = 0, 0
        while rest > 0:
            if rest >= 2 and j < len(Bmm):
                if i+1 < len(Bp):
                    if Bmm[j] >= Bp[i] * Bp[i+1]:
                        ans = (ans * (Bmm[j] % q)) % q
                        j += 1
                        rest -= 2
                    else:
                        ans = (ans * Bp[i]) % q
                        i += 1
                        rest -= 1
                elif i < len(Bp):
                    if Bmm[j] >= Bp[i]:
                        ans = (ans * (Bmm[j] % q)) % q
                        j += 1
                        rest -= 2
                    else:
                        ans = (ans * Bp[i]) % q
                        i += 1
                        rest -= 1
                else:
                    ans = (ans * (Bmm[j] % q)) % q
                    j += 1
                    rest -= 2
            else:
                ans = (ans * Bp[i]) % q
                i += 1
                rest -= 1
        return ans

        # i = 0
        # ip = 0
        # im = 0
        # while rest > 0:
        #     if B[i] > 0:
        #         ans = (ans * B[i]) % q
        #         i += 1
        #         ip += 1
        #         rest -= 1
        #     else:  # B[i] < 0
        #         if rest == 1:
        #             i += 1
        #         elif B[i+1] < 0:  # rest >= 2
        #             ans = (ans * (B[i]*B[i+1] % q)) % q
        #             i += 2
        #             im += 2
        #             rest -= 2
        #         else:  # rest >= 2 and B[i+1] > 0
        #             if Bp[ip] * Bp[ip+1] > Bm[im] * Bm[im+1]:
        #                 ans = (ans * (Bp[ip]*Bp[ip+1] % q)) % q


print(main())

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 != 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
	if cm % 2 != 0:
		anss = 1

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

	#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


		
	print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heappush
from collections import deque

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    mod = 7 + 10 ** 9
    q = []
    for a in A:
        if a < 0: heappush(q, (a, -1))
        else: heappush(q, (-a, 1))

    qu = deque()
    minus = -1
    plus = 1
    plusFound = False
    mc = 0
    ans = 1
    for i in range(K):
        a, pm = heappop(q)
        if pm == 1:
            plusFound = True
            ans *= plus
            ans %= mod
            plus = -a
        else:
            if mc == 1:
                ans *= (minus * a) % mod
                ans %= mod
            else:
                minus = a
            mc ^= 1
        qu.append((a, pm))
    if mc == 1:
        stock = 1
        sp = -1
        sm = 1
        for i in range(K, N):
            a, pm = heappop(q)
            if pm == 1 and sp == -1:
                sp = -a
            elif pm == -1 and plusFound and stock == 1:
                stock = a
            qu.append((a, pm))
        
        fin = False
        if sp > -1 and sm < 1:
            ans *= max(sp * plus, sm * minus) % mod
            fin = True
        elif sp > -1:
            ans *= (sp * plus) % mod
            fin = True
        elif sm < 1:
            ans *= (sm * minus) % mod
            fin = True

        if fin:
            print(ans % mod)
            return 0

        ans = 1
        for i in range(K):
            a, pm = qu.pop()
            ans *= a
            ans %= mod
        print(ans)
    else: 
        print((ans * plus) % mod)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import heapq
 
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
q=[]
for i in range(n):
  if arr[i]>0:
    heapq.heappush(q,(-arr[i],1))
  elif arr[i]<0:
    heapq.heappush(q,(arr[i],-1))
  else:
    heapq.heappush(q,(0,0))
pick=[]
prev=0
cnt=0
for i in range(k):
  tmp,flag=heapq.heappop(q)
  tmp*=-1
  if flag==0:
    print(0)
    exit()
  if flag==1:
    pick.append(tmp)
  if flag==-1:
    if cnt==0:
      prev=tmp
      cnt+=1
    else:
      cnt=0
      pick.append(prev)
      pick.append(tmp)
if cnt==0:
  ans=1
  for i in range(k):
    ans*=pick[i]
    ans%=mod
  print(ans%mod)
else:
  cand_plus=0
  cand_minus=0
  while len(q)!=0:
    tmp,flag=heapq.heappop(q)
    tmp*=-1
    if flag==1 and cand_plus==0:
      cand_plus=tmp
    if flag==-1 and cand_minus==0:
      cand_minus=tmp
  if cand_plus==0 and cand_minus==0:
    if arr.count(0)!=0:
      print(0)
      exit()
    else:
      q=[]
      for i in range(n):
        heapq.heappush(q,abs(arr[i]))
      ans=1
      for _ in range(k):
        ans*=heapq.heappop(q)
        ans%=mod
      print((-ans)%mod)
  else:
    if pick[-1]*cand_plus>=prev*cand_minus:
      pick.append(cand_plus)
    else:
      pick=pick[:-1]
      pick.append(prev)
      pick.append(cand_minus)
    ans=1
    for i in range(k):
      ans*=pick[i]
      ans%=mod
    print(ans%mod)

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def main():
    INF = 999999999999999999999999
    MOD = 10**9+7

    n,*A = get_all_int()
    A = list(A)
    A.sort(reverse=True)

    c = 1
    ans = A[0]
    i = 1
    flag = False
    while(c < n-1):
        ans += A[i]
        c += 1
        if flag:
            i+=1
            flag = False
        else:
            flag = True
    
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
A = list(map(int,input().split()))
B  =[0]*n
C = [0]*n
ff = 1
gg= 1
an = 1
t=0
u=0
for i in range(n):
  if(A[i]>=0):
    B[i]=A[i]
    C[i]= 0
    t +=1 
  else:
    B[i]=0
    C[i]=-A[i]
    u +=1
D = sorted(B)
E = sorted(C)
if(n>=2):
  if(t==0 and k%2==1):
    for i in range(k):
      an = (an*E[n-1-i])%(10**9+7)
    an = (-an)%(10**9+7)
  else:    
    for j in range(k-2):
      if(D[n-gg]>=E[n-ff]):
        an = (an*D[n-gg])%(10**9+7)
        gg+=1
      else:
        an = an*E[n-ff]%(10**9+7)
        ff +=1
    if(ff%2==0):
      an = (an*D[n-gg]*E[n-ff])%(10**9+7)
    else:
      an = (an*max(D[n-gg]*D[n-gg-1],E[n-ff]*E[n-ff-1]))%(10**9+7)
else:
  an = D[0]%(10**9+7)
print(an)

Submission status: Wrong Answer

Solution code:
import numpy as np
mod = 10 ** 9 + 7

n, k = map(int, input().split())
a = list(map(int, input().split()))
a_abs = list(map(abs, a))
a_sign = list(map(np.sign, a))
a_sort_idx = np.argsort(-np.array(a_abs))

plus = 0
minus = 0
zero = 0
for sign in a_sign:
    if sign == 0:
        zero += 1
    if sign == 1:
        plus += 1
    if sign == -1:
        minus += 1

def modinv(a):
    b = mod
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= mod
    if u < 0:
        u += m
    return u

def is_plus_possible():
    minus_div2 = minus // 2
    return (k - minus_div2 <= plus)

if is_plus_possible():
    flag = 1
    ans = 1
    last_sign_idx = [-1, -1]
    for i in range(k):
        flag *= a_sign[a_sort_idx[i]]
        ans = ans * a[a_sort_idx[i]] % mod
        if a_sign[a_sort_idx[i]] == 1:
            last_sign_idx[0] = i
        else:
            last_sign_idx[1] = i
    if flag == 1:
        print("hoge")
        print(ans)
        exit()
    else:
        last_sign = a_sign[a_sort_idx[k - 1]]
        rev_sign = last_sign * -1
        if last_sign == -1:
            if last_sign_idx[0] == -1:
                ans = ans * modinv(a[a_sort_idx[k - 1]]) % mod
                for i in range(k, n):
                    if a_sign[a_sort_idx[i]] == rev_sign:
                        ans = ans * a[a_sort_idx[i]] % mod
                        break
            print(ans)
            exit()
        else:
            big1 = a[a_sort_idx[k - 1]]
            big2 = a[a_sort_idx[last_sign_idx[0]]]
            if rev_sign == -1:
                big2 = a[a_sort_idx[last_sign_idx[1]]]
            small1, small2 = 10 ** -10, 10 ** -10
            for i in range(k, n):
                if a_sign[a_sort_idx[i]] == rev_sign:
                    small1 = a[a_sort_idx[i]]
                    break
            for i in range(k, n):
                if a_sign[a_sort_idx[i]] == last_sign:
                    small2 = a[a_sort_idx[i]]
                    break
            big, small = big1, small1
            if big1 / small1 >= big2 / small2:
                big, small = big2, small2
            ans = ans * modinv(big) % mod * small % mod
            print(ans)
            exit()
else:
    if zero > 0:
        print(0)
    else:
        a_abs.sort()
        ans = -1 % mod
        for i in range(k):
            ans = ans * a_abs[i] % mod
        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 != 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
	if cm % 2 != 0:
		anss = 1

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

	#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


		
	print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heappush
from collections import deque

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    mod = 7 + 10 ** 9
    q = []
    for a in A:
        if a < 0: heappush(q, (a, -1))
        else: heappush(q, (-a, 1))

    qu = deque()
    minus = -1
    plus = 1
    plusFound = False
    mc = 0
    ans = 1
    for i in range(K):
        a, pm = heappop(q)
        if pm == 1:
            plusFound = True
            ans *= plus
            ans %= mod
            plus = -a
        else:
            if mc == 1:
                ans *= (minus * a) % mod
                ans %= mod
            else:
                minus = a
            mc ^= 1
        qu.append((a, pm))
    if mc == 1:
        stock = 1
        sp = -1
        sm = 1
        for i in range(K, N):
            a, pm = heappop(q)
            if pm == 1 and sp == -1:
                sp = -a
            elif plusFound and stock == 1:
                stock = a
            qu.append((a, pm))
        
        fin = False
        if sp > -1 and sm < 1:
            ans *= max(sp * plus, sm * minus) % mod
            fin = True
        elif sp > -1:
            ans *= (sp * plus) % mod
            fin = True
        elif sm < 1:
            ans *= (sm * minus) % mod
            fin = True

        if fin:
            print(ans % mod)
            return 0

        ans = 1
        for i in range(K):
            a, pm = qu.pop()
            ans *= a
            ans %= mod
        print(ans)
    else: 
        print((ans * plus) % mod)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7
a.sort(reverse=True)
x = [[1, 0]]
for i in range(n):
    if a[i]<0:
        x.append([(x[-1][0]*(-a[i]))%mod, (x[-1][1]+1)%2])
    else:
        x.append([(x[-1][0]*(a[i]))%mod, x[-1][1]])
      

y = [[1, 0]]
for i in range(n):
    if a[-i-1] < 0: 
        y.append([(y[-1][0]*(-a[-i-1]))%mod, (y[-1][1]+1)%2])
    else:
        y.append([(y[-1][0]*a[-i-1])%mod, y[-1][1]])
r = []
for i in range(k+1):
    r.append([(x[i][0]*y[k-i][0])%mod, (x[i][1]+y[k-i][1])%2])



s, t = [], []
for i,j in r:
    if j==1:
        t.append(i)
    else:
        s.append(i)
if len(s)>0:
    print(s[0])
else:
    print((-t[-1])%mod)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7


def mod_mul(arr, mod):
    res = 1
    for elem in arr:
        res *= elem
        res %= mod
    return res


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(key=lambda x: abs(x), reverse=True)

    if all([e <= 0 for e in a]):
        print(mod_mul(a[n - k:], MOD))
        return

    if k == 1:
        print(max(a))
        return

    if k == n:
        print(mod_mul(a, MOD))
        return

    res = 1
    if sum(a[i] < 0 for i in range(k)) % 2 == 1:
        minus_flag = False
        for i in range(k - 1, -1, -1):
            if a[i] < 0:
                if not minus_flag:
                    minus_flag = True
                else:
                    res *= a[i]
                    res %= MOD
            else:
                res *= a[i]
                res %= MOD
        for i in range(k, n):
            if a[i] >= 0:
                res *= a[i]
                res %= MOD
                break
    else:
        for i in range(k):
            res *= a[i]
            res %= MOD

    print(res)


main()

Submission status: Wrong Answer

Solution code:
N , K = map(int, input().split())
A =list(map(int, input().split()))
mod = 10**9 + 7
count =0
for k in range(len(A)):
    if A[k] == 0:
        count +=1
        A[k] = float("inf")
if N-count < K:
    print(0)
    exit()
A.sort()
A = A[:N-count]
A.sort(reverse=True)
#print(A)
ans = 1
plus = 0
minus = -1
countp = 0
countm = 0
if A[0] >0:
    for k in range(K):
        if abs(A[plus]) >= abs(A[minus]):
            ans = ans*A[plus]%mod
            plus+=1
        else:
            ans = ans*A[minus]%mod
            if A[minus] <0:
                lasm = 0+minus
            minus-=1
            
    if minus%2 == 1:
        print(ans%mod)
    else:
        a = max(A[plus], A[minus])
        print(ans//A[lasm]*a%mod)
else:
    for k in range(K):
        ans = ans*A[k]%mod
    print(ans%mod)

Submission status: Wrong Answer

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

NEGA = 0
POSI = 1
EVEN = 0
ODD = 1
MOD = 10**9 + 7

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    is_all_nega = True

    b = []
    for i_a in a:
        if i_a < 0:
            b.append((abs(i_a), NEGA))
        else:
            b.append((i_a, POSI))
            is_all_nega = False

    a.sort(reverse=True)
    ans = 1
    if is_all_nega and k % 2 == 1:
        for i in range(k):
            ans *= a[i]
            ans %= MOD
        print(ans)
        return


    b.sort(reverse=True)

    e_or_o = 0
    pool_nega_num = None
    pool_posi_num = None
    add_num = 0
    ans = 1
    for i_num, i_n_or_p in b:
        if i_n_or_p == NEGA:
            e_or_o += 1

            if e_or_o % 2 == 0:
                if add_num + 1 == k:
                    if pool_posi_num is None:
                        ans *= i_num * pool_nega_num
                    else:
                        ans = ans * i_num * pool_nega_num // pool_posi_num
                    ans %= MOD
                    add_num += 1
                else:
                    ans *= i_num * pool_nega_num
                    ans %= MOD
                    add_num += 2
            else:
                pool_nega_num = i_num
        
        else:
            ans *= i_num
            ans %= MOD
            add_num += 1
            pool_posi_num = i_num

        if add_num == k:
            break

    if e_or_o % 2 == 1:
        ans *= -1
        ans %= MOD
    print(ans)
    return


if __name__ == "__main__":
    main()
    sys.exit(0)