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:
def prod(l):
    r = 1
    mod = 10 ** 9 + 7
    for a in l:
        r = (r * a) % mod
    return r

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    P = [a for a in A if a >=0]
    M = [a for a in A if a < 0]
    PP, MM = len(P), len(M)
    P.sort(reverse=True)
    M.sort()
    k = 0
    p, m = 0, 0
    if PP == 0:
        if K % 2 == 0:
            return prod(M[:K])
        return prod(M[-K:])
    if P[0] == 0 and K % 2 == 1:
        return 0
    while p + m < K:
        if m == MM:
            p += 1
        elif p == PP:
            m += 1
        elif P[p] > -M[m]:
            p += 1
        else:
            m += 1
    if m % 2 != 0:
        if m == MM or p == 0:
            m -= 1
            p += 1
        elif p == PP or m == 0:
            m += 1
            p -= 1
        elif M[m - 1] * M[m] >= P[p - 1] * P[p]:
            m += 1
            p -= 1
        else:
            m -= 1
            p += 1
    if p < 0 or p > PP:
        return prod(M[-K:])
    return prod(P[:p] + M[:m]) 

print(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, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_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

N, K = MAP()

A = LIST()

plus0 = []
minus = []
zero = []

for a in A:
    if a >= 0:
        plus0.append(a)
    if a == 0:
        zero.append(a)
    if a < 0:
        minus.append(a)

# print(plus0)
# print(minus)
# print(zero)

if (len(minus) == N and K%2 == 1) or (plus0 and minus and N == K and (N-len(plus0))%2 == 1):
    # 答えはマイナスなので最小化を目指す
    if (len(minus) == N and K%2 == 1):
        minus.sort(reverse=True)  # 小さい方からKこ
        ans = 1
        for i in range(K):
            ans *= minus[i]
            ans %= mod
    else:
        ans = 1
        for x in minus+plus0:
            ans *= x
            ans %= mod
    print(ans)
else:
    # 答えは0以上なので最大化を目指す
    ans = 1
    cnt = 0
    plus0.sort()
    minus.sort(reverse=True)
    # print(plus0)
    # print(minus)
    while cnt != K:
        if cnt == K-1 or len(minus) <= 1:
            ans *= plus0.pop()
            cnt += 1
        else:
            if not plus0:
                ans *= minus.pop()
                ans *= minus.pop()
                cnt += 2
            else:
                if plus0[-1] > minus[-1]*minus[-2]:
                    ans *= plus0.pop()
                    cnt += 1
                else:
                    ans *= minus.pop()
                    ans *= minus.pop()
                    cnt += 2
        ans %= mod
    print(ans)

Submission status: Wrong Answer

Solution code:
aa=input("").split(" ")
bb=input("").split(" ")
n=int(aa[0])
k=int(aa[1])
b=[]
for i in range(n):
    b+=[int(bb[i])]
b.sort(reverse=True)
s=1
for kk in range(k):
    if(b[kk]<=0):
        break
    s*=b[kk]
    s%=(10**9+7)
print(s)

Submission status: Wrong Answer

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

def solve():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    P = 10**9 + 7
    def mod_prod(a,b):
        return (a % P) * (b % P) % P

    def mod_fact(a):
        ret = 1
        for i in range(a):
            ret = ret * (i + 1) % P
        return ret

    def mod_pow(a, n):
        ret = 1
        while n > 0:
            if n % 2 == 1:
                ret = ret * a % P
            a = a * a % P
            n = n >> 1
        return ret

    def mod_div(a, b):
        b_inv = mod_pow(b, P - 2)
        return a * b_inv % P

    def mod_comb(a,b):
        ret = 1
        b = min(b, a - b)
        for i in range(b):
            ret *= a - i
            ret %= P
        ret = mod_div(ret, mod_fact(b))
        return ret

    A.sort(key=lambda x:-abs(x))

    topK = A[:K]
    rest = A[K:]

    if sum(1 if a < 0 else 0 for a in topK) % 2 == 0:
        ans = 1
        for a in topK:
            ans *= a
            ans %= P
        print(ans)
    else:
        default_ans = 1
        for a in topK:
            default_ans = default_ans * a % P

        ans1 = default_ans
        rest_negs = [a for a in rest if a < 0]
        topk_poss = [a for a in topK if a >= 0]
        if len(rest_negs) > 0 and len(topk_poss) > 0:
            ans1 = 1
            for a in topK:
                ans1 *= a
                ans1 %= P
            ans1 = mod_div(ans1, min(topk_poss))
            ans1 = ans1 * min(rest_negs) % P
        else:
            pass

        ans2 = default_ans
        rest_poss = [a for a in rest if a >= 0]
        topk_negs = [a for a in topK if a < 0]
        if len(rest_poss) > 0 and len(topk_negs) > 0:
            ans2 = 1
            for a in topK:
                ans2 = ans2 * a % P
            ans2 = mod_div(ans2, max(topk_negs))
            ans2 = ans2 * max(rest_poss) % P
        
        ans3 = 1
        for i in range(K):
            ans3 = ans3 * A[N - 1 - i] % P

        print(max(ans1, ans2, ans3))

solve()

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
        f11 = False
        f12 = False
        for i in range(K, N):
            if A[i][1] < 0:
                a1 *= A[i][0]
                f11 = True
                break
        for i in range(K-1, -1, -1):
            if A[i][1] > 0:
                a1 /= A[i][0]
                f12 = True
                break
        a2 = 1
        f21 = False
        f22 = False
        for i in range(K, N):
            if A[i][1] > 0:
                a2 *= A[i][0]
                f21 = True
                break
        for i in range(K-1, -1, -1):
            if A[i][1] < 0:
                a2 /= A[i][0]
                f22 = True
                break

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

print(ans)

Submission status: Wrong Answer

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

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

    qu = deque()
    minus = 0
    plus = 1
    plusFound = False
    mc = 0
    ans = 1
    for i in range(K):
        a, pm = heappop(q)
        if pm == 1:
            plusFound = True
            ans *= plus
            ans %= mod
            plus = -a
        else:
            if mc == 1:
                ans *= (minus * a) % mod
                ans %= mod
            else:
                minus = a
            mc ^= 1
        qu.append((a, pm))
    if mc == 1:
        for i in range(K, N):
            a, pm = heappop(q)
            if pm == 1:
                ans *= (-a * plus) % mod
                ans %= mod
                print(ans)
                break
            elif plusFound:
                ans *= (a * minus) % mod
                ans %= mod
                print(ans)
                break
            qu.append((a, pm))
        else:
            ans = 1
            for i in range(K):
                a, pm = qu.pop()
                if pm == 1:
                    ans *= -a
                else:
                    ans *= a
                ans %= mod
            print(ans)
    else: 
        print((ans * plus) % mod)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

    plus = [A[i] for i in range(N) if A[i] >= 0]
    minus = [A[i] for i in range(N) if A[i] < 0]

    ans = 1

    id = 0
    id2 = 0
    P = len(plus)
    M = len(minus)
    plus.sort(reverse=True)

    mod = 10**9 + 7

    if P == 0:
        if K % 2 == 0:
            minus.sort()
            for i in range(K):
                ans *= minus[i]
                ans %= mod
        else:
            minus.sort(reverse=True)
            for i in range(K):
                ans *= minus[i]
                ans %= mod

    elif M == 0:
        for i in range(K):
            ans *= plus[i]
            ans %= mod

    else:

        p = P // 2
        m = M // 2
        if K > (p+m)*2 and (K % 2 == 0 or (K % 2 == 1 and P % 2 == 0)):  # 絶対値が小さい方から貪欲
            A.sort(key=lambda x: abs(x))
            for i in range(K):
                ans *= A[i]
                ans %= mod

        else:  # 絶対値が大きい方から貪欲
            minus.sort()
            pp = [plus[i]*plus[i+1] for i in range(P // 2)]
            mm = [minus[i] * minus[i+1] for i in range(M//2)]

            id = 0
            id2 = 0

            pp.sort(reverse=True)
            mm.sort(reverse=True)
            pp.append(1)
            mm.append(1)
            for i in range((K // 2) - 1):
                if id == p - 1:
                    ans *= mm[id2]
                    id2 += 1
                elif id2 == m:
                    ans *= pp[id]
                    id += 1
                elif pp[id] >= mm[id2]:
                    ans *= pp[id]
                    id += 1
                else:
                    ans *= mm[id2]
                    id2 += 1

                ans %= mod

            if K % 2 == 1:
                if id >= p-1:
                    ans *= mm[id2]
                    ans *= plus[id*2]
                else:
                    ans *= pp[id]
                    id += 1
                    ans *= plus[id*2]
            else:
                if id >= p:
                    ans *= mm[id2]
                elif id2 >= m:
                    ans *= pp[id]
                elif pp[id] >= mm[id2]:
                    ans *= pp[id]
                else:
                    ans *= mm[id2]

    print(ans % mod)


main()

Submission status: Wrong Answer

Solution code:
N,K = list(map(int,input().split()))
a = list(map(int,input().split()))
a.sort()
large = 10**9 + 7
num_minus = 0
for k in range(N):
    if a[k] < 0:
        num_minus += 1
if num_minus == N and K%2 == 1:
    ans = 1
    for i in range(K):
        #print(a[K-1-i],K-1-i)
        ans *= a[N-1-i]
        ans = ans % large
    print(ans)
    exit()

large = 10**9 + 7

i_left = 0
i_right = N-1

if K == 1:
    print(a[i_right])
    exit()
ans = 1



while K > 1:
    print(i_right,i_left)
    if a[i_right]*a[i_right-1] >= a[i_left]*a[i_left+1]:
        ans = ans * a[i_right]
        ans = ans % large
        ans = ans * a[i_right-1]
        ans = ans % large
        i_right -= 2
    else:
        ans = ans * a[i_left]
        ans = ans % large
        ans = ans * a[i_left+1]
        ans = ans % large
        i_left += 2
    K -= 2

if K == 0:
    print(ans)
else:
    ans = ans * a[i_right]
    ans = ans % large
    print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7

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

p, m = [], []
zero = False
for x in a:
    if x == 0:
        zero = True
        continue
    elif x >= 0: p.append(x)
    else: m.append(x)

if len(p) == 0 and len(m) == 0:
    print(0)
    exit()

p.sort(reverse=True)
m.sort()
mr = list(reversed(m))

def mmod(x):
    if x < 0: return -(MOD - x % MOD)
    return x % MOD

def cum(s):
    n = len(s)
    cs = [1] * (n+1)
    for i in range(n):
        cs[i+1] = mmod(cs[i] * s[i])
    return cs

pc = cum(p)
mc = cum(m)
mrc = cum(mr)

ans = -float("inf")
pl, ml = len(p), len(m)

d = min(pl, k)

for pn in range(d+1)[::-1]:
    mn = k - pn
    if mn > ml: continue
    tmp = mmod(pc[pn] * mc[mn])
    tmp1 = mmod(pc[pn] * mrc[mn])
    ans = max(ans, tmp, tmp1)

if ans < 0 and zero:
    print(0)
else: 
    print(ans % MOD)

Submission status: Wrong Answer

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
#import numpy as np
Q = int(1e9 + 7)

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

A = sorted(A)

if K == N:
    ans = 1
    for a in A:
        ans *= a
        ans %= Q
    print(ans)
    exit()
elif K == 1:
    ans = A[-1] % Q
    print(ans)
    exit()

A_mi, A_0, A_pl = [], [], []
for a in A:
    if a > 0:
        A_pl.append(a)
    elif a < 0:
        A_mi.append(a)
    else:
        A_0.append(a)

#答えが必ず0
if len(A_mi) + len(A_pl) < K:
    print(0)
    exit()

#全て正
if N == len(A_pl):
    ans, c = 1, 0
    for a in reversed(A_pl):
        ans *= a
        ans %= Q
        c += 1
        if c == K:
            break
    print(ans)
    exit()

#全て負or0
if N == len(A_mi) + len(A_0):
    if K % 2 == 0:
        ans, c = 1, 0
        for a in A_mi:
            ans *= a
            ans %= Q
            c += 1
            if c == K:
                break
        print(ans)
        exit()
    else:
        if len(A_0) > 0:
            print(0)
            exit()
        else:
            ans, c = 1, 0
            for a in reversed(A_mi):
                ans *= a
                ans %= Q
                c += 1
                if c == K:
                    break
            print(ans)
            exit()

if (K == len(A_mi) + len(A_pl)) and (len(A_mi) % 2 == 1):
    print(0)
    exit()

cost_2 = []
if len(A_mi) > 1:
    for i in range(0, len(A_mi)-1, 2):
        cost_2.append(A_mi[i] * A_mi[i + 1])

c = 0
ans = 1

while True:
    if (K - c > 1) and (len(cost_2) > 0):
        c2 = cost_2[0]
        if len(A_pl) > 2:
            pl2 = A_pl[-1] * A_pl[-2]
        else:
            pl2 = 0
        if c2 >= pl2:
            ans *= -A_mi[0]
            ans %= Q
            A_mi.pop(0)
            ans *= -A_mi[0]
            ans %= Q
            A_mi.pop(0)
            cost_2.pop(0)
        else:
            ans *= A_pl[-1]
            ans %= Q
            A_pl.pop(-1)
            ans *= A_pl[-1]
            ans %= Q
            A_pl.pop(-1)
        c += 2
    else:
        ans *= A_pl[-1]
        ans %= Q
        c += 1
        A_pl.pop(-1)
    if K == c:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), key=lambda x: abs(x))[::-1]
P = int(1e9+7)
hu_cnt = []

ans = 1
hu = None
sei = 1
flg = False
for a in A:
    flg = a > 0
    if flg:
        break
if not flg:
    for i in range(1, K+1):
        ans = (ans * A[-i]) % P
    print(ans)
    sys.exit()
if K == N:
    for a in A:
        ans = (ans * a)%P
    print(ans)
    sys.exit()

for i, a in zip(range(K), A):
    if a > 0:
        ans = (ans * sei) % P
        sei = a
    else:
        if not hu:
            hu = a
        else:
            ans = (ans * a * hu) % P
            hu = None

ptn1, ptn2 = -1, -1
if hu:
    for i in range(K, N):
        if A[i] > 0:
            ptn1 = sei * A[i]
            break
    for i in range(K, N):
        if A[i] <= 0:
            ptn1 = hu * A[i]
            break
    if hu != 1:
        sei = 1
        ans = (ans * A[K] * hu) % P
    ans = (ans * max(ptn1, ptn2)) % P
else:
    ans = (ans * sei) % P
print(ans%P)

Submission status: Wrong Answer

Solution code:
MOD = 1000000007

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

A.sort(key=lambda x: abs(x))

neg = []
pos = []
zero = 0

for i in range(N):
    if A[i] > 0:
        pos.append(A[i])
    elif A[i] < 0:
        neg.append(A[i])
    else:
        zero += 1

res = 1
sign = 1

for i in range(K):
    res *= A[~i]
    res %= MOD
    if A[~i] < 0:
        sign *= -1

    if A[~i] == 0:
        sign = 0



if sign == 1:
    print(res % MOD)

elif sign == 0:
    print(0)

else:
    flag1 = False
    tmp1 = -1
    minneg = None
    for i in range(K):
        if A[~i] < 0:
            minneg = ~i
    maxpos = None
    for i in range(N - K):
        if A[i] > 0:
            flag1 = True
            maxpos = i
    if maxpos is not None:
        tmp1 *= A[maxpos]
        tmp1 /= A[minneg]
    flag2 = False
    tmp2 = -1
    minpos = None
    for i in range(K):
        if A[~i] > 0:
            flag2 = True
            minpos = ~i
    maxneg = None
    for i in range(N - K):
        if A[i] < 0:
            maxneg = i
    if maxneg is not None and minpos is not None:
        tmp2 *= A[maxneg]
        tmp2 /= A[minpos]
    if tmp1 > 0 or tmp2 > 0:
        if tmp1 > tmp2:
            print(res * A[maxpos] * pow(A[minneg], MOD - 2, MOD) % MOD)
        else:
            print(res * A[maxneg] * pow(A[minpos], MOD - 2, MOD) % MOD)
    else:
        if zero:
            print(0)
        else:
            res = 1
            for i in range(K):
                res *= A[i]
                res %= MOD
            print(res % MOD)

Submission status: Wrong Answer

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

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

if __name__=='__main__':
    Main()

Submission status: Wrong Answer

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

ret = 1
mod = 10 ** 9 + 7

left = k
mptr = 0
pptr = len(a) - 1
mls = []
a.sort()
for i in range(len(a)):
    if i % 2 == 0:
        continue
    else:
        if a[i] < 0 and a[i-1] < 0:
            mls.append((a[i] * a[i-1], 2))
        else:
            break

for i in range(1, len(a) + 1):
    if a[-i] > 0:
        mls.append((a[-i], 1))

mls.sort()
mls.reverse()
ptr = 0

while left > 0:
    if ptr >= len(mls):
        break
    else:
        tmp = mls[ptr]
        if left > 1:
            ret = (mls[ptr][0] % mod) * ret % mod
            left -= mls[ptr][1]
            ptr += 1
        else:
            if mls[ptr][1] == 2:
                ptr += 1
            else:
                ret = (mls[ptr][0] % mod) * ret % mod
                left -= mls[ptr][1]
                ptr += 1

if left == 0:
    print(ret % mod)
else:
    a.sort(key=lambda x: abs(x))
    ret = 1
    for i in range(k):
        ret *= a[i] % (10 ** 9 + 7)
        if ret == 0:
            break
    print(ret % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7

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

alst.sort()

if k == 1:
    print(alst[-1] % MOD)
    exit()

if alst[0] >= 0:
    ans = 1
    alst.sort(reverse = True)
    for i in range(k):
        ans *= alst[i]
        ans %= MOD
    print(ans)
    exit()

if alst[-1] <= 0:
    ans = 1
    if k % 2 == 1:
        alst.sort(reverse = True)
    for i in range(k):
        ans *= alst[i]
        ans %= MOD
    print(ans)
    exit()

blst = []
for num in alst:
    try:
        blst.append([abs(num), abs(num) // num])
    except ZeroDivisionError:
        blst.append([abs(num), 0])
blst.sort(reverse = True,key = lambda x:x[0])
if blst[k - 1] == 0:
    print(0)
    exit()
    
minus = 0
last_minus = 0
last_plus = 0
ans_lst = []
for i in range(k):
    if blst[i][1] == -1:
        minus += 1
        last_minus = blst[i][0]
    else:
        last_plus = blst[i][0]
    ans_lst.append(blst[i][0])

next_minus = 0
next_plus = 0
flg_minus = False
flg_plus = False

for i in range(k, n):
    if blst[i][1] == -1 and (not flg_minus):
        next_minus = blst[i][0]
        flg_minus = True
    if blst[i][1] == 1 and (not flg_plus):
        next_plus = blst[i][0]
        flg_plus = True
    if (flg_plus and flg_minus) or blst[i][1] == 0:
        break

if minus % 2 == 0:
    ans = 1
    for num in ans_lst:
        ans *= num
        ans %= MOD
    print(ans)

else:
    minus_s = last_minus * next_minus
    plus_s = last_plus * next_plus
    ans = 1
    if minus == k:
        ans_lst.remove(last_minus)
        ans_lst.append(next_plus)
    elif minus == 0:
        pass
    elif minus_s == plus_s == 0:
        if last_minus == 0:
            ans_lst.remove(last_plus)
            ans_lst.append(next_minus)
        else:
            ans_lst.remove(last_minus)
            ans_lst.append(next_plus)
        
    elif minus_s > plus_s:
        ans_lst.remove(last_plus)
        ans_lst.append(next_minus)
    else:
        ans_lst.remove(last_minus)
        ans_lst.append(next_plus)
    for num in ans_lst:
        ans *= num
        ans %= MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
#import bisect
#import numpy as np
# from collections import deque
from collections import deque
# map(int, sys.stdin.read().split())
import itertools
import heapq

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


def main():
    N,K =map(int,input().split())
    A =list(map(int,input().split()))
    mod =10**9+7
    A.sort()
    A = deque(A)
#    print(A)
    A_minus = deque([s for s in A if s <0])
    A_plus =deque( [s for s in A if s >=0])

#    print(A_plus)
#    print(A_minus)
    AA = []
    if K%2 ==0:
        while len(A_minus)>=2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            AA.append(-a1*a2)

        while len(A_plus)>=2:
            a1 =A_plus.pop()
            a2 =A_plus.pop()
            AA.append(-a1*a2)
        ans =1
        heapq.heapify(AA)
        for i in range(K//2):
            ans *= (-1 * heapq.heappop(AA)) %mod
        print(ans%mod)

    elif len(A_plus)==0:
        ans = 1
        for i in range(K):
            ans *= A_minus.pop() %mod
        print(ans)

    else:
        ans = A_plus.pop()
        while len(A_minus)>=2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            AA.append(-a1*a2)

        while len(A_plus)>=2:
            a1 =A_plus.pop()
            a2 =A_plus.pop()
            AA.append(-a1*a2)

        heapq.heapify(AA)
        for i in range(K//2):
            ans *= (-1 * heapq.heappop(AA)) %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.append(i)
        if i<0:y.append(i)
    if 0<len(x)<k and len(y)>=k:
        y=sorted(y)[:k]
        x=sorted(x)[::-1]
        m=len(x)
        i=k
        j=0
        if k%2:
            y[i-1]=x[j]
            i-=1
            j+=1
        while i>1 and j+1<m and y[i-1]*y[i-2]<x[j]*x[j+1]:
            y[i-1],y[i-2]=x[j],x[j+1]
            i-=2
            j+=2
        c=1
        for i in y:
            c=c*i%M
        print(c)
    if len(x)+len(y)<k or len(x)<k and (k-len(x))%2 and len(x)+len(y)<n:
        print(0)
        exit()
    if len(x)<k and (k-len(x))%2:
        x=sorted(x+[-i for i in y])[:k]
        x[0]*=-1
        c=1
        for i in x:
            c=c*i%M
        print(c)
        exit()
    x=sorted(x)[::-1][:k]
    y.sort()
    m=len(y)
    i=len(x)
    j=0
    if i<k:
        j=k-i
        x+=y[:j]
        j+=1
    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:
from scipy.special import comb

Submission status: Wrong Answer

Solution code:
from collections import deque
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
d=deque(A)

l=[]
if K%2==0 or (K%2==1 and A[0]>0):
  for i in range(K//2):
    if d[0]*d[1]>=d[-1]*d[-2] and len(d)>2 and d[2]>0:
      l.append(d.popleft())
      l.append(d.popleft())
    else:
      l.append(d.pop())
      l.append(d.pop())
  if K%2==1:
    l.append(d[0])
else:
  for i in range(K):
    l.append(d.popleft())
      
ans=1
for i in l:
  ans*=i
  ans%=10**9+7
print(ans%(10**9+7))

Submission status: Wrong Answer

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

if n == k:
    ans = 1
    for i in a:
        ans *= i
        ans %= mod
    print(ans)

m = []
p = []
zero = 0
for i in a:
    if i < 0:
        m.append(-i)
    elif i > 0:
        p.append(i)
    else:
        zero += 1

if n - k < zero:
    print(0)
    exit()

if n - k == zero:
    if len(m) % 2 == 1:
        print(0)
        exit()

if len(p) == 0 and k % 2 == 1:
    if zero >= 1:
        print(0)
    else:
        m.sort()
        ans = 1
        for i in range(k):
            ans *= m[i]
            ans %= mod
        ans = mod - ans
        print(ans % mod)
    exit()

m.sort(reverse=True)
p.sort(reverse=True)
nm = 0
np = 0
ans = 1
if k % 2 == 1:
    ans *= p[0]
    np += 1
lap = k // 2

while nm < len(m) - 1 and np < len(p) - 1 and lap > 0:
    lap -= 1
    i = m[nm] * m[nm + 1]
    j = p[np] * p[np + 1]
    if i > j:
        ans *= i
        ans %= mod
        nm += 2
    else:
        ans *= j
        ans %= mod
        np += 2

if lap > 0:
    if nm < len(m) - 1:
        for i in range(nm, nm + lap * 2):
            ans *= m[i]
            ans %= mod
    else:
        for i in range(np, np + lap * 2):
            ans *= p[i]
            ans %= mod

print(ans % mod)