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: Accepted

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

P = []
M = []
Z = []
for i in range(N):
    if A[i]>0:
        P.append(A[i])
    elif A[i]<0:
        M.append(A[i])
    else:
        Z.append(A[i])

mod = 1000000007

if len(P)+len(M) < K:
    print(0)
elif len(P)==0:
    if K%2==1:
        if len(Z)>0:
            print(0)
        else:
            M.sort(reverse=True)
            ans = 1
            for i in range(K):
                ans*=abs(M[i])
                ans%=mod
            if ans==0:
                print(ans)
            else:
                print(mod-ans)
    else:
        M.sort()
        ans = 1
        for i in range(K):
            ans*=abs(M[i])
            ans%=mod
        print(ans)
else:
    B = [(abs(A[i]),A[i]) for i in range(N)]
    B.sort(reverse=True,key=lambda x:x[0])
    pc = 0
    lastpc = -1
    mc = 0
    lastmc = -1
    for i in range(K):
        if B[i][1]>0:
            pc += 1
            lastpc = i
        else:
            mc += 1
            lastmc = i
    if mc%2==0:
        ans = 1
        for i in range(K):
            ans *= B[i][0]
            ans %= mod
        print(ans)
    else:
        nextpc = -1
        nextmc = -1
        for i in range(K,N):
            if B[i][1]>0:
                if nextpc==-1:
                    nextpc=i
            elif B[i][1]<0:
                if nextmc==-1:
                    nextmc=i
        if nextmc==-1 and nextpc==-1:
            if len(Z)>0:
                print(0)
            else:
                ans = 1
                for i in range(K):
                    ans *= B[i][0]
                    ans %= mod
                if ans==0:
                    print(ans)
                else:
                    print(mod-ans)
        elif nextmc==-1:
            ans = 1
            for i in range(K):
                if i!=lastmc:
                    ans *= B[i][0]
                    ans %= mod
            ans *= B[nextpc][0]
            ans %= mod
            print(ans)
        elif nextpc==-1:
            ans = 1
            for i in range(K):
                if i!=lastpc:
                    ans *= B[i][0]
                    ans %= mod
            ans *= B[nextmc][0]
            ans %= mod
            print(ans)
        else:
            if lastpc==-1:
                ans = 1
                for i in range(K):
                    if i!=lastmc:
                        ans *= B[i][0]
                        ans %= mod
                ans *= B[nextpc][0]
                ans %= mod
                print(ans)
            elif lastmc==-1:
                ans = 1
                for i in range(K):
                    if i!=lastpc:
                        ans *= B[i][0]
                        ans %= mod
                ans *= B[nextmc][0]
                ans %= mod
                print(ans)
            elif B[nextpc][0]*B[lastpc][0] > B[nextmc][0]*B[lastmc][0]:
                ans = 1
                for i in range(K):
                    if i!=lastmc:
                        ans *= B[i][0]
                        ans %= mod
                ans *= B[nextpc][0]
                ans %= mod
                print(ans)
            else:
                ans = 1
                for i in range(K):
                    if i!=lastpc:
                        ans *= B[i][0]
                        ans %= mod
                ans *= B[nextmc][0]
                ans %= mod
                print(ans)

Submission status: Accepted

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

plus = []
minus = []
zero = []
for i in range(n):
    if a[i] < 0:
        minus.append(abs(a[i]))
    elif a[i] > 0:
        plus.append(a[i])
    else:
        zero.append(0)


len_p = len(plus)
len_m = len(minus)
len_z = len(zero)

is_z = False
is_p = False
if len_z != 0:
    is_z = True

