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 numpy as np
import sys
n,k = map(int,input().split())
a_list = sorted(map(int,input().split()))
mod = 10**9+7
if n-k < a_list.count(0):
    print(0)
    exit()
if (sum([1 for a in a_list if np.sign(a)!=-1])==0 and k%2==1) or (k==n and len([1 for a in a_list if np.sign(a)==-1])%2==1):
    a_list.sort(key = abs)
    ans = 1
    for num in a_list[:k]:
        ans *= num
        ans %= mod
    print(ans)
    exit()
else:
    a_list.sort(key = abs,reverse = True)
    add = 1
    remove = 1
    if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
        negative_big = [num for num in a_list[:k] if np.sign(num)==-1]
        positive_big = [num for num in a_list[:k] if np.sign(num)!=1]
        negative_small = [num for num in a_list[k:] if np.sign(num)==-1]
        positive_small = [num for num in a_list[k:] if np.sign(num)!=-1]
        
        
        if len(negative_big)==0 or len(positive_small)==0:
            remove = min(positive_big)
            add = min(negative_small)
        elif len(positive_big)==0 or len(negative_small)==0:
            remove = max(negative_big)
            add = max(positive_small)
        else:
            positive_small_max = max(positive_small)
            negative_big_max = max(negative_big)
            negative_small_min = min(negative_small)
            positive_big_min = min(positive_big)
            if positive_small_max/negative_big_max < negative_small_min/positive_big_min:
                remove = negative_big_max
                add = positive_small_max
            else:
                remove = positive_big_min
                add = negative_small_min
ans = 1
for num in a_list[:k]:
    ans *= num
    ans %= mod
    
if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
    ans *= add
    ans %= mod
    ans *= pow(remove, mod-2, mod)
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

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

    # もしN = K なら全部選択しないといけないので、
    # 全部掛け算して返す
    if N == K:
        ans = 1
        for a in A:
            ans = (ans * a) % MOD
        print(ans)
        return

    Ap = [] # 正の数だけ入っている
    Am = [] # 負の数だけ入っている.値は絶対値で入れる
    has0 = False # 0がAの中にあるか
    for a in A:
        if a == 0:
            has0 = True
        elif a > 0:
            Ap.append(a)
        else:
            Am.append(-a)

    # それぞれを絶対値の大きい順に並べる
    Ap.sort(reverse=True)
    Am.sort(reverse=True)

    ip = 0
    im = 0
    lp = len(Ap)
    lm = len(Am)

    # もし0でない数がK個未満しかない場合、0を必ず選ばないといけないので
    # 答えは0になる
    if lp + lm < K:
        print(0)
        return

    # 正の数+負の数=K かつ負の数が奇数のとき、0を選んだほうがマシなので、
    # 答えは0になる
    if lp + lm == K and lm % 2 == 1:
        print(0)
        return 
    # もしKが奇数のときで、かつ正の数が1個もない時
    if K % 2 == 1 and lp == 0:
        # 0があるなら0にする
        if has0:
            print(0)
            return
        # 0がない場合は、負の数の中から絶対値の小さいものを選ぶ
        else:
            ans = 1
            for a in Am[-K:]:
                ans = (ans * a) % MOD
            print(MOD - ans)
            return

    # 戦略: Aの中から絶対値の大きい順に選んでいく
    ans = 1
    for i in range(K):
        x = 1
        if ip == lp: # 正の数をこれ以上選べないのであれば負の数を選ぶ
            x = Am[im]
            im += 1
        elif im == lm: # 負の数をこれ以上選べないのであれば正の数を選ぶ
            x = Ap[ip]
            ip += 1
        # 正の数、負の数どちらも選べるのであれば、絶対値の大きいほうを選ぶ
        elif Am[im] < Ap[ip]:
            x = Ap[ip]
            ip += 1
        else:
            x = Am[im]
            im += 1
        
        ans = ans * x % MOD

    # もし絶対値の大きい順で選んで、負の数を奇数個選んでいたとき
    if im % 2 == 1:
        # 選んだ中で一番小さい負の数を外して、まだ選んでない中で最も大きい正の数を入れるか、
        # 選んだ中で一番小さい正の数を外して、まだ選んでない中で最も（絶対値が）大きい負の数を入れるか選ぶ

        # これ以上0でない数がない場合は、0を選択して答えを0にするのが最大値になる
        if ip == lp and im == lm:
            print(0)
            return
        # 正の数をこれ以上選べない場合は負の数から選ぶ
        elif ip == lp:
            ans = ans * modinv(Ap[ip-1]) % MOD
            ans = ans * Am[im] % MOD
        # 負の数をこれ以上選べない場合は正の数から選ぶ
        elif im == lm:
            ans = ans * modinv(Am[im-1]) % MOD
            ans = ans * Ap[ip] % MOD
        # 正、負ともまだ選ぶ余裕がある場合
        else:
            # 一旦、選んだ中で一番小さい負の数と、選んだ中で一番小さい正の数を戻す（再度選べるようにする）
            if ip > 0:
                ans = ans * modinv(Ap[ip]) % MOD
                ip -= 1
            if im > 0:
                ans = ans * modinv(Am[im]) % MOD
                im -= 1
            # 正、負のリストから、まだ選んでない中で絶対値が大きいもの2つを選び、その積の大きいほうを選ぶ
            a = Ap[ip] * Ap[ip+1]
            b = Am[im] * Am[im+1]

            ans = ans * max(a, b) % MOD

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    M=10**9+7
    n,k,*a=map(int,open(0).read().split())
    x,y=[],[]
    for i in a:
        if i>0:x+=i,
        if i<0:y+=i,
    if len(x)+len(y)<k or k%2 and not x and len(y)<n:
        print(0)
        return
    if k%2 and not x:
        c=1
        for i in sorted(y)[-k:]:
            c=c*i%M
        print(c)
        return
    x=sorted(x)[::-1][:k]
    i=len(x)
    y.sort()
    m=len(y)
    j=k-i
    if j%2:
        x=x[:-1]
        i-=1
        j+=1
    x+=y[:j]
    if len(x)!=k:
        print(0)
        return
    while i>1 and j+1<m and x[i-1]*x[i-2]<y[j]*y[j+1]:
        x[i-1],x[i-2]=y[j],y[j+1]
        i-=2
        j+=2
    c=1
    for i in x:
        c=c*i%M
    print(c)
