Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

We will choose exactly K of these elements. Find the maximum possible product of the chosen elements.

Then, print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Constraints

1 \leq K \leq N \leq 2\times 10^5

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

Print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

The possible products of the two chosen elements are 2, -3, -4, -6, -8, and 12, so the maximum product is 12.

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

The possible products of the three chosen elements are -24, -12, -8, and -6, so the maximum product is -6.

We print this value modulo (10^9+7), that is, 1000000001.

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

The possible products of the one chosen element are -1 and 1000000000, so the maximum product is 1000000000.

Sample Input 4

10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1

Sample Output 4

999983200

Be sure to print the product modulo (10^9+7).



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
p = []
m = []
mod = 10**9 + 7
if n == k:
  ans = 1
  for x in a:
    ans *= x
    ans %= mod
  print(ans)
  exit()
zero = 0
for x in a:
  if x == 0:
    zero += 1
  if x > 0:
    p.append(x)
  else:
    m.append(-x)
p.sort(reverse=True)
m.sort(reverse=True)
#print(zero,p,m)
nowp = 0
nowm = 0
lenp = len(p)
lenm = len(m)
if k + zero > n:
  print(0)
  exit()
n -= zero
ans = 1
def inv(x):
  y = 1
  while x != 1:
    y *= mod // x + 1
    y %= mod
    x -= mod % x
  return y
pp = 0
for _ in range(k):
  if nowp == lenp:
    ans *= -m[nowm]
    ans %= mod
    nowm += 1
    pp = 1-pp
  elif nowm == lenm:
    ans *= p[nowp]
    ans %= mod
    nowp += 1
  elif p[nowp] >= m[nowm]:
    ans *= p[nowp]
    ans %= mod
    nowp += 1
    #print('$$')
  else:
    ans *= -m[nowm]
    ans %= mod
    nowm += 1
    pp = 1-pp
    #print('$')
  #print(pp,nowp,nowm)
#print(pp,ans)
if pp == 0:
  print(ans)
  exit()
if nowm == 0:
  print(ans)
  exit()
if nowp == 0:
  ans = 1
  m.reverse()
  for d in range(k):
    ans *= -m[d]
    ans %= mod
  print(ans)
  exit()
if lenp == nowp:
  ans *= inv(p[-1])
  ans *= -m[nowm]
  ans %= mod
  print(ans)
  exit()
if lenm == nowm:
  ans *= inv(-m[-1])
  ans *= p[nowp]
  ans %= mod
  print(ans)
  exit()
if nowp == 0:
  ans *= inv(-m[nowm-1])
  ans *= p[0]
  ans %= mod
  print(ans)
  exit()
if nowm == 0:
  ans *= inv(p[nowp-1])
  ans *= -m[0]
  ans %= mod
  print(ans)
  exit()
pl = p[nowp-1]
pr = p[nowp]
ml = m[nowm-1]
mr = m[nowm]
if mr * ml > pl * pr:
  ans *= inv(pl)
  ans *= -mr
  ans %= mod
  print(ans)
else:
  ans *= inv(-ml)
  ans *= pr
  ans %= mod
  print(ans)

Submission status: Wrong Answer

Solution code:
import sys

MOD = 10**9 + 7


def read_int():
    line = sys.stdin.readline().rstrip('\n')
    return int(line)

def read_int_list():
    line = sys.stdin.readline().rstrip('\n')
    return [int(e) for e in line.split(' ')]

def sign(n):
    if n > 0:
        return 1
    if n < 0:
        return -1
    return 0

def abs_prod(A, K, add, remove):
    prod = 1
    for i in range(K):
        if i == remove:
            continue
        prod *= abs(A[i])
        prod %= MOD
    if add != None:
        prod *= abs(A[add])
        prod %= MOD
    return prod


N, K = read_int_list()
A = read_int_list()

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

last_plus = None
last_minus = None
sig = 1
for i in range(K):
    sig *= sign(A[i])
    if A[i] > 0:
        last_plus = i
    if A[i] < 0:
        last_minus = i
remove = None
add = None
if sig < 0:
    for i in range(K, N):
        if A[i] > 0 and last_minus != None:
            remove = last_minus
            add = i
            sig = 1
            break
        elif A[i] < 0 and last_plus != None:
            remove = last_plus
            add = i
            sig = 1
            break
        elif A[i] == 0:
            sig = 0
            break

