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 = [int(a) for a in input().split()]

mod = 10**9+7

cp = 0
cm = 0
for i in range(N):
    n = 1
    if A[i] < 0:
        n = -1
    elif A[i] == 0:
        n = 0
    A[i] = (abs(A[i]), n)
    if n > 0:
        cp += 1
    elif n < 0:
        cm += 1

f = -1
for i in range(0, K+1, 2):
    if i <= cm and K-i <= cp:
        f = 1
        break


if K > cp+cm:
    ans = 0
elif f == -1:
    A.sort()
    ans = 1
    for i in range(K):
        ans *= A[i][0]
        ans %= mod
    ans *= -1
    ans %= mod
else:
    A.sort(reverse=True)
    cnt = 0
    ans = 1
    for i in range(K):
        ans *= A[i][0]
        ans %= mod
        if A[i][1] < 0:
            cnt += 1

    if cnt % 2 == 1:
        a1 = 1
        if K > cnt and cnt < cm:
            for i in range(K, N):
                if A[i][1] < 0:
                    a1 *= A[i][0]
                    break
            for i in range(K-1, -1, -1):
                if A[i][0] > 0:
                    a1 /= A[i][0]
                    break
        else:
            a1 = -1
        a2 = 1
        if cnt > 0 and cnt < cp:
            for i in range(K, N):
                if A[i][1] > 0:
                    a2 *= A[i][0]
                    break
            for i in range(K-1, -1, -1):
                if A[i][0] < 0:
                    a2 /= A[i][0]
                    break
        else:
            a2 = 0
        if a1 > a2 >= 0:
            for i in range(K, N):
                if A[i][1] < 0:
                    ans *= A[i][0]
                    break
            for i in range(K-1, -1, -1):
                if A[i][0] > 0:
                    ans *= pow(A[i][0], mod-2, mod)
                    ans %= mod
                    break
        elif a2 > a1 >= 0:
            for i in range(K, N):
                if A[i][1] > 0:
                    ans *= A[i][0]
                    break
            for i in range(K-1, -1, -1):
                if A[i][0] < 0:
                    ans *= pow(A[i][0], mod-2, mod)
                    ans %= mod
                    break
        else:
            ans = 0

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9+7

ps = []
ns = []
zs = []
for i in range(n):
  if a[i] > 0:
    ps.append(a[i])
  elif a[i] < 0:
    ns.append(a[i])
  else:
    zs.append(a[i])
    
if len(ps) + len(ns) < k:
  print(0)
elif len(ps) == 0:
  ans = 1
  if k % 2 == 0:
    ns = sorted(ns)
    for i in range(k):
      ans = ans * ns[i] % mod
  elif len(zs) > 0:
    print(0)
  else:
    ns = sorted(ns, reverse=True)
    for i in range(k):
      ans = ans * ns[i] % mod
  print(ans)