main()

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, K = MAP()
A = LIST()

if N == K:
	ans = 1
	for x in A:
		ans = ans*x%mod
	print(ans)
	exit()

a = []
for x in A:
	flg = 0
	if x < 0:
		flg = 1
	a.append([x, abs(x), flg])

a.sort(key = lambda x: -x[1])

#print(a)

flg_sum = sum([x[2] for x in a[:K]])

if flg_sum%2 == 0:
	ans = 1
	for x in a[:K]:
		ans = ans*x[1]%mod
	print(ans)
	exit()

flg = a[K-1][2]
s0 = 0
s1 = INF
for i in range(K, N):
	if a[i][2] != flg:
		s0 = a[K-1][1]
		s1 = a[i][1]
		break

flg = a[K][2]
t0 = 0
t1 = INF
for i in range(K-1, -1, -1):
	if a[i][2] != flg:
		t0 = a[i][1]
		t1 = a[K][1]
		break

if t0 + s0 != 0:
	ans = 1
	if s1*t0 >= s0*t0:
		for i in range(K-1):
			ans = ans*a[i][1]%mod
		print(ans*s1%mod)
		exit()
	else:
		for i in range(K):
			if a[i][1] != t0:
				ans = ans*a[i][1]%mod
		print(ans*t1%mod)
		exit()

ans = 1
for x in a[::-1][:K]:
	ans = ans*x[0]%mod

print(ans)

Submission status: Wrong Answer

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

plus = []
minus = []

for i in a:
	if i >= 0:
		plus.append(i)
	else:
		minus.append(i)

plus.sort(key=lambda x:-x)
minus.sort()

#print(plus, minus)

"""
貪欲チックに求める
numplus … 前からnumplus番目まで掛け合わせる
numminus … 前からnumminus番目まで掛け合わせる

入力例2に合わせるのは場合分けが必要だが, minusは2個単位で管理する.
"""
numplus = k
numminus = 0

"""
kがplusを超える場合, うまく処理ができないのでリスト参照できる範囲まで下げる.
"""
while numplus > len(plus):
	numplus -= 2
	numminus += 2

tmpminus = -1

#print(numplus, numminus)

while numplus-1 >= 0 and numminus+1 < len(minus):
	if plus[numplus-1] * plus[numplus-2] <= minus[numminus] * minus[numminus+1]:
		numplus -= 2
		numminus += 2
		tmpplus = numplus
	else:
		break

#print(tmpminus, tmpplus)

ans = 1
if tmpminus != -1:
	for i in range(numplus):
		ans = ans * plus[i] % mod
	for i in range(numminus):
		ans = ans * minus[i] % mod