if sig == 0:
    print(0)


if sig > 0:
    ap = abs_prod(A, K, add, remove)
    print(ap)
else:
    ap = abs_prod(A[::-1], K, add, remove)
    print((MOD - ap) % MOD)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
mod=10**9+7
P=1
B=[]
C=False
for i in range(N):
  if A[i]:
    B.append(A[i])
  else:
    C=True
if len(B)<K:
  print(0)
  exit()
B.sort(reverse=True,key=lambda x:abs(x))
Y=0
for i in range(K):
  if B[i]<0:
    Y+=1
  P=P*B[i]%mod
if Y&1==0:
  print(P)
  exit()
if Y==K:
  B.sort()
  if B[-1]<0:
    if C:
      print(0)
      exit()
    P=1
    for i in range(K):
      P=P*B[-(i+1)]%mod
    print(P)
    exit()
  P=P*pow(B[0],mod-2,mod)*B[-1]%mod
  print(P)
  exit()
Y,Z=0,0
for i in range(K,len(B)):
  if B[i]<0:
    Y=B[i]
    break
for i in range(K,len(B)):
  if B[i]>0:
    Z=B[i]
    break
if Y==0:
  for i in range(K-1,-1,-1):
    if B[i]<0:
      P=P*pow(B[i],mod-2,mod)
      break
  print(P*Z%mod)
elif Z==0:
  for i in range(K-1,-1,-1):
    if B[i]>0:
      P=P*pow(B[i],mod-2,mod)
      break
  print(P*Y%mod)
if Y==0 or Z==0:
  exit()
V,W=0,0
for i in range(K-1,-1,-1):
  if B[i]<0:
    V=B[i]
    break
for i in range(K-1,-1,-1):
  if B[i]>0:
    W=B[i]
    break
if -Y/W>-Z/V:
  print(P*Y*pow(W,mod-2,mod)%mod)
else:
  print(P*Z*pow(V,mod-2,mod)%mod)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from scipy.sparse.csgraph import floyd_warshall
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush, heapify
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    a.sort()
    ans = 1
    cnt = 0
    l = 0
    r = n-1
    x = bisect.bisect_left(a,0)
    y = bisect.bisect_right(a,0)
    flag = 0
    if n == 1:
        print(a[0]%mod)
        return
    if n == 2:
        if k == 1:
            print((max(a[0],a[1]))%mod)
        else:
            print(a[0]*a[1]%mod)
        return
    if k == n:
        if x%2 == 0:
            flag = 1
    elif k == n-1:
        if x == n:
            if k%2 == 0:
                flag = 1
        else:
            if not(x == n and x%2 == 0):
                flag = 1
    else:
        flag = 1
    if flag:
        while True:
            if a[l+1] >= 0:
                ans *= a[r]
                ans %= mod
                cnt += 1
                r -= 1
            else:
                if a[l]*a[l+1] >= a[r]*a[r-1] and cnt < k-1:
                    ans *= a[l]
                    ans *= a[l+1]
                    ans %= mod
                    cnt += 2
                    l += 2
                else:
                    ans *= a[r]
                    ans %= mod
                    cnt += 1
                    r -= 1
            if cnt == k:
                break
        print(ans)
    else:
        for i in range(n):
            a[i] = abs(a[i])
        a.sort()
        for i in range(k):
            ans *= a[i]
            ans %= mod
        ans *= -1
        ans %= mod
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    mod = 10 ** 9 + 7
    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
    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
    def prod(l):
        r = 1
        for a in l:
            r = (r * a) % mod
        return r
    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
from heapq import heappop, heappush
from collections import deque

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

    qu = deque()
    minus = 0
    mc = 0
    ans = 1
    for i in range(K):
        a, pm = heappop(q)
        if pm == 1:
            ans *= -a
            ans %= mod
        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
                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)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
mod = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
pm = 1
ans = 1
odd = False
if k%2 == 1:
    odd = True

while 0 in a:
    a.pop(a.index(0))

if len(a) < k:
    print(0)
    sys.exit()
ispop = False if len(a) == n else True
n = len(a)
a.sort()
if odd and a[n - 1] < 0:
    if ispop:
        print(0)
        sys.exit()
    for i in range(k):
        ans = (ans * a[n - 1 - i])%mod
    print(ans%mod)
    sys.exit()