else:
  ans = 1
  ps = sorted(ps, reverse=True)
  ns = sorted(ns)
  if k % 2 == 0:
    pp = []
    for i in range(0,min(k, len(ps)), 2):
      try:
        pp.append(ps[i] * ps[i+1])
      except:
        pass
  else:
    pp = []
    ans = ps[0]
    for i in range(1,min(k, len(ps)), 2):
      try:
        pp.append(ps[i] * ps[i+1])
      except:
        pass
  np = []
  for i in range(0,min(k, len(ps)), 2):
    try:
      np.append(ns[i] * ns[i+1])
    except:
      pass
  pnp = sorted(pp + np, reverse=True)
  if len(pnp) >= k//2:
    for i in range(k//2):
      ans = ans * pnp[i] % mod
    print(ans)
  else:
    print(0)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import os
from sys import stdin, stdout

MOD = int(1e9+7)

def solve(tc):
    n, k = map(int, stdin.readline().split())
    seq = list(map(int, stdin.readline().split()))

    seq = sorted(seq, key=lambda x: abs(x), reverse=True)

    last_plus = -1
    last_minus = -1
    mul_minus = False

    arr = []
    p = 0
    while p < n and len(arr) < k:
        if seq[p] == 0:
            p += 1
            continue

        if seq[p] < 0:
            last_minus = len(arr)
            mul_minus ^= True
        elif seq[p] > 0:
            last_plus = len(arr)

        arr.append(seq[p])
        p += 1

    # should contain zeros
    if p == n and len(arr)<k:
        print(0)
        return

    # found maximal
    if not mul_minus:
        ans = 1
        for num in arr:
            ans *= num
            ans %= MOD
        print(ans)
        return

    first_plus = -1
    first_minus = -1
    while p < n:
        if seq[p] < 0:
            if first_minus < 0:
                first_minus = p
        elif seq[p] > 0:
            if first_plus < 0:
                first_plus = p
        p += 1

    if last_plus < 0 and first_plus < 0:
        ans = 1
        for i in range(n-1, n-k-1, -1):
            ans *= seq[i]
            ans %= MOD
        print(ans)
        return

    if first_minus < 0:
        arr[last_minus] = seq[first_plus]
    elif first_plus < 0:
        arr[last_plus] = seq[first_minus]
    else:
        if seq[first_plus]*arr[last_plus] < seq[first_minus]*arr[last_minus]:
            arr[last_plus] = seq[first_minus]
        else:
            arr[last_minus] = seq[first_plus]
    ans = 1
    for num in arr:
        ans *= num
        ans %= MOD
    print(ans)


tcs = 1
tc = 1
while tc <= tcs:
    solve(tc)
    tc += 1

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = sorted(map(int, input().split()))
mod = 10 ** 9 + 7

mia, pla, zero = [], [], []
for ai in a:
    if ai < 0:
        mia.append(ai)
    elif ai > 0:
        pla.append(ai)
    elif ai == 0:
        zero.append(ai)

cnt = 1
while k > 0:
    if len(pla) == 0 and len(mia) == 0:
        print(0)
        break
    elif len(pla) == 0:
        cnt = cnt * mia.pop() % mod
        k -= 1
    elif len(mia) <= 1 or k == 1:
        cnt = cnt * pla.pop() % mod
        k -= 1
    elif len(pla) == 1:
        if k % 2 == 1:
            cnt = cnt * pla.pop() % mod
            k -= 1
        elif k % 2 == 0 and len(mia) >= 2:
            cnt = cnt * mia.pop() * mia.pop() % mod
            k -= 2
        elif k % 2 == 0 and len(mia) == 1:
            cnt = cnt * pla.pop() % mod
            k -= 1
    elif len(pla) >= 2 and len(mia) >= 2:
        if pla[-1] * pla[-2] >= mia[-1] * mia[-2]:
            cnt = cnt * pla.pop() % mod
            k -= 1
        elif pla[-1] * pla[-2] < mia[-1] * mia[-2]:
            cnt = cnt * mia.pop() * mia.pop() % mod
            k -= 2
else:
    print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

def solve():
    N, K = mapint()
    As = list(mapint())
    mod = 10**9+7
    pos = []
    neg = []
    for a in As:
        if a>=0:
            pos.append(a)
        else:
            neg.append(a)

    pos.sort(reverse=True)
    neg.sort()
    lenp = len(pos)
    lenn = len(neg)
    if not pos and K%2==1:
        ans = 1
        for i, n in enumerate(neg[::-1]):
            ans *= n
            ans %= mod
            if i==K-1:
                break
        return ans
    if lenp+lenn==K and (K-lenp)%2==1:
        ans = 1
        pos.extend(neg)
        pos.sort(reverse=True)
        for i, p in enumerate(pos):
            ans *= p
            ans %= mod
            if i==K-1:
                break
        return ans
    ans = 1
    pcnt = 0
    ncnt = 0
    for i in range(K//2):
        if pcnt*2+1>=lenp:
            ans *= neg[ncnt*2]*neg[ncnt*2+1]
            ans %= mod
            ncnt += 1
        elif ncnt*2+1>=lenn:
            ans *= pos[pcnt*2]*pos[pcnt*2+1]
            ans %= mod
            pcnt += 1
        elif pos[pcnt*2]*pos[pcnt*2+1]>neg[ncnt*2]*neg[ncnt*2+1]:
            ans *= pos[pcnt*2]*pos[pcnt*2+1]
            ans %= mod
            pcnt += 1
        else:
            ans *= neg[ncnt*2]*neg[ncnt*2+1]
            ans %= mod
            ncnt += 1
    if K%2==1:
        ans *= pos[pcnt]
        ans %= mod
    return ans

print(solve())

Submission status: Wrong Answer

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

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 inv(x, MOD):
    return pow(x, MOD-2, MOD)

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

    n,k,*A = get_all_int()
    A = list(A)

    # 答えが負である条件
    # ・Aが全て負で、Kが奇数
    # ・Aの負数が奇数個かつ0が存在せず、K=N

    # 答えが0である条件
    # ・N-(Aの0の個数) < K

    positives = 0
    zeros = 0
    negatives = 0

    for a in A:
        if a > 0:
            positives += 1
        elif a == 0:
            zeros += 1
        else:
            negatives += 1
    

    if k == 1:
        # 1個だけの場合はたんに最大値を出力する
        A.sort(reverse=True)
        print(A[0])
        exit()

    if (n-zeros) < k:
        # 答えが0
        print(0)
        exit()
    
    elif (k==n and negatives%2==1  or  n==negatives+zeros and k%2==1):
        # 答えが負
        # 絶対値小さい順にK個掛ける
        A.sort(key=lambda a: abs(a))
        # log(A)
        ans = 1
        for i in range(k):
            ans =  (ans * A[i]) % MOD
        print(ans%MOD)
        exit()

    else:
        # 答えが正
        # 絶対値大きい順にK個掛ける
        A.sort(reverse=True, key=lambda a: abs(a))
        # log(A)
        ans = 1
        n_count = 0
        last_n = 0
        last_p = 0
        for i in range(k):
            a = A[i]
            ans =  (ans * a) % MOD
            if a < 0:
                n_count += 1
                last_n = a
            elif a > 0:
                last_p = a
                # log(i, last_n)

        # log(ans, n_count, last_n)
        
        # 負数を奇数個選んでいる場合は調整する
        if n_count%2 == 1:
            first_p = None
            first_n = None
            for i in range(k,n):
                a = A[i]
                if a > 0 :
                    ans_a = ans*inv(last_n, MOD) * a
                    first_p = a
                    break
            if last_p != 0:
                for i in range(k,n):
                    a = A[i]
                    if a < 0:
                        ans_b = ans*inv(last_p, MOD) * a
                        first_n = a
                        break
                if first_n is not None:
                    if first_p is not None:
                        xx = Fraction(first_p, last_n)
                        yy = Fraction(first_n, last_p)
                        # xx = abs(first_p) / abs(last_n)
                        # yy = abs(first_n) / abs(last_p)
                        if yy > xx:
                            ans_a = ans_b
                    else:
                        ans_a = ans_b
            if first_n is None and first_p is None:
                ans_a = 0
            ans = ans_a
        
        print(ans%MOD)
        exit()

main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int , input().split()))
MOD = 10 ** 9 + 7