else:
	"""
	これは, ansが負になる場合や, minusが1個だけの場合, minusしかない場合, plusしかない場合に使える.
	"""
	#print("ここに来ました！")
	tmp = sorted(a, key=lambda x:-x)
	for i in range(k):
		ans = ans*tmp[i]%mod

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

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

if N==K:
    T=1
    for a in A:
        T=(T*a)%M
    print(T)
    sys.exit()
elif max(A)<0 and K%2==1:
    A.sort(reverse=True)
    T=1
    for i in range(K):
         T=(T*A[i])%M
    print(T)
    sys.exit()
    
U=list(map(lambda x:max(x,0),A))
U.sort(reverse=True)
U=deque(U)

V=list(map(lambda x:min(x,0),A))
V.sort()
V=deque(V)

T=1
Y=0
while Y<K:
    x1,x2=U[0],U[1]
    y1,y2=V[0],V[1]

    if Y==K or x1*x2>=y1*y2:
        Y+=1
        T=(T*x1)%M
        _=U.popleft()
        U.append(0)
    else:
        Y+=2
        T=(T*y1*y2)%M
        _=V.popleft()
        _=V.popleft()
        V.append(0)
        V.append(0)
print(T)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def main():
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    ans = modint(1)
    if N == K:
        for a in A:
            ans *= a
        return print(ans)
    elif all(a < 0 for a in A) and K % 2 == 1:
        A.sort(key=abs)
        for a in A[:K]:
            ans *= a
        return print(ans)
    # 以降，非負の答えにできる
    A.sort(reverse=True, key=abs)
    if sum(a < 0 for a in A[:K]) % 2 == 0:
        for a in A[:K]:
            ans *= a
    else:
        ans1 = modint(1)  # 正を取り除く
        ans2 = modint(1)  # 負を取り除く
        p_remove = False
        x1 = -1
        for a in A[:K][::-1]:
            if a > 0 and not p_remove:
                p_remove = True
                x1 = a
                continue
            ans1 *= a
        n_remove = False
        x2 = -1
        for a in A[:K][::-1]:
            if a < 0 and not n_remove:
                n_remove = True
                x2 = a
                continue
            ans2 *= a
        y1 = 0  # 一番大きい負
        y2 = 0  # 一番大きい正
        for a in A[K:]:
            if y1 == 0 and a < 0:
                y1 = a
            if y2 == 0 and a > 0:
                y2 = a
            if y1 != 0 and y2 != 0:
                break
        ans1 *= y1
        ans2 *= y2
        if abs(x2*y1) <= abs(x1*y2):
            ans = ans2
        else:
            ans = ans1
    print(ans)


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

Am, Ap = [], []
pm = [0, 0]

for x in A:
  if x < 0:
    Am.append(-x)
    pm[0] += 1
  else:
    Ap.append(x)
    pm[1] += 1

Bm = list(zip(Am, [1]*pm[0]))
Bp = list(zip(Ap, [0]*pm[1]))
B = Bm + Bp
ans = 1
cnt = 0

if pm[0] == N and K%2 == 1:
  for i in range(K):
    ans *= B[i][0]
    ans %= mod
    ans *= (-1)
  print(ans)
  exit()

B.sort(reverse = True)  

for i in range(K):
  ans *= B[i][0]
  ans %= mod
  cnt ^= B[i][1]

if cnt == 0:
  print(ans)
  exit()

amcnt, apcnt, rmcnt, rpcnt = 0, 0, 0, 0  

ans1, ans2 = ans, ans

for i in range(K+1, N):
  if B[i][1] == 1:
    amcnt += 1
    ans1 *= B[i][0]
    ans1 %= mod
    break

for i in range(K+1, N):
  if B[i][1] == 0:
    apcnt += 1
    ans2 *= B[i][0]
    ans2 %= mod
    break

for i in range(K-1, -1, -1):
  if B[i][1] == 1:
    rmcnt += 1
    r = pow(B[i][0], mod-2, mod)
    ans2 *= r
    ans2 %= mod
    break

for i in range(K-1, -1, -1):
  if B[i][1] == 0:
    rpcnt += 1
    r = pow(B[i][0], mod-2, mod)
    ans1 *= r
    ans1 %= mod
    break

Flag1 = (amcnt + rpcnt) % 2
Flag2 = (apcnt + rmcnt) % 2

if Flag1 == 0 and Flag2 == 0:
  print(max(ans1, ans2))