for i in range(k//2):
    p = a[n-1] * a[n-2]
    m = a[0] * a[1]
    if p >= m:
        ans = (ans * p)%mod
        a.pop(n - 1)
        a.pop(n - 2)
    else:
        ans = (ans * m)%mod
        a.pop(1)
        a.pop(0)
    n -= 2
if k%2 == 1:
    if a[n - 1] > 0:
        ans = (ans * a[n - 1])%mod
    else:
        if ispop:
            ans = 0
        else:
            ans = (ans * a[n - 1])%mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,K=map(int,input().split())
A=list(map(int,input().split()))
A_m=[x for x in A if x<0]
A_pz=[x for x in A if x>=0]
A_m.sort()
A_pz.sort()
if N==K:
    ans=1
    for x in A:
        ans*=x
        ans%=MOD
elif not A_pz and K%2==1:
    ans=1
    for x in A_m[::-1][:K]:
        ans*=x
        ans%=MOD
else:
    B=[]
    for i in range(len(A_m)//2):
        B.append(A_m[i*2]*A_m[i*2+1])
    B.sort()
    i,j=0,0
    ans=1
    while i+j*2<=K-2:
        if i<len(A_pz) and j<len(B):
            if A_pz[i]>B[j]:
                ans*=A_pz[i]
                i+=1
            else:
                ans*=B[j]
                j+=1
        elif i<len(A_pz):
            ans*=A_pz[i]
            i+=1
        else:
            ans*=B[j]
            j+=1
        ans%=MOD
    if i+j*2==K-2:
        if i<len(A_pz)-1 and j<len(B):
            ans*=max(A_pz[i]*A_pz[i+1],B[j])
        elif i<len(A_pz)-1:
            ans*=A_pz[i]*A_pz[i+1]
        else:
            ans*=B[j]
    elif i+j*2==K-1:
        if i<len(A_pz):
            ans*=A_pz[i]
        else:
            ans*=A_m[-1]
    ans%=MOD
print(ans)

Submission status: Wrong Answer

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

b = [(abs(i), 1 if i >= 0 else -1) for i in a]

b = sorted(b)
b = list(reversed(b))
mod = int(1e9 + 7)

def fp(x,y):
	res=1
	while y > 0:
		if y % 2:
			res *= x
		x *= x
		y //= 2
		x %= mod
		res %= mod
	return res

def inv(x):
	return fp(x,mod-2)

p = 1
signe = 1
for i in range(k):
	p *= b[i][0]
	p %= mod
	if b[i][0] == 0:
		signe = 0
	signe *= b[i][1]

if signe >= 0:
	print(p % mod)
else:
	# choice between replacing the last positive by the next negative
	# and replacing the last negative by the next positive
	lastP, nextP, lastN, nextN = -1, -1, -1, -1
	for i in range(k):
		if b[i][0] * b[i][1] >= 0:
			lastP = i
		if b[i][0] * b[i][1] <= 0:
			lastN = i
	for i in range(k, n):
		if b[i][0] * b[i][1] >= 0:
			nextP = i
		if b[i][0] * b[i][1] <= 0:
			nextN = i
	if (lastP!=-1 and nextN !=-1) and (lastN!=-1 and nextP!=-1):
		if b[nextN][0] * b[lastN][0] >= b[nextP][0] * b[lastP][0]:
			ans = -p * inv(b[lastP][0]) * b[nextN][0]
			ans %= mod
			print(ans)
		else:
			ans = -p * inv(b[lastN][0]) * b[nextN][0]
			ans %= mod
			print(ans)
	elif lastP!=-1 and nextN!=-1:
		ans = -p * inv(b[lastP][0]) * b[nextN][0]
		ans %= mod
		print(ans)
	elif lastN!=-1 and nextP!=-1:
		ans = -p * inv(b[lastN][0]) * b[nextP][0]
		ans %= mod
		print(ans)
	else:
		# tout le monde est negatif
		a = list(reversed(sorted(a)))
		p = 1
		for i in range(k):
			p *= a[i]
			p %= mod
		print(p)

Submission status: Wrong Answer

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

B = []
for a in A:
    B.append([abs(a), a])

B.sort(reverse=True)
ans =  1
pre_nega = 0
pre_posi = 0
num_posi = num_nega = 0
for count, (b, a) in enumerate(B, 1):
    ans *= b
    ans %= MOD
    if a < 0:
        pre_nega = a
        num_nega += 1
    if a > 0:
        pre_posi = a
        num_posi += 1
    if count == K:
        break

if num_nega % 2 == 0:
    print(ans)
    quit()

next_nega = next_posi = 0
for b, a in B[K:]:
    if a < 0:
        next_nega = a
    elif a > 0:
        next_posi = a

if next_nega != 0 and num_posi > 0:
    if next_posi != 0 and num_nega > 0:
        if next_nega * pre_nega > next_posi * pre_posi:
            ans *= abs(next_nega)
            ans *= pow(pre_posi, MOD-2, MOD)
            ans %= MOD
        else:
            ans *= next_posi
            ans *= pow(abs(pre_nega), MOD-2, MOD)
            ans %= MOD
    else:
        ans *= abs(next_nega)
        ans *= pow(pre_posi, MOD-2, MOD)
        ans %= MOD
else:
    if next_posi != 0 and num_nega > 0:
        ans *= next_posi
        ans *= pow(abs(pre_nega), MOD-2, MOD)
        ans %= MOD
    else:
        if 0 in A:
            ans = 0
        else:
            ans = 1
            B.sort()
            for count, (b, a) in enumerate(B, 1):
                ans *= a
                ans %= MOD
                if count == K:
                    break

print(ans)

Submission status: Wrong Answer

Solution code:
import sys;input=sys.stdin.readline
MOD = 10**9+7
N, K = map(int, input().split())
X = list(map(int, input().split()))
if N==K:
    R = 1
    for x in X:
        R = R*x%MOD
    print(R)
else:
    ps,ns=[],[]
    for x in X:
        if x>=0:
            ps.append(x)
        else:
            ns.append(x)
    ps.sort()
    ns.sort()
    if K%2 and len(ps)==0:
        R = 1
        ns = ns[::-1]
        for i in range(K):
            R = R*ns[i]%MOD
        print(R)
        sys.exit()
    if len(ps) == 0:
        R = 1
        for i in range(K):
            R = R*ns[i]%MOD
        print(R)
        sys.exit()
    nns = []
    for i in range(len(ns)//2):
        nns.append(ns[2*i]*ns[2*i+1])
    if K%2:
        R = ps.pop()
        K -= 1
    else:
        R = 1
    nns = nns[::-1]
    K = K//2
    pps  = []
    for i in range(len(ps)//2):
        pps.append(ps[2*i]*ps[2*i+1])
    while K:
        x = 0
        if pps:
            x = pps.pop()
        if nns:
            x = max(x, nns.pop())
        R = R*x%MOD
        K-=1
    print(R)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left, bisect_right
from collections import deque
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    idx1 = bisect_left(A, 0)
    idx2 = bisect_right(A, 0)
    A_minus = A[:idx1]
    A_zero = idx2 - idx1
    A_plus = A[idx2:]

    if N - A_zero < K:
        print(0)
        return
    if N - idx2 == 0 and K % 2 == 0:
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= mod
        print(ans)
        return
    if N - idx2 == 0 and K % 2 != 0:
        ans = 1
        for i in range(K):
            ans *= A[N - i - 1]
            ans %= mod
        print(ans)
        return

    pos_idx = max(0, (N - idx2) - K)
    neg_idx = 0
    while pos_idx < N - idx2 - 1 and neg_idx < idx1 - 1:
        x = A_plus[pos_idx] * A_plus[pos_idx + 1]
        y = A_minus[neg_idx] * A_minus[neg_idx + 1]
        if x < y:
            pos_idx += 2
            neg_idx += 2
        else:
            break

    ans = 1
    for i in range(pos_idx, N - idx2):
        ans *= A_plus[i]
        ans %= mod
    for i in range(neg_idx):
        ans *= A_minus[i]
        ans %= mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod = 10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort(key=lambda x:-abs(x))
p = []
n = []
for i in range(K):
    a = A[i]
    if a>0:
        p.append(a)
    elif a<0:
        n.append(a)

if len(n)%2==0:
    ans = 1
    for a in n:
        ans *= a
        ans %= mod
    for a in p:
        ans *= a
        ans %= mod
else:
    ap = 0
    an = 0
    for i in range(K,N):
        if ap==0 and A[i]>0:
            ap = A[i]
        if an==0 and A[i]<0:
            an = -A[i]
    if len(p)*len(n)>0:
        ap_ = p[-1]
        an_ = -n[-1]
        if ap_*an_==0:
            ans = 0
        else:
            if ap*ap_>an*an_:
                n.pop()
                p.append(ap)
            else:
                p.pop()
                n.append(-an)
            ans = 1
            for a in n:
                ans *= a
                ans %= mod
            for a in p:
                ans *= a
                ans %= mod
    elif len(p)>0:
        ans = 1
        for a in p:
            ans *= a
            ans %= mod
    elif len(n)>0:
        ans = 1
        for a in n:
            ans *= a
            ans %= mod
if len(p)+len(n)<K:
    ans = 0
if len(p)==0 and len(n)==K and K%2==1:
    An = [A[i] for i in range(N) if A[i]<0]
    An.sort()
    An = An[::-1]
    ans = 1
    for i in range(K):
        ans *= An[i]
        ans %= mod
    if A[-1]==0:
        ans = 0
if N==K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= 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
A.sort()
B = []
flag = False
F = False
tmp = 0
num = -1
ans = 1
for i, a in enumerate(A):
    if a < 0:
        if flag:
            B.append(tmp * a)
            flag = False
        else:
            tmp = a
            flag = True
    elif a == 0:
        F = True
    else:
        num = i
        break
if num == -1:
    if K % 2 == 1:
        for i, a in enumerate(A[::-1]):
            if i == K:
                print(ans)
                exit()
            ans *= a
            ans %= mod

A = A[num:]
A.sort(reverse=True)
if K % 2 == 1:
    ans = A[0]
    A = A[1:]
    K -= 1
ans %= mod
flag = False
for a in A:
    if flag:
        B.append(tmp * a)
        flag = False
    else:
        tmp = a
        flag = True
K //= 2
if len(B) < K:
    print(0)
    exit()
B.sort(reverse=True)
for i, b in enumerate(B):
    if K == i:
        break
    ans *= b
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
'''
# Sample code to perform I/O:

name = input()                  # Reading input from STDIN
print('Hi, %s.' % name)         # Writing output to STDOUT

# Warning: Printing unwanted or ill-formatted data to output will cause the test cases to fail
'''

# Write your code here
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
m = 1
mod = 1000000007
for i in range(k):
    m = (m) * (a[i])
print(m%mod)

Submission status: Wrong Answer

Solution code:
import sys
MOD = 10 ** 9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
S = sorted(A, key=abs, reverse=True)
X = 1
pm = 0
for i in range(K - 1):
    if S[i] < 0:
        pm = 1 - pm
    X *= abs(S[i]) % MOD
    X = X % MOD
for i in range(K - 1, N):
    if pm == 0:
        if S[i] > 0:
            Y = X * S[i] % MOD
            print(Y % MOD)
            sys.exit()
    else:
        if S[i] < 0:
            Y = X * abs(S[i]) % MOD
            print(Y % MOD)
            sys.exit()

X = 1
S = S[::-1]
for i in range(K):
    X *= abs(S[i]) % MOD
X *= -1
print(X % MOD)

Submission status: Wrong Answer

Solution code:
import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict

# available on Google, not available on Codeforces
# import numpy as np
# import scipy


def solve(lst,k):  # fix inputs here
    console("----- solving ------")

    MOD = 10**9 + 7

    lst = sorted(lst, key=lambda x: abs(x))[::-1]
    sign = [0 if x == 0 else x//abs(x) for x in lst]

    # no choice negative
    if all([x == -1 for x in sign]) and k%2 == 1:
        res = 1
        for i in lst[::-1][:k]:
            res = (res*i)%MOD 
        return res

    if lst[k-1] == 0:
        return 0

    pos = max(lst[k-1:])
    neg = min(lst[k-1:])

    initial_sign = 1
    for i in sign[:k-1]:
        initial_sign = initial_sign*i

    if initial_sign == 1:
        res = pos
        for i in lst[:k-1]:
            res = (res*i)%MOD
        return res

    if initial_sign == -1:
        res = neg
        for i in lst[:k-1]:
            res = (res*i)%MOD
        return res

    # return a string (i.e. not a list or matrix)
    return 0


def console(*args):  # the judge will not read these print statement
    print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return


for case_num in [1]:
    # read line as a string
    # strr = input()

    # read line as an integer
    # k = int(input())
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
    _,k = list(map(int,input().split()))
    lst = list(map(int,input().split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    # grid = []
    # for _ in range(nrows):
    #     grid.append(list(map(int,input().split())))

    res = solve(lst,k)  # please change
    
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
    print(res)

Submission status: Wrong Answer

Solution code:
import math
n,k=list(map(int,input().split()))
l=list(map(int,input().split()))
lul = 10**9 + 7
if n==1:
	print(l[0])
else:
	pos = []
	neg = []
	for i in range(n):
		if l[i]<0:
			neg.append(-1*l[i])
		else:
			pos.append(l[i])
	pos.sort(); pos=pos[::-1]
	neg.sort(); neg = neg[::-1]
	temp = list(neg)
	v = 1
	for i in range(len(pos)):
		v=(v*pos[i])%lul
		pos[i] = v
	v = 1
	for i in range(len(neg)):
		v=(v*neg[i])%lul
		neg[i] = v
	v = 0
	a = -1*math.inf
	# print(pos)
	# print(neg)
	while True:
		if(v>k):
			break
		if(v<=len(neg) and (k-v)<=len(pos)):
			ans = 1
			if(v-1 >= 0):
				ans = (ans*neg[v-1])%lul
			if k-v-1 >= 0:
				ans = (ans*pos[k-v-1])%lul
			a = max(ans,a)
		v+=2
	if(k<=len(neg)):
		if k%2==0:
			a = max(a,neg[k-1]%lul)
		else:
			# print("yo",neg[k-1])
			v = 1
			for i in range(len(neg)-k,len(neg)):
				v = (v*temp[i])%lul
			# print(v)
			a = max(a,-1*v)
	# print(a)
	print(a%lul)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    if N == K:
        ans = 1
        for a in A:
            ans *= a
            ans %= mod
        return ans

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

    if len(neg) == N:
        res = 1
        for x in neg[:K]:
            res *= x
            res %= mod
        return res

    ans = 1

    if K & 1:
        ans *= pos.pop()
        K -= 1
    # この時点でKは偶数
    while K > 1 and len(pos) > 1 and len(neg) > 1:
        K -= 2
        x = 1
        if pos[-1] * pos[-2] > neg[-1] * neg[-2]:
            ans *= pos.pop()
            ans *= pos.pop()
            ans %= mod
        else:
            ans *= neg.pop()
            ans *= neg.pop()
            ans %= mod
    while K > 1 and len(pos) > 1:
        K -= 2
        ans *= pos.pop()
        ans %= mod
        ans *= pos.pop()
        ans %= mod
    while K > 1 and len(neg) > 1:
        K -= 2
        ans *= neg.pop()
        ans %= mod
        ans *= neg.pop()
        ans %= mod
    return ans


if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,K = IL()
A = IL()
A = sorted(A,key= lambda x:(-abs(x),-x))
S = [a//abs(a) if abs(a)!=0 else 0 for a in A]

count_M = 0
last_M = None
last_P = None
for i in range(K):
  if S[i] == 0:
    print(0)
    exit()
  if S[i] == -1:
    last_M = i
    count_M += 1
  if S[i] == 1:
    last_P = i

if count_M%2 == 0:
  ans = 1
  for i in range(K):
    ans *= A[i]
    ans %= MOD
  print(ans)
  exit()
else:
  ANS1 = -INF
  ANS2 = -INF
  if last_M!=None:
    for i in range(K,N):
      if S[i] == 1:
        ans = 1
        for ii in range(K):
          if ii != last_M:
            ans *= A[ii]
            ans %= MOD
        ans *= A[i]
        ans %= MOD
        ANS1 = ans
        break
  if last_P!=None:
    for i in range(K,N):
      if S[i] == -1:
        ans = 1
        for ii in range(K):
          if ii != last_P:
            ans *= A[ii]
            ans %= MOD
        ans *= A[i]
        ans %= MOD
        ANS2 = ans
        break
  if max(ANS1,ANS2)!=-INF:
    print(max(ANS1,ANS2))
    exit()
  if A[-1] == 0:
    print(0)
    exit()
  else:
    ans = 1
    for i in range(K):
      ans *= A[N-1-i]
      ans %= MOD
    print(ans)