a.sort()
cm = 0
c0 = 0
cp = 0
for ai in a:
    if ai == 0:
        c0 += 1
    elif ai > 0:
        cp += 1
    else:
        cm += 1

ans = []
tmp = 1
#print(a[-k:], a[:k])
for ai in a[-k:]:
    tmp *= ai % MOD
ans.append(tmp)
tmp = 1
for ai in a[:k]:
    tmp *= ai % MOD
ans.append(tmp)
if c0 > 0:
    ans.append(0)

#print(ans)
print(max(ans) % MOD)

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

	#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:
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 N - zero == K:
    ans = 1
    if len(nag) & 1 == 0:
        for k in nag + pos:
            ans *= k
            ans %= MOD
    else:
        ans = 0
    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:
n, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort(reverse=True, key=lambda x:abs(x))
cnt = 0
im = 0
ip = 0
cp = 0
mod = 10 ** 9 + 7

for i, ai in enumerate(a):
    if i < k:
        if ai < 0:
            im = i
            cnt += 1
        if ai > 0:
            ip = i
    if ai > 0:
        cp += 1

ans = 1
f = 0

# print(a)
if cnt % 2:
    if cp == 0:
        a.sort(reverse=True)
        for i, ai in enumerate(a):
            if i == k:
                break
            ans *= ai
            ans %= mod
        print(ans)
    else:
        ans = 1
        cnt = 0
        f = 0
        for i, ai in enumerate(a):
            if cnt == k:
                f = 2
                break
            if i == im:
                f = 1
                continue
            if f == 1 and ai <= 0:
                continue
            ans *= abs(ai)
            ans %= mod
            # print(i, ai)
            cnt += 1
        if f == 2:
            print(ans)
        else:
            ans = 1
            cnt = 0
            f = 0
            for i, ai in enumerate(a):
                if cnt == k:
                    f = 2
                    break
                if i == ip:
                    f = 1
                    continue
                if f == 1 and ai >= 0:
                    continue
                ans *= abs(ai)
                ans %= mod
                # print(i, ai)
                cnt += 1
            if f == 2:
                print(ans)
            else:
                ans = 1
                a.sort(reverse=True)
                for i, ai in enumerate(a):
                    if i == k:
                        break
                    ans *= ai
                    ans %= mod
                print(ans)