cnt = 2 * (len_m // 2) + len_p
if cnt >= k:
    is_p = True
if len_p == 0 and k % 2 == 1:
    is_p = False

if is_p:
    minus = sorted(minus, reverse=True)
    plus = sorted(plus, reverse=True)
    ans = 1
    if k % 2 == 1:
        k -= 1
        ans = plus[0]
        del plus[0]
    tmp = []
    for i in range(len(minus) // 2):
        tmp.append(minus[2 * i] * minus[2 * i + 1])
    for i in range(len(plus) // 2):
        tmp.append(plus[2 * i] * plus[2 * i + 1])
    tmp = sorted(tmp, reverse=True)
    for i in range(k // 2):
        ans *= tmp[i]
        ans %= MOD
    print(ans)
    exit()

elif is_z:
    print(0)
    exit()

else:
    for i in plus:
        minus.append(i)
    minus = sorted(minus)
    ans = -1
    for i in range(k):
        ans *= minus[i]
        ans %= MOD
    print(ans)
    exit()

Submission status: Accepted

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

if n == k:
    for x in a:
        ans *= x
        ans %= mod
    print(ans)
    exit()

b = []
c = []
for x in a:
    if 0 <= x:
        b += [x]
    else:
        c += [x]

if len(b) == 0 and k % 2 == 1:
    c.reverse()
    for i in range(k):
        ans *= c[i]
        ans %= mod
    print(ans)
    exit()

b.reverse()
bi = 0
ci = 0
bl = len(b)
cl = len(c)
if k % 2 == 1:
    ans *= b[0]
    bi += 1
    k -= 1
while k > 0:
    if bl-1 <= bi:
        ans *= c[ci] * c[ci+1]
        ans %= mod
        ci += 2
    elif cl-1 <= ci:
        ans *= b[bi] * b[bi + 1]
        ans %= mod
        bi += 2
    else:
        if b[bi] * b[bi + 1] < c[ci] * c[ci + 1]:
            ans *= c[ci] * c[ci + 1]
            ans %= mod
            ci += 2
        else:
            ans *= b[bi] * b[bi + 1]
            ans %= mod
            bi += 2
    k -= 2
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

def f(A, N, K):
    A.sort()
    I = (np.abs(A)).argsort()
    A = A[I][::-1]
    if N == K:
        return A
    # 全部負
    if np.all(A < 0):
        if K % 2 == 0:
            return A[:K]
        else:
            return A[-K:]
    # これ以外の場合は、必ず正を実現できる
    pos = A[A >= 0]
    neg = A[A < 0]
    nums = [1]
    if K & 1:
        nums = [pos[0]]
        pos = pos[1:]
        K -= 1
    # K は偶数
    # pos, neg から偶数個ずつセットにする
    if len(pos) & 1:
        pos = pos[:-1]
    if len(neg) & 1:
        neg = neg[:-1]
    pos = pos[::2] * pos[1::2]
    neg = neg[::2] * neg[1::2]
    A = np.concatenate([pos, neg])
    A.sort()
    A = A[::-1]
    return np.concatenate([nums, A[:K // 2]])

MOD = 10**9 + 7
B = f(A, N, K).tolist()
ans = 1
for x in B:
    ans = ans * x % MOD
print(ans)

Submission status: Accepted

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

positives = [a for a in A if a > 0]
negatives = [a for a in A if a < 0]
positive_cnt = len(positives)
negative_cnt = len(negatives)
zero_cnt = A.count(0)


if min(2 * (negative_cnt // 2), 2 * (K // 2)) + positive_cnt >= K:
    # 答えが正になる場合
    positives = sorted(positives, reverse=True)
    negatives = sorted(negatives)

    positives_twin = [positives[2 * i] * positives[2 * i + 1] for i in range(positive_cnt // 2)] + [0]
    negatives_twin = [negatives[2 * i] * negatives[2 * i + 1] for i in range(negative_cnt // 2)] + [0]
    positives_twin.sort()
    negatives_twin.sort()

    ans = 1
    positive_select = 0
    for i in range(K // 2):
        if positives_twin[-1] <= negatives_twin[-1]:
            ans *= negatives_twin[-1]
            ans %= MOD
            negatives_twin.pop()
        else:
            ans *= positives_twin[-1]
            ans %= MOD
            positives_twin.pop()
            positive_select += 1

    if K % 2 == 1:
        if K == 1:
            ans = positives[2 * positive_select]
        else:
            ans *= positives[2 * positive_select]
    print(ans % MOD)

elif zero_cnt > 0:
    # 答えが０になる場合
    print(0)
else:
    # 答えが負になる場合
    ans = 1
    A_abs = sorted([abs(a) for a in A])
    for a in A_abs[:K]:
        ans *= a
        ans %= MOD
    ans = -ans % MOD
    print(ans)

Submission status: Accepted

Solution code:
mod = 10**9 + 7

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

pos_cnt = sum(ai>=0 for ai in a)
neg_cnt = n-pos_cnt
if k-pos_cnt > 0 and (k-pos_cnt)%2 == 1 and (n==k or pos_cnt == 0):
    res = 1
    a.sort(reverse=True)
    for i in range(k):
        res *= a[i]
        res %= mod
    print(res)
    exit()

b = [(abs(ai), ai) for ai in a]
b.sort(reverse=True)
pos_top = []
neg_top = []
for i in range(k):
    _, ai = b[i]
    if ai >= 0:
        pos_top.append(ai)
    else:
        neg_top.append(ai)

pos_left = []
neg_left = []
for i in range(k, n):
    _, ai = b[i]
    if ai >= 0:
        pos_left.append(ai)
    else:
        neg_left.append(ai)

ans = 1
if len(neg_top)%2 == 0:
    for ai in pos_top:
        ans *= ai
        ans %= mod
    for ai in neg_top:
        ans *= ai
        ans %= mod
    print(ans)
    exit()

ans_tmp = []
if len(pos_left) > 0 and len(neg_top) > 0:
    pos_use = pos_left[0]
    neg_drop = neg_top[-1]
    pos_tmp = pos_top[:]
    pos_tmp.append(pos_use)
    neg_tmp = neg_top[:]
    neg_tmp.pop()
    res = 1
    for ai in pos_tmp:
        res *= ai
        res %= mod
    for ai in neg_tmp:
        res *= ai
        res %= mod
    ans_tmp.append([abs(pos_use/neg_drop), res])

if len(neg_left) > 0 and len(pos_top) > 0:
    neg_use = neg_left[0]
    pos_drop = pos_top[-1]
    pos_tmp = pos_top[:]
    pos_tmp.pop()
    neg_tmp = neg_top[:]
    neg_tmp.append(neg_use)
    res = 1
    for ai in pos_tmp:
        res *= ai
        res %= mod
    for ai in neg_tmp:
        res *= ai
        res %= mod
    ans_tmp.append([abs(neg_use/pos_drop), res])

ans_tmp.sort(reverse=True)
ans = ans_tmp[0][1]
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

MOD = 10 ** 9 + 7

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

A.sort()

n = bisect_left(A, 0) #負の数の個数
p = N - bisect_left(A, 0.5)
z = N - n - p

if K == 1: #一つだけ選ぶ-->最大の値を選べば良い
    print (A[-1] % MOD)
    exit()

if n + p < K: #正の数と負の数だけでは足りない-->必ず0になる　(0　を選ばざる得ない)
    print (0)
    exit()

i = 0 #負の数をどこから取るか
j = N - 1 #正の数をどこから取るか

if p >= 1: #正の数が一つ以上ある-->掛けた数を正に調整することができる
    if K % 2 == 0: #2つずつセット
        ans = 1
    else:
        ans = A[-1]
        j -= 1
        K -= 1
    
    k = K // 2
    for _ in range(k):
        if A[i] * A[i + 1] < A[j - 1] * A[j]:
            ans = (((ans * A[j - 1]) % MOD) * A[j]) % MOD
            j -= 2
        else:
            ans = (((ans * A[i]) % MOD) * A[i + 1]) % MOD
            i += 2
else:
    if K % 2 == 0: #正にすることができる -->最終的にプラスになるなら絶対値が大きいやつから使うべき
        ans = 1
        for i in range(K):
            ans = (ans * A[i]) % MOD
    else: #正にすることができない -->最終的にマイナスになるなら絶対値が小さいやつから使うべき
        ans = 1
        for i in range(K):
            ans = (ans * (A[N - 1 - i])) % MOD

print (ans % MOD)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
pos = []
neg = []
for v in A:
	if v >= 0: pos.append(v)
	else: neg.append(-v)

pos.sort(reverse=True)
neg.sort(reverse=True)

MOD = 10 ** 9 + 7
ppos = [1] * (len(pos)+1)
pneg = [1] * (len(neg)+1)

for i, v in enumerate(pos):
	ppos[i+1] = ppos[i] * v % MOD
for i, v in enumerate(neg):
	pneg[i+1] = pneg[i] * v % MOD

i = j = 0

while i + j < K:
	if i == len(pos): j += 1
	elif j == len(neg) or pos[i] >= neg[j]: i += 1
	else: j += 1

if j % 2 == 1:
	v = (-1, -1, -1)
	if i and j < len(neg):
		v = (neg[j-1] * neg[j], i-1, j+1)

	if i < len(pos) and j:
		v = max(v, (pos[i-1] * pos[i], i+1, j-1))

	if v[0] == -1:
		X = pos + neg
		X.sort()
		r = 1
		for v in X[:K]: r = r * v % MOD
		print(-r % MOD)
		raise SystemExit

	i, j = v[1:]

r = 1
for x in pos[:i]: r = r * x % MOD
for x in neg[:j]: r = r * x % MOD
print(r)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
it = lambda: list(map(int, input().strip().split()))

def solve():
    N, K = it()
    A = it()
    
    zero = 0
    neg = []
    pos = []
    for i in range(N):
        if A[i] < 0:
            neg.append(A[i])
        elif A[i] > 0:
            pos.append(A[i])
        else:
            zero += 1
    
    if not neg and not pos:
        return 0
    
    pos.sort()
    neg.sort(reverse=True)

    if not pos and K % 2 == 1:
        if zero > 0:
            return 0

        ans = 1
        for i in range(K):
            ans = ans * neg[i] % MOD
        return ans

    ans = 1
    for _ in range(K >> 1):
        if len(pos) >= 2 and len(neg) >= 2:
            if neg[-1] * neg[-2] >= pos[-1] * pos[-2]:
                ans = ans * neg.pop() % MOD * neg.pop() % MOD
            else:
                ans = ans * pos.pop() % MOD * pos.pop() % MOD
        elif len(pos) >= 2:
            ans = ans * pos.pop() % MOD * pos.pop() % MOD
        elif len(neg) >= 2:
            ans = ans * neg.pop() % MOD * neg.pop() % MOD
        elif len(pos) == 1 and len(neg) == 1:
            ans = ans * pos.pop() % MOD * neg.pop() % MOD
        else:
            return 0
    
    if K % 2 == 1:
        if pos:
            ans = ans * pos.pop() % MOD
        elif neg:
            ans = ans * neg.pop() % MOD
        else:
            return 0
    if zero > 1 and ans < 0:
        return 0
    return ans


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
*A, = map(int,input().split())

B = [a for a in A if a>=0]
B.sort()
C = [a for a in A if a<0]
C.sort(reverse = True)

ans = 1
MOD = 10**9+7

if len(B)==0 and K%2==1:
    C.sort()
    for _ in [0]*K:
        ans *= C.pop()
        ans %= MOD
    print(ans)
    exit()

if K==N:
    for a in A:
        ans = ans * a % MOD
    print(ans)
    exit()

while K>=2:
    if len(B)>=2 and len(C)>=2:
        if B[-1]*B[-2] > C[-1]*C[-2]:
            ans *= B.pop()*B.pop()%MOD
            ans %= MOD
            K -= 2
        else:
            ans *= C.pop()*C.pop()%MOD
            ans %= MOD
            K -= 2
    elif len(C)>=2:
        ans *= C.pop()*C.pop()%MOD
        ans %= MOD
        K -= 2
    else:
        ans *= B.pop()
        ans %= MOD
        K -=1
if K==1:
    ans *= B.pop()
    ans %= MOD

ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys

n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])

P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod

print(ans)

Submission status: Accepted

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

from collections import deque
a = list(map(int, input().split()))
a.sort()
minus, zero, plus = 0, 0, 0
for i in range(n):
    if a[i] < 0:
        minus += 1
    elif a[i] == 0:
        zero += 1
    else:
        plus += 1

que = deque(a)

plus_flg = False
if plus >= k:
    plus_flg = True
for i in range(plus+1):
    if (k - i) % 2 == 0 and (k - i) // 2 <= minus // 2:
        plus_flg = True
        break
#plus可能
if plus_flg:
    ans = 1
    cnt = 0 
    
    while cnt < k:
        if k - cnt >= 2:
            cnt += 2
            if que[0] * que[1] >= que[-1] * que[-2]:
                ans *= que.popleft()
                ans *= que.popleft()
                ans %= mod
            else:
                ans *= que.pop()
                ans *= que.pop()
                ans %= mod
        else:
            ans *= que.pop()
            ans %= mod
            cnt += 1

    print(ans)



#zero
elif zero > 0:
    print(0)

#minus
else:
    a = [abs(a[i]) for i in range(n)]
    a.sort()
    ans = 1
    for i in range(k):
        ans *= a[i]
        ans %= mod
    ans = -ans % mod
    print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n, k = na()
a = na()

neg = []
pos = []
for i in range(n):
    if a[i] < 0:
        neg.append(a[i])
    elif a[i] > 0:
        pos.append(a[i])
neg.sort()
pos.sort(reverse=True)

mx = -1
arg = -1
lall = 0

nn, np = 0, k
while np > len(pos):
    np -= 2
    nn += 2

if np >= 0 and nn <= len(neg):
    arg = nn
    while np-2 >= 0 and nn+1 < len(neg):
        if pos[np-1] * pos[np-2] < neg[nn] * neg[nn+1]:
            nn += 2
            np -= 2
            arg = nn
        else:
            break

ans = 1
mod = 1000000007
if arg == -1:
    a.sort(reverse=True)
    for i in range(k):
        ans = ans * a[i] % mod
    print(ans)
else:
    for i in range(arg):
        ans = ans * neg[i] % mod
    for i in range(k-arg):
        ans = ans * pos[i] % mod
    print(ans)

Submission status: Accepted

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

N, K = [int(_) for _ in input().split()]

A = [int(_) for _ in input().split()]
MOD = 10**9 + 7

Apos = sorted([el for el in A if el > 0], reverse=True)
Aneg = sorted([el for el in A if el <= 0])

Cpos = 0
Cneg = 0

answer = 1

# edge case to minimize negative
if K % 2 and len(Apos) == 0:
    Aneg = Aneg[::-1]
    for i in range(K):
        answer *= Aneg[i]
        answer %= MOD
else:
    while K > 0:
        if K % 2:
            if Cpos < len(Apos):
                answer *= Apos[Cpos]
                Cpos += 1
            else:
                answer *= Aneg[Cneg]
                Cneg += 1
            answer %= MOD
            K -= 1
        else:
            if Cpos + 1 >= len(Apos) and Cneg + 1 >= len(Aneg):
                answer *= Apos[Cpos] * Aneg[Cneg]
                Cpos += 1
                Cneg += 1
            elif Cpos + 1 >= len(Apos):
                answer *= Aneg[Cneg] * Aneg[Cneg + 1]
                Cneg += 2
            elif Cneg + 1 >= len(Aneg):
                answer *= Apos[Cpos] * Apos[Cpos + 1]
                Cpos += 2
            else:
                if Apos[Cpos] * Apos[Cpos+1] > Aneg[Cneg] * Aneg[Cneg+1]:
                    answer *= Apos[Cpos] * Apos[Cpos + 1]
                    Cpos += 2
                else:
                    answer *= Aneg[Cneg] * Aneg[Cneg + 1]
                    Cneg += 2
            K -= 2
            answer %= MOD
print(answer)

Submission status: Accepted

Solution code:
import sys


def solve(n, k, aaa):
    pos = []
    neg = []
    MOD = 10 ** 9 + 7
    for a in aaa:
        if a > 0:
            pos.append(a)
        elif a < 0:
            neg.append(a)
    if len(pos) + len(neg) < k:
        return 0
    if len(pos) == 0:
        if k % 2 == 1:
            if len(neg) < n:
                return 0
            neg.sort(reverse=True)
        else:
            neg.sort()
        ans = 1
        for a in neg[:k]:
            ans = ans * a % MOD
        return ans
    if len(pos) + len(neg) == k:
        if n > k and len(neg) % 2 == 1:
            return 0
        ans = 1
        for a in pos:
            ans = ans * a % MOD
        for a in neg:
            ans = ans * a % MOD
        return ans

    pos.sort()
    neg.sort(reverse=True)

    ans = 1
    r = k
    while r >= 2:
        if len(pos) <= 1:
            ans = ans * neg.pop() * neg.pop() % MOD
        elif len(neg) <= 1:
            ans = ans * pos.pop() * pos.pop() % MOD
        else:
            pm = pos[-1] * pos[-2]
            nm = neg[-1] * neg[-2]
            if pm > nm:
                ans = ans * pm % MOD
                pos.pop()
                pos.pop()
            else:
                ans = ans * nm % MOD
                neg.pop()
                neg.pop()
        r -= 2

    if r == 1:
        ans = ans * pos[-1] % MOD

    return ans


n, k, *aaa = map(int, sys.stdin.buffer.read().split())
print(solve(n, k, aaa))

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

N, K = map(int, input().split())
l = list(map(int, input().split()))
pos = []
neg = []
z = 0

for v in l:
    if v > 0:
        pos.append(v)
    elif v < 0:
        neg.append(v)
    else:
        z += 1
pos.sort()
neg.sort()

if N - z < K:
    print(0)
elif N - z == K:
    if len(neg) % 2 and z:
        print(0)
    else:
        out = 1
        for v in neg + pos:
            out *= v
            out %= 10 ** 9 + 7
        print(out)
elif len(pos) == 0:
    if K % 2:
        if z:
            print(0)
        else:
            neg.reverse()
            out = 1
            for i in range(K):
                out *= neg[i]
                out %= 10 ** 9 + 7
            print(out)
    else:
        out = 1
        for i in range(K):
            out *= neg[i]
            out %= 10 ** 9 + 7
        print(out)
else:
    out = 1
    neg.reverse()
    if K % 2:
        out = pos.pop()
        K -= 1
    while K:
        if len(pos) >= 2:
            nP = pos[-1] * pos[-2]
        else:
            nP = 0

        if len(neg) >= 2:
            nN = neg[-1] * neg[-2]
        else:
            nN = 0

        if nP > nN:
            pos.pop()
            pos.pop()
            out *= nP
        else:
            neg.pop()
            neg.pop()
            out *= nN
        out %= MOD
        K -= 2
    print(out)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = sorted([int(a) for a in input().split()], key = lambda x: -abs(x))
# print("A =", A)
P = 10 ** 9 + 7
m = 0
ans = 1
lp = 0
lm = 0
np = 0
nm = 0
for a in A[:K]:
    if a > 0:
        lp = a
        ans = ans * a % P
    elif a < 0:
        lm = a
        m ^= 1
        ans = ans * a % P
    else:
        print(0)
        exit()

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

for a in A[K:]:
    if a > 0:
        np = a
        break
for a in A[K:]:
    if a < 0:
        nm = a
        break

if lp and nm and lm and np:
    if lp * np > lm * nm:
        print(ans * pow(lm, P-2, P) * np % P)
    else:
        print(ans * pow(lp, P-2, P) * nm % P)
elif lp and nm:
    print(ans * pow(lp, P-2, P) * nm % P)
elif lm and np:
    print(ans * pow(lm, P-2, P) * np % P)
elif A[-1] == 0:
    print(0)
else:
    A = A[::-1][:K]
    ans = 1
    for a in A:
        ans = ans * a % P
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(-a)
pos = deque(sorted(pos))
neg = deque(sorted(neg))
mod = 10**9 + 7
ans = 1
sign = 1
if K % 2 == 1:
    if len(pos) > 0:
        ans = ans * pos.pop() % mod
    else:
        ans = ans * neg.popleft() % mod
        sign *= -1
    K -= 1
while K > 0:
    if len(pos) == 1 and len(neg) == 1:
        ans = ans * -neg.pop() * pos.pop() % mod
    elif sign == 1:
        if len(pos) < 2 or (len(neg) >= 2 and pos[-2] * pos[-1] < neg[-2] * neg[-1]):
            ans = ans * neg.pop() * neg.pop() % mod
        else:
            ans = ans * pos.pop() * pos.pop() % mod
    else:
        if len(pos) < 2 or (len(neg) >= 2 and pos[-2] * pos[-1] < neg[-2] * neg[-1]):
            ans = ans * neg.popleft() * neg.popleft() % mod
        else:
            ans = ans * pos.popleft() * pos.popleft() % mod
    K -= 2
ans = ans * sign % mod
print(ans)

Submission status: Runtime Error

Solution code:
from functools import reduce

N, K = map(int, input().split())
A = sorted(map(int, input().split()), key=abs, reverse=True)


def modmul_list(l):
    mod = 10**9+7
    modmul = lambda a, b: a*b%mod
    return reduce(modmul, l)

if K == N:    
    print(modmul_list(A))
elif all(a < 0 for a in A):
    A = list(reversed(A))
    print(modmul_list(A[:K]))
else:
    candidate, rest = A[:K], A[K:]
    if sum(c < 0 for c in candidate) % 2 == 0:
        print(modmul_list(candidate))
    else:
        if all(r > 0 for r in rest):
            c_negmax = max(c for c in candidate if c < 0)
            candidate.remove(c_negmax)
            candidate.append(rest[0])
        elif all(r < 0 for r in rest):
            c_posmin = min(c for c in candidate if c > 0)
            candidate.remove(c_posmin)
            candidate.append(rest[0])
        else:
            c_posmin = min(c for c in candidate if c > 0)
            c_negmax = max(c for c in candidate if c < 0)
            r_posmax = max(r for r in rest if r > 0)
            r_negmin = min(r for r in rest if r < 0)
            if c_posmin * r_negmin > c_negmax * r_posmax:
                candidate.remove(c_negmax)
                candidate.append(r_posmax)
            else:
                candidate.remove(c_posmin)
                candidate.append(r_negmin)

        print(modmul_list(candidate))

Submission status: Runtime Error

Solution code:
from collections import deque
rand = False
verbose = False

if rand:
    import random
    N, K = 200000, 10000
    A = random.choices(range(-10**9, 10**9), k=N)
else:
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

MOD = 10**9 + 7

def mul(A):
    ret = 1
    for i in range(len(A)):
        ret = (ret * A[i]) % MOD
#        print (ret)
    return ret

if K==N:
    print(mul(A))
    exit()

POS, NEG = list(), list()
for i in range(len(A)):
    if A[i] < 0:
        NEG.append(A[i])
    else:
        POS.append(A[i])

POS.sort(reverse=True)
NEG.sort()

if len(POS)==0 and K%2==1: # must go negative
    print(mul(NEG[-K:]))
    exit()

POS = deque(POS)
NEG = deque(NEG)

ans = list()
while len(ans)<K:
    if len(NEG) <= 1:
        if verbose: print('no more neg numbers')
        ans.append(POS.popleft()) # no negative numbers to add
    elif len(POS) <= 1:
        if verbose: print('no more pos numbers')
        if K-len(ans)>=2:
            ans.append(NEG.popleft())
        else:
            ans.append(POS.popleft())
    elif POS[0]*POS[1] > NEG[0]*NEG[1] or K-len(ans)==1:
        if verbose: print('pos bigger')
        ans.append(POS.popleft())
    else:
        if verbose: print('neg biger')
        ans.append(NEG.popleft())
        ans.append(NEG.popleft())

print(mul(ans))

Submission status: Runtime Error

Solution code:

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

MOD = 10**9 + 7

def mul(A):
    ret = 1
    for i in range(len(A)): ret = ret * A[i] % MOD
    return ret

if K==N:
    print(mul(A))
    exit()

POS, NEG = list(), list()
for i in range(len(A)):
    if A[i] < 0:
        NEG.append(A[i])
    else:
        POS.append(A[i])

POS.sort(reverse=True)
NEG.sort()

if len(POS)==0 and K%2==1: # must go negative
    print(mul(NEG[-K:]))
    exit()

ans = list()
while len(ans)<K:
    if len(NEG) <= 1:
        ans.append(POS.pop()) # no negative numbers to add
    elif len(POS) <= 1:
        if K-len(ans)>=2:
            ans.append(NEG[:K-len(ans)])
        else:
            ans.append(POS.pop())
    elif POS[0]*POS[1] > NEG[0]*NEG[1] or K-len(ans)==1:
        ans.append(POS.pop())
    else:
        ans.append(NEG.pop())
        ans.append(NEG.pop())

print(mul(ans))

Submission status: Runtime Error

Solution code:
from sys import stdin

input = stdin.readline
MOD = 10 ** 9 + 7


def solve():
    N, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(key=abs, reverse=True)
    noneg = 1
    res = 1
    i = 0
    platest = -1
    nlatest = -1
    ind = set()
    while i < k:
        if a[i] > 0:
            ind.add(i)
            platest = i
        elif a[i] < 0:
            if noneg:
                noneg = 0
                nlatest = i
            else:
                noneg = 1
                ind |= {nlatest, i}
        i += 1
    if not noneg:
        pnext = -1
        nnext = -1
        while i < N and (pnext == -1 or nnext == -1):
            if a[i] > 0 and pnext == -1:
                pnext = i
            elif a[i] < 0 and nnext == -1:
                nnext = i
            i += 1
        t1 = float('-inf')
        t2 = float('-inf')
        if platest != -1 and nnext != -1:
            t1 = abs(a[nnext]) / a[platest]
        if pnext != -1:
            t2 = a[pnext] / abs(a[nlatest])
        else:
            if a[-1] == 0:
                print(0)
                return
            else:
                res = 1
                for i in range(N-1,N-k-1,-1):
                    res *= a[i]
                    res %= MOD
                print(res)
                return
        if t1 >= t2:
            ind.discard(platest)
            ind.add(a[nnext])
        else:
            ind.discard(nlatest)
            ind.add(a[pnext])
        res = 1
    for i in ind:
        res *= a[i]
        res %= MOD
    print(res)



if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

if all(i <= 0 for i in a):
    for i in range(k):
        res = (res*a[i])%mod
else:
    right = n-1
    left = 0
    while k > 1:
        if a[right]*a[right-1] < a[left]*a[left+1]:
            res = (res*a[left]*a[left+1])%mod
            left += 2
        else:
            res = (res*a[right]*a[right-1])%mod
            right += 2
        k -= 2
    if k == 1:
        res = (res*max(a[left:right+1]))%mod
print(res)