elif Flag1 == 0:
  print(ans1)
else:
  print(ans2)

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
import bisect
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,K = LI()
AS=LI()
AS.sort(reverse=True)
res = 1
if AS[0] >= 0 and AS[N-1] >= 0:
    for i in range(K):
        res *= AS[i]
        res %= DVSR
elif AS[0] > 0:
    if N != K:
        AS.reverse()
        POS = bisect.bisect_left(AS, 1)
        AS2 = AS[POS:N]
        AS2.reverse()
        ACC = [1] * (len(AS2) + 1)
        for i in range(len(AS2)):
            ACC[i+1] = ACC[i]*AS2[i]
            # ACC[i+1] %= DVSR

        BS = []
        for i in range(0, POS//2):
            BS.append(AS[i]*AS[i+1])
        BS.sort(reverse=True)

        BCC = [1]*(len(BS)+1)
        res = 1
        for i in range(len(BS)):
            BCC[i+1] = BS[i]*BCC[i]
            # BCC[i+1] %= DVSR

        for i in range(min(K//2+1, len(BCC))):
            if K-2*i < len(ACC):
                res = max(BCC[i]*ACC[K-2*i], res)
    else:
        for i in range(N):
            res *= AS[i]
            res %= DVSR

else: # AS[0] <= 0
    if K % 2:
        v1 = 1
        v2 = 1
        for i in range(K):
            v1 *= AS[i]
            v1 %= DVSR
        res = v1
    else:
        res = 1
        for i in range(N-K, N):
            res *= AS[i]
            res %= DVSR

print(res%DVSR)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def main():
    from collections import Counter
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    ans = modint(1)
    if N == K:
        for a in A:
            ans *= a
        return print(ans)
    elif all(a < 0 for a in A) and K % 2 == 1:
        A.sort(key=abs)
        for a in A[:K]:
            ans *= a
        return print(ans)
    # 以降，非負の答えにできる
    if sum(a < 0 for a in A[:K]) % 2 == 0:
        A.sort(key=abs)
        for a in A[:K]:
            ans *= a
    else:
        ans1 = modint(1)  # 正を取り除く
        ans2 = modint(1)  # 負を取り除く
        p_remove = False
        x1 = -1
        for a in A[:K][::-1]:
            if a > 0 and not p_remove:
                p_remove = True
                x1 = a
                continue
            ans1 *= a
        n_remove = False
        x2 = -1
        for a in A[:K][::-1]:
            if a < 0 and not n_remove:
                n_remove = True
                x2 = a
                continue
            ans2 *= a
        y1 = 0  # 一番大きい負
        y2 = 0  # 一番大きい正
        for a in A[K:]:
            if y1 == 0 and a < 0:
                y1 = a
            if y2 == 0 and a > 0:
                y2 = a
            if y1 != 0 and y2 != 0:
                break
        ans1 *= y1
        ans2 *= y2
        if abs(x2*y1) <= abs(x1*y2):
            ans = ans2
        else:
            ans = ans1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, k = (int(x) for x in input().split())
A = list(int(x) for x in input().split())
MOD = 10**9 + 7
P = []
M = []
Z = []
for a in A:
    if a < 0:
        M.append(a)
    elif a > 0:
        P.append(a)
    else:
        Z.append(a)
P.sort()
M.sort(reverse=True)
lp = len(P)
lm = len(M)
lz = len(Z)

# どうしてもマイナスになるとき
if (lp + lm < k) or (lm == n and k % 2 == 1):
    if lz > 0:
        print(0)
        exit()
    else:
        tmp = 1
        M.sort(reverse=True)
        for m in M[:k]:
            tmp *= -m
            tmp %= MOD
        if tmp == 0:
            print(0)
        else:
            print(-tmp % MOD)
        exit()

# プラスにできそうなとき
ans = 1
pindex = lp - 1
mindex = lm - 1
for _ in range(k // 2):
    if pindex > 0 and mindex > 0:
        p = P[pindex] * P[pindex - 1]
        m = M[mindex] * M[mindex - 1]
        if p > m:
            ans *= p
            ans %= MOD
            pindex -= 2
        else:
            ans *= m
            ans %= MOD
            mindex -= 2
    else:
        if pindex > 0:
            ans *= P[pindex] * P[pindex - 1]
            ans %= MOD
            pindex -= 2
        elif mindex > 0:
            ans *= M[mindex] * M[mindex - 1]
            ans %= MOD
            mindex -= 2

if k % 2 == 0:
    print(ans)
    exit()
else:
    if pindex >= 0:
        ans *= P[pindex]
        ans %= MOD
        print(ans)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
n, k = (int(x) for x in input().split())
A = list(int(x) for x in input().split())
MOD = 10**9 + 7
P = []
M = []
Z = []
for a in A:
    if a < 0:
        M.append(a)
    elif a > 0:
        P.append(a)
    else:
        Z.append(a)
P.sort()
M.sort(reverse=True)
lp = len(P)
lm = len(M)
lz = len(Z)

# どうしてもマイナスになるとき
if (lp + lm < k) or (lm == n and k % 2 == 1):
    if lz > 0:
        print(0)
        exit()
    else:
        tmp = 1
        M.sort(reverse=True)
        for m in M[:k]:
            tmp *= -m
            tmp %= MOD
        if tmp == 0:
            print(0)
        else:
            print(MOD - tmp)
        exit()

# プラスにできそうなとき
ans = 1
pindex = lp-1
mindex = lm-1
for _ in range(k // 2):
    if pindex > 0 and mindex > 0:
        p = P[pindex] * P[pindex - 1]
        m = M[mindex] * M[mindex - 1]
        if p > m:
            ans *= p
            ans %= MOD
            pindex -= 2
        else:
            ans *= m
            ans %= MOD
            mindex -= 2
    else:
        if pindex > 0:
            ans *= P[pindex] * P[pindex - 1]
            ans %= MOD
            pindex -= 2
        elif mindex > 0:
            ans *= M[mindex] * M[mindex - 1]
            ans %= MOD
            mindex -= 2

if k % 2 == 0:
    print(ans)
    exit()
else:
    if pindex >= 0:
        ans *= P[pindex]
        ans %= MOD
        print(ans)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
#import numba

def run():
    N, K = list(map(int, input().split()))
    A = list(map(int, sysread().split()))
    mod = 10 ** 9 + 7

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

    plus = sorted(plus, reverse=True)
    minus = sorted(minus, reverse=True)

    P, M  = [1], [1]
    for p in plus:
        P.append((P[-1] * p) % mod)
    for m in minus:
        M.append(((M[-1] * (-m)) % mod))
    #print(P, M)
    max_ans = -1

    for i in range(K, -1, -2):
        if len(plus) < i:continue
        if len(minus) < K - i:continue
        if max_ans == -1:
            max_ans = P[i] * M[K-i] % mod
        else:
            if not plus[i] or not plus[i + 1]:
                max_ans = max(max_ans, 0)
                break
            if plus[i+1] / minus[K-i-2] < minus[K-i-3] / plus[i]:
                max_ans = P[i] * M[K-i] % mod

    if max_ans == -1:
        plus = plus[::-1]
        minus = minus[::-1]
        P, M = [1], [1]
        for p in plus:
            P.append((P[-1] * p) % mod)
        for m in minus:
            M.append(((M[-1] * (-m)) % mod))

        for i in range(K-1, -1, -2):
            if len(plus) < i: continue
            if len(minus) < K - i: continue
            if max_ans == -1:
                max_ans = P[i] * M[K - i] % mod
            else:
                if not plus[i] or not plus[i+1]:
                    max_ans = 0
                    break
                if plus[i + 1] / minus[K - i - 2] > minus[K - i - 3] / plus[i]:
                    max_ans = P[i] * M[K - i] % mod

    print(max_ans)

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

U=list(map(lambda x:max(x,0),A))
U.sort(reverse=True)
U=deque(U)

V=list(map(lambda x:min(x,0),A))
V.sort()
V=deque(V)

T=1
Y=0
while Y<K:
    x1,x2=U[0],U[1]
    y1,y2=V[0],V[1]

    if Y==K or x1*x2>=y1*y2:
        Y+=1
        T=(T*x1)%M
        _=U.popleft()
        U.append(0)
    else:
        Y+=2
        T=(T*y1*y2)%M
        _=V.popleft()
        _=V.popleft()
        V.append(0)
        V.append(0)
print(T)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
n,k = map(int,input().split())
a_list = sorted(map(int,input().split()))
mod = 10**9+7
if n-k < a_list.count(0):
    print(0)
    exit()
if (sum([1 for a in a_list if np.sign(a)!=-1])==0 and k%2==1) or (k==n and len([1 for a in a_list if np.sign(a)==-1])%2==1):
    a_list.sort(key = abs)
    ans = 1
    for num in a_list[:k]:
        ans *= num
        ans %= mod
    print(ans)
    exit()
else:
    a_list.sort(key = abs,reverse = True)
    add = 1
    remove = 1
    if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
        negative_big = [num for num in a_list[:k] if np.sign(num)==-1]
        positive_big = [num for num in a_list[:k] if np.sign(num)==1]
        negative_small = [num for num in a_list[k:] if np.sign(num)==-1]
        positive_small = [num for num in a_list[k:] if np.sign(num)!=-1]
        
        
        if len(negative_big)==0 or len(positive_small)==0:
            remove = min(positive_big)
            add = min(negative_small)
        elif len(positive_big)==0 or len(negative_small)==0:
            remove = max(negative_big)
            add = max(positive_small)
        else:
            positive_small_max = max(positive_small)
            negative_big_max = max(negative_big)
            negative_small_min = min(negative_small)
            positive_big_min = min(positive_big)
            if positive_small_max/negative_big_max < negative_small_min/positive_big_min:
                remove = negative_big_max
                add = positive_small_max
            else:
                remove = positive_big_min
                add = negative_small_min
ans = 1
for num in a_list[:k]:
    ans *= num
    ans %= mod
    
if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
    ans *= add
    ans %= mod
    ans *= pow(remove, mod-2, mod)
    ans %= mod

print(ans)

Submission status: Wrong Answer

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

plst=sorted([x for x in lst if x>=0],reverse=True)
nlst=sorted([abs(x) for x in lst if x<0],reverse=True)
out=[None for _ in range(k)]
lenn=len(nlst)
lenp=len(plst)



if lenp==0 and k%2==1:
    sm=1
    for i in range(lenn-1,lenn-k-1,-1):
        sm*=-nlst[i]
        sm%=mod
    print(sm)
    exit()


ptoken=0
ntoken=0
token=0
pm=0



while token<k:
    if ptoken==lenp:
        out[token]=nlst[ntoken]
        pm=(pm+1)%2
        ntoken+=1
    elif ntoken==lenn:
        out[token]=plst[ptoken]
        ptoken+=1
    elif plst[ptoken]>nlst[ntoken]:
        out[token]=plst[ptoken]
        ptoken+=1
    else :
        out[token]=nlst[ntoken]
        pm=(pm+1)%2
        ntoken+=1
    token+=1

if pm==1:
    if n!=k:
        if ptoken==lenp:          
            out.remove(plst[ptoken-1])
            out.append(nlst[ntoken])
        elif ntoken==lenn:
            out.remove(nlst[ntoken-1])
            out.append(plst[ptoken])
        elif ptoken==0 : 
            out.remove(nlst[ntoken-1])
            out.append(plst[ptoken])
        else : 
            if nlst[ntoken-1]*nlst[ntoken]>=plst[ptoken-1]*plst[ptoken]:
                out.remove(plst[ptoken-1])
                out.append(nlst[ntoken])
            else :
                out.remove(nlst[ntoken-1])
                out.append(plst[ptoken])               

sm=1
for x in out:
    sm*=x
    sm%=mod

print(sm)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
modulo = 10 ** 9 + 7
*arr, = map(int, input().split())
inverses = [pow(v, modulo - 2, modulo) for v in arr]
neg_cnt = 0
for v in arr:
    if v < 0:
        neg_cnt += 1


def min_pos(arr):
    pass


if neg_cnt == n:
    res = 1
    arr.sort(reverse=True)
    for i in range(k):
        res *= arr[i]
        res %= modulo
    print(res)
elif k == n:
    res = 1
    for v in arr:
        res *= v
        res %= modulo
    print(res)
else:
    pos = []
    neg = []
    for i, v in enumerate(arr):
        if v < 0:
            neg.append(i)
        else:
            pos.append(i)

    neg.sort(key=lambda v: abs(arr[i]))
    pos.sort(key=lambda v: abs(arr[i]))

    if k % 2:
        res = arr[pos[0]] % modulo
        i = 1
    else:
        res = 1
        i = 0
    j = 0
    while i < len(pos) - 1 and j < len(neg) - 1 and i + j < k:
        if j == len(pos) or i < len(pos) and arr[pos[i]] * arr[pos[i + 1]] > arr[neg[j]] * arr[neg[j + 1]]:
            res *= arr[pos[i]]
            res *= arr[pos[i + 1]]
            i += 2
        else:
            res *= arr[neg[j]]
            res *= arr[neg[j + 1]]
            j += 2
        res %= modulo

    print(res)