else:
    for i, ai in enumerate(a):
        if i == k:
            break
        ans *= abs(ai)
        ans %= mod
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, K = mi()
A = li()

d = defaultdict(int)
mod = 10**9+7
K_ = K

for i in range(N):
    d[A[i]] += 1
    if A[i] < 0:
        A[i] *= -1

A = sorted(A, reverse=True)
l = []

for num in A:
    if d[-num] > 0:
        l.append(1)
        d[-num] -= 1
    else:
        l.append(0)
        d[num] -= 1

#print(l)
#print(sum(l[:K]))

if not sum(l[:K])%2:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= mod
    print(ans)

else:
    flag = False
    ans = 1
    for i in range(K, N):
        if not l[i]:
            flag = True
            ans *= A[i]
            ans %= mod
            break
    
    if flag:
        for i in reversed(range(K)):
            if flag and l[i]:
                flag = 0
                continue
            ans *= A[i]
            ans %= mod
        print(ans)
    
    else:
        if K%2:
            for i in range(N-K, N):
                ans *= -A[i]
                ans %= mod
            print(ans)

        else:
            for i in range(N):
                if l[i]:
                    K -= 1
                    ans *= A[i]
                    ans %= mod
                if K == 0:
                    break

            else:
                if N == K_:
                    ans = -1
                    for num in A:
                        ans *= num
                        ans %= mod
                    print(ans)
                    exit()
    
                ans = 1
                flag = True
                for i in reversed(range(K_)):
                    if flag and not l[i]:
                        flag = 0
                        continue
                    ans *= A[i]
                    ans %= mod
                ans *= A[K_]
                ans %= mod
                print(ans)
                exit()

            print(ans)

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 num_zero>N-K:
  print(0)
  sys.exit(0)
  
if N==K:
  answer=1
  for a in alist:
    answer*=a
    answer%=MOD
  print(answer)
  sys.exit(0)
  
pos_possible=True
if num_pos+num_zero==0:
  if 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
for i in range(K-1):
  aa,a=aalist[i]
  answer*=a
  answer%=MOD
  if a<0:
    sgn*=-1
for i in range(K-1,N):
  aa,a=aalist[i]
  if sgn>0 and a>=0:
    answer*=a
    answer%=MOD
    break
  elif sgn<0 and a<=0:
    answer*=a
    answer%=MOD
    break
    
print(answer)

Submission status: Wrong Answer

Solution code:
import sys, bisect


if(__name__ == "__main__"):

    N, K = map( int, input().strip().split() )
    divisor = 10**9+7

    list_a = list( map(int, input().strip().split()) )

    """
    left, right側の2項の積で大きい方を選択
    選べるのが残り1項ならright側を選択
    """
    multiplies = 1

    if(N==K or N==1):
        for i in range(N):
            multiplies = multiplies * list_a[i] % divisor
        print(multiplies)
    else:
        list_a.sort()
        N_negative_numbers = bisect.bisect_left(list_a, 0)
        N_select_negatives = K + N_negative_numbers -N
        flag_overzero = True
        if(N_select_negatives > 0 and N_select_negatives % 2 != 0):
            flag_overzero = False
        if(flag_overzero == True):
            left = 0
            right = N-1

            multiply_right = list_a[right] * list_a[right-1]
            flag_left = True
            while(K>0):
                if(K>1):
                    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_left %= divisor
                        multiplies = multiplies * multiply_left % divisor
                        left += 2
                        flag_left=True

                    else:
                        multiply_right %= divisor
                        multiplies = multiplies * multiply_right % divisor
                        right -= 2
                        flag_left=False

                else:
                    multiplies = multiplies * list_a[right] % divisor
                    K =0
                    print(multiplies)
            print(multiplies)
        else:
            list_a = [ abs(list_a[i]) for i in range(N)]
            list_a.sort()
            for i in range(K-1):
                multiplies = multiplies * list_a[i] % divisor
            multiplies = (-1) * multiplies * list_a[K-1] % divisor

            print(multiplies)

Submission status: Wrong Answer

Solution code:
n,k=map(int, input().split())
a = list(map(int, input().split()))
mod=10**9+7
if n==k:
    ans=1
    for i in range(k):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()

minus=[i for i in a if i<0]
plus=[i for i in a if i>=0]

minus=sorted(minus)
plus=sorted(plus,reverse=True)
if k%2==1 and len(plus)==0:
    ans=1
    for i in range(k):
        ans*=abs(minus[-i-1])
        ans%=mod
    print((mod-ans)%mod)
    exit()

n_minus=len(minus)
n_plus=len(plus)

m_saiyo=0
for i in range(0, n_minus+1, 2): # i個minusから採用
    if i==0:
        continue
    if 0<=k-i<n_plus-1 and (minus[i-1]*minus[i-2])>=(plus[k-i]*plus[k-i+1]):
        m_saiyo=i

ans=1

if set(plus)=={0}:
    if m_saiyo==0:
        print(0)
        exit()

for i in range(m_saiyo):
    ans*=minus[i]
    ans%=mod
for i in range(k-m_saiyo):
    try:
        ans*=plus[i]
    except:
        ans*=minus[-(i-n_plus)-1]
    ans%=mod

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
lc = []
mod2 = 10**9+7
tmp = -1
m = 0

for i in A:
    if i == 0:
        pp = 0
    if i < 0:
        i *= -1
        lc.append([i,1])
        m += 1
    else:
        lc.append([i,0])
lc.sort(key=lambda x: x[0], reverse=True)
#print(lc)

ans = 1
cnt = 0
pl = []
if m == N and K%2 == 1:
    for i in range(K):
        ans *= -lc[N-i-1][0]
        ans %= mod2
    print(ans)
elif(N == K or m==N):
    for i in range(K):
        ans *= lc[i][0]
        ans %= mod2
        cnt += lc[i][1]
    if cnt%2 == 1:
        ans = -ans
    print(ans)
else:
    for i in range(N):
        if i < K-1:
            cnt += lc[i][1]
            if lc[i][1] == 1:
                tmp = i
        if(i >= K-1):
            if((cnt + lc[i][1])%2 == 0):
                if i == K-1:
                    tmp = -1
                for x in range(i+1):
                    if x != tmp:
                        ans *= lc[x][0]
                        ans %= mod2
                print(ans)
                break
            else:
                if(lc[i][1] == 0 and i >= K):
                    for x in range(i):
                        if x != tmp:
                            ans *= lc[x][0]
                            ans %= mod2
                    print(ans)
                    break

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
while count < K:
  if K - count >= 2:
    fo = A[i] * A[i + 1]
    re = A[j] * A[j - 1]
    #print(fo, re)
    if fo > re:
      ans *= (fo % mod) 
      ans %= mod
      i += 2
    elif (A[j - 1] < 1) or (A[j - 2] < 1):
      if (K % 2 == 0) and (A[j - 2] < 1):
        ans *= (re % mod)
        ans %= mod
        j -= 2
      else:  
        ans *= (fo % mod) 
        ans %= mod
        i += 2      
    else:
      ans *= (re % mod)
      ans %= mod
      j -= 2
    count += 2  
  else:
    count += 1
    ans *= A[j]
      
  #print(ans)
print(ans % mod)

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

pl = []
mn = []
zr = []

tmp = 1
cnt = 0

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

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

ans = 0

if len(mn) >= k and k % 2:
    tmp = 1
    for i in range(1, k+1):
        tmp *= mn[-i]
        tmp %= mod
    ans = -tmp

if len(zr) > 0:
    ans = max(0, ans)

pl_cum = [1]
for i, x in enumerate(pl):
    pl_cum.append(pl_cum[-1]*x % mod)

mn_cum = [1]
for i, x in enumerate(mn):
    mn_cum.append(mn_cum[-1]*x % mod)


for p in range(0, k+1, 2):
    if len(mn) < p:
        break
    first = False
    if len(pl) >= k-p:
        first = True
        pl_ind = k-p
        mn_ind = 0
        break

if not first:
    print(ans % mod)
    exit()

while pl_ind-2 > -1 and mn_ind+1 < len(mn):
    if pl[pl_ind-1]*pl[pl_ind-2] < mn[mn_ind]*mn[mn_ind+1]:
        pl_ind -= 2
        mn_ind += 2
    else:
        break

if pl_ind < 0:
    ans = mn_cum[mn_ind]
else:
    ans = pl_cum[pl_ind]*mn_cum[mn_ind]

print(ans % mod)

Submission status: Wrong Answer

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

A.sort()

def get_pos_num():
    lb = -1
    ub = N

    while ub - lb > 1:
        mid = (ub + lb) // 2
        if A[mid] > 0:
            ub = mid
        else:
            lb = mid

    return ub

def get_neg_num():
    lb = -1
    ub = N

    while ub - lb > 1:
        mid = (ub + lb) // 2
        if A[mid] >= 0:
            ub = mid
        else:
            lb = mid

    return lb

pos_num = get_pos_num()
neg_num = get_neg_num()
# A[0], A[1], ... , A[neg_num] <- negative number
# A[neg_num + 1], ..., A[pos_num - 1] <- 0
# A[pos_num], ..., A[N-1] <- positive number

neg_ind = 0
pos_ind = N-1
ans = 1

if (N-1) - neg_ind > K or K % 2 == 0:
    while K > 0:
        if K >= 2:
            if pos_ind < pos_num:
                pos_tmp = -1*INF
            else:
                pos_tmp = A[pos_ind]*A[pos_ind-1]

            if neg_ind > neg_num:
                neg_tmp = -1 * INF
            else:
                neg_tmp = A[neg_ind]*A[neg_ind+1]

            if pos_tmp == -1*INF and neg_tmp == -1*INF:
                ans = 0
                K = 0
                
            elif pos_tmp < neg_tmp:
                neg_ind += 2
                ans = (ans * neg_tmp + MOD) % MOD

                # ans *= neg_tmp
                K -= 2
            else:
                pos_ind -= 2
                ans = (ans * pos_tmp + MOD) % MOD

                # ans *= pos_tmp
                K -= 2
        
        else:
            ans = (ans * A[pos_ind] + MOD) % MOD
            # ans *= A[pos_ind]
            K -= 1
else:
    for i in range(K):
        ans = (ans * A[N-1-i] + MOD) % MOD
        # ans *= A[N-1-i]

print(ans)