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()))
mod = 10**9+7
a1 = []
a2 = []
cnt = 0
for i in a:
    if (i >= 0):
        a1.append(i)
    else:
        a2.append(-i)
a1.sort()
a2.sort()
#print(a1,a2)
if (k==1):
    print(max(a)%mod)
    exit()
if (n==k):
    ans = 1
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()
if (len(a1)==0):
    if (k%2==0):
        ans = 1
        for i in range(k):
            ans *= a2.pop()
            ans %= mod
        print(ans)
        exit()
    else:
        ans = 1
        for i in range(k):
            ans *= -a2[i]
            ans %= mod
        print(ans)
        exit()
elif (len(a2)==0):
    ans = 1
    for i in range(k):
        ans *= a1.pop()
        ans %= mod
    print(ans)
    exit()

bef1 = 10**10
bef2 = 10**10
index1 = 0
index2 = 0
ans = 1
for i in range(k):
    if (len(a1)==0):
        x = a2.pop()
        ans *= x
        ans %= mod
        index2 += 1
        cnt += 1
        continue
    if (len(a2)==0 or a1[-1]>=a2[-1]):
        x = a1.pop()
        ans *= x
        ans %= mod
        index1 += 1
        bef1 = x
    else:
        x = a2.pop()
        ans *= x
        ans %= mod
        index2 += 1
        cnt += 1
        bef2 = x
if (cnt%2==1):
    if len(a1)>0 and len(a2)>0:
        if (index1==0):
            ans *= a1[-1]
            ans *= pow(bef2,mod-2,mod)
            ans %= mod
        elif (index2==0):
            ans *= a2[-1]
            ans *= pow(bef1,mod-2,mod)
            ans %= mod
        else:
            A = a1[-1]/bef2
            B = a2[-1]/bef1
            if (A>=B):
                ans *= a1[-1]
                ans *= pow(bef2,mod-2,mod)
                ans %= mod
            else:
                ans *= a2[-1]
                ans *= pow(bef1,mod-2,mod)
                ans %= mod
    elif (len(a1)==0):
        ans *= a2[-1]
        ans *= pow(bef1,mod-2,mod)
        ans %= mod
    else:
        ans *= a1[-1]
        ans *= pow(bef2,mod-2,mod)
        ans %= mod
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    A.sort()
    A_neg = [a for a in A if a < 0]
    A_zero = [a for a in A if a == 0]
    A_pos = [a for a in A if a > 0]

    A_neg.sort(reverse=True)
    A_pos.sort()

    if K > len(A_neg) + len(A_pos):
        print(0)
        return
    elif len(A_pos) == 0:
        if len(A_zero) > 0:
            print(0)
            return
        elif K % 2:
            ans = 1
            for a in A_neg[:K]:
                ans = (ans * a) % MOD
            print(ans)
            return
        else:
            ans = 1
            for a in A_neg[-K:]:
                ans = (ans * a) % MOD
            print(ans)
            return

    tmp_pos = []
    tmp_neg = []

    ans = 1
    neg = 0
    for i in range(K):
        if not A_neg:
            tmp_pos.append(A_pos[-1])
            ans = ans * A_pos.pop()
        elif not A_pos:
            tmp_neg.append(A_neg[-1])
            ans = ans * A_neg.pop()
            neg = 1 - neg
        elif -A_neg[-1] > A_pos[-1]:
            tmp_neg.append(A_neg[-1])
            ans = ans * A_neg.pop()
            neg = 1 - neg
        else:
            tmp_pos.append(A_pos[-1])
            ans = ans * A_pos.pop()

    if neg:
        if A_pos:
            ans = ans * pow(tmp_neg[-1], MOD - 2, MOD) * A_pos.pop() % MOD
        else:
            ans = ans * pow(tmp_pos[-1], MOD - 2, MOD) * A_neg.pop() % MOD

    print(ans % MOD)

    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
MOD = 10**9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 1
is_pos = 0
for ai in A:
    if ai > 0:
        is_pos += 1
if is_pos == 0 and K % 2 == 1:
    sortA = sorted(A, key=abs)    
    for ai in sortA[:K]:
        ans = (ans * ai) % MOD
    print(ans)
    sys.exit()
        
sortA = sorted(A, reverse=True, key=abs)
# print(sortA)

pos_list = [0]
neg_list = [0]


for ai in sortA[:K]:
    if ai < 0:
        neg_list += [ai]
    elif ai > 0:
        pos_list += [ai]
    else:
        print(0)
        sys.exit()
first_pos = 0
first_neg = 0
for i in range(K, N):
    if first_pos > 0 and first_neg < 0:
        break
    elif ai > 0 and first_pos == 0:
        first_pos = ai
    elif ai < 0 and first_neg == 0:
        first_neg = ai
len_pos = len(pos_list)
len_neg = len(neg_list)
if len_pos == 0:
    if len_neg % 2 == 1:
        for i in range(1, len_neg):
            ans = (ans * neg_list[i]) % MOD
    else:
        ans = ans * first_pos
        for i in range(1, len_neg-1):
            ans = (ans * neg_list[i]) % MOD
    print(ans)
    sys.exit()
if len_neg % 2 == 1:
    for i in range(1, len_pos):
        ans = (ans * pos_list[i]) % MOD
    for i in range(1, len_neg):
        ans = (ans * neg_list[i]) % MOD
    print(ans)
    sys.exit()



pos2 = abs(pos_list[-1] * first_pos)
neg2 = abs(neg_list[-1] * first_neg)
if pos2 > neg2:
    ans = (ans * first_pos) % MOD
    for i in range(1, len_pos):
        ans = (ans * pos_list[i]) % MOD
    for i in range(1, len_neg-1):
        ans = (ans * neg_list[i]) % MOD
else:
    ans = (ans * first_neg) % MOD
    for i in range(1, len_pos-1):
        ans = (ans * pos_list[i]) % MOD
    for i in range(1, len_neg):
        ans = (ans * neg_list[i]) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = sorted(A, key=lambda x: abs(x), reverse=True)
    Bp = [x for x in B if x > 0]
    Bm = [x for x in B if x < 0]
    Bpm = [x for x in B if x != 0]
    Bmm = []
    for i in range(0, len(Bm)-1, 2):
        Bmm.append(Bm[i]*Bm[i+1])

    q = 10**9 + 7

    n_plus, n_zero, n_minus = 0, 0, 0
    for a in A:
        if a > 0:
            n_plus += 1
        elif a < 0:
            n_minus += 1
        else:
            n_zero += 1

    if K > n_plus + n_minus:
        return 0

    # ans != 0
    rest = K
    ans = 1
    if K > n_plus and (K-n_plus) % 2 == 1:
        # ans < 0
        for i in range(K):
            ans = (ans * Bpm[len(Bpm)-1-i]) % q
        return ans
    else:
        # ans > 0
        i, j = 0, 0
        while rest > 0:
            if rest >= 2 and j < len(Bmm):
                if i+1 < len(Bp):
                    if Bmm[j] >= Bp[i] * Bp[i+1]:
                        ans = (ans * (Bmm[j] % q)) % q
                        j += 1
                        rest -= 2
                    else:
                        ans = (ans * Bp[i]) % q
                        i += 1
                        rest -= 1
                elif i < len(Bp):
                    if Bmm[j] >= Bp[i]:
                        ans = (ans * (Bmm[j] % q)) % q
                        j += 1
                        rest -= 2
                    else:
                        ans = (ans * Bp[i]) % q
                        i += 1
                        rest -= 1
                else:
                    ans = (ans * (Bmm[j] % q)) % q
                    j += 1
                    rest -= 2
            else:
                ans = (ans * Bp[i]) % q
                i += 1
                rest -= 1
        return ans

        # i = 0
        # ip = 0
        # im = 0
        # while rest > 0:
        #     if B[i] > 0:
        #         ans = (ans * B[i]) % q
        #         i += 1
        #         ip += 1
        #         rest -= 1
        #     else:  # B[i] < 0
        #         if rest == 1:
        #             i += 1
        #         elif B[i+1] < 0:  # rest >= 2
        #             ans = (ans * (B[i]*B[i+1] % q)) % q
        #             i += 2
        #             im += 2
        #             rest -= 2
        #         else:  # rest >= 2 and B[i+1] > 0
        #             if Bp[ip] * Bp[ip+1] > Bm[im] * Bm[im+1]:
        #                 ans = (ans * (Bp[ip]*Bp[ip+1] % q)) % q


print(main())

Submission status: Wrong Answer

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

m = 1
o = 1
list.sort(reverse=True)
for i in range(K):
    m=m*list[i]

for i in range(K):
    o=o*list[N-i-1]
if m > o:
    print(m%1000000007)

else:
    print(o%1000000007)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
cnt=1
if n==k and 0 in a:
  print(0)
elif a[-1]<0 and k%2!=0:
  if 0 in a:
    print(0)
  else:
    for j in range(k):
      cnt*=a[-(j+1)]
      cnt%=1000000007
    print(cnt)
else:
  for i in range(k//2):
    if a[0]*a[1]>a[-1]*a[-2] and a[1]<0:
      cnt*=a[0]*a[1]
      cnt%=1000000007
      a.pop(0)
      a.pop(0)
    else:
      cnt*=a[-1]*a[-2]
      cnt%=1000000007
      a.pop(-1)
      a.pop(-1)
  if k%2!=0:
    cnt*=a[-1]
    cnt%=1000000007
    print(cnt)
  else:
    print(cnt)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n, k = inpl()
a = inpl()
data = [[abs(i), i < 0] for i in a]
all_minus = 0
for t in data:
    if t[1]:
        all_minus += 1
if all_minus == n:
    ans = 1
    data.sort()
    for i in range(k):
        ans = ans * data[i][0] % mod
    print(-ans % mod)
    exit()
data.sort(reverse=True)
last_minus = 0
last_plus = 0
ans = 1
minus_amount = 0
for i in range(k):
    elem, sign = data[i][0], data[i][1]
    if elem == 0:
        print(0)
        exit()
    ans = ans * elem % mod
    minus_amount += sign
    if sign:
        last_minus = elem
    else:
        last_plus = elem
if minus_amount % 2 == 0:
    print(ans % mod)
    exit()
if n == k:
    print(-ans % mod)
    exit()
tmp_plus = 0
tmp_minus = 0
FLAG = False
for i in range(k, n):
    elem, sign = data[i][0], data[i][1]
    if last_plus and sign and not tmp_minus:
        tmp_minus = elem
    elif last_minus and not sign and not tmp_plus:
        tmp_plus = elem
if tmp_plus == 0 and tmp_minus == 0:
    ans = 0
elif tmp_plus == 0:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
elif tmp_minus == 0:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
elif tmp_plus * last_plus > tmp_minus * last_minus:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
else:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
print(ans)

Submission status: Wrong Answer

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

mod = 10**9+7
res = 1
last_plus_index = -1
last_minus_index = -1

from collections import deque
d = deque(A)

for i in range(K):
    t = d.pop()
    res *= t
    if t < 0:
        last_minus_index = i
    if t > 0:
        last_plus_index = i

if res >= 0:
    print(res % mod)
    exit()

# if K-1 == last_minus_index:
#     for i in range(K, N):
#         if A[i] > 0:
#             res = res // A[last_minus_index] * A[i]
#             print(res % mod)
#             exit()
#         if i == N-1:
#             if last_plus_index != -1:
#                 res = res // A[last_plus_index] * A[K]
#                 print(res % mod)
#                 exit()
#             else:
#                 # 解が0以下
#                 A = sorted(A, reverse=True)
#                 res = 1
#                 for i in range(K):
#                     res *= A[i]
#                 print(res % mod)
#                 exit()
#
# else:
#     for i in range(K, N):
#         if A[i] < 0:
#             res = res // A[K-1] * A[i]
#             print(res % mod)
#             exit()
#         if i == N-1:
#             res = res // A[last_minus_index] * A[K]
#             print(res % mod)
#             exit()

Submission status: Wrong Answer

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

if k != 1:
    for i in range(n):
        a[i] = a[i]%modu

a.sort(reverse=True)

ans = a[0]

for i in range(1,k):
    ans = (ans*(a[i]))%modu

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()
mi = []
pl = []
zero = 0
for i in a:
    if i < 0:
        mi.append(i)
    elif i == 0:
        zero += 1
    else:
        pl.append(i)

if n-zero < k:
    print(0)
    exit()
if mi == []:
    ans = 1
    count = 0
    while count < k:
        ans *= a[-1-count]
        ans %= mod
        count += 1
    print(ans)
    
    exit()
if pl == []:
    if k%2:
        if zero:
            print(0)
        else:
            ans = 1
            count = 0
            while count < k:
                ans *= a[-1-count]
                ans %= mod
                count += 1
            print(ans)
            
    else:
        ans = 1
        count = 0
        while count < k:
            ans *= a[count]
            ans %= mod
            count += 1
        print(ans)
        
    exit()

ans = 0
sm = [mi[-1]]
for i in range(len(mi)-2,-1,-1):
    sm.append((sm[-1]*mi[i])%mod)
sp = [pl[-1]]
for i in range(len(pl)-2,-1,-1):
    sp.append((sp[-1]*pl[i])%mod)

for i in range(0,k+1,2):
    j = k-i
    
    if i > len(mi) or j > len(pl):
        continue
    x = 1
    if i > 0:
        x *= sm[i-1]
        x %= mod
    if j > 0:
        x *= sp[j-1]
        x %= mod
    
    ans = max(ans,x)
print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
from collections import defaultdict as dd
import sys
input=sys.stdin.readline
#t=int(input())
#while t:
n,k=map(int,input().split())
positive=[]
negative=[]
zero=[]
mod=10**9+7
l=list(map(int,input().split()))
l.sort(reverse=True)
for i in range(n):
    if(l[i]>0):
        positive.append(l[i])
    elif(l[i]==0):
        zero.append(0)
    else:
        negative.append(l[i])
positive.sort()
negative.sort(reverse=True)
com=[]
for i in range(len(negative)-1,-1,-2):
    com.append(abs(negative[i]))
    com.append(abs(negative[i-1]))
#print(com)
lp=len(positive)
ln=len(negative)
lc=len(com)
lz=len(zero)
mul=1
if(k%2==0):
    i=lp-1
    j=lc-1
    while(k and j>0 and i>0):
        if(com[j]*com[j-1]>positive[i]*positive[i-1]):
            mul=(mul*com[j]*com[j-1])%mod
            j-=2
        else:
            mul=(mul*positive[i]*positive[i-1])%mod
            i-=2
        k-=2
    while (k and i>0):
        mul=(mul*positive[i]*positive[i-1])%mod
        i-=2
        k-=2
    while(k and j>0):
        mul=(mul*com[j]*com[j-1])%mod
        j-=2
        k-=2
    if(k):
        mul=0
else:
    i=lp-1
    j=lc-1
    if(positive):
        mul=positive.pop()
        i-=1
        while(k and j>0 and i>0):
            if(com[j]*com[j-1]>positive[i]*positive[i-1]):
                mul=(mul*com[j]*com[j-1])%mod
                j-=2
            else:
                mul=(mul*positive[i]*positive[i-1])%mod
                i-=2
            k-=2
        while (k and i>0):
            mul=(mul*positive[i]*positive[i-1])%mod
            i-=2
            k-=2
        while(k and j>0):
            mul=(mul*com[j]*com[j-1])%mod
            j-=2
            k-=2
        if(k):
            mul=0
    else:
        mul=1
        kk=k
        for i in range(min(k,ln)):
            #print(negative[i])
            mul=((mul%mod)*((negative[i]+mod)%mod))%mod
            kk-=1
        if(kk):
            mul=0
print(mul)

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

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

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

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

            print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
import sys
from functools import reduce
input = sys.stdin.readline
N,K = map(int,input().split())
A = list(map(int,input().split()))

def solve(N,K,A):
    A.sort()
    minus = [a for a in A if a < 0][::-1]
    plus = [a for a in A if a > 0][::-1]

    prod = lambda x,y : ((x*y) % MOD)

    if K % 2 == 1 and len(plus) == 0:
        if 0 in A:
            return 0
        else:
            ans = reduce(prod,minus[:K],1)
            return ans % MOD

    ans = 1
    if K % 2 == 1:
        ans *= plus[0]
        plus2 = [p*q for p,q in zip(plus[1::2],plus[2::2])]
        minus2 = [p*q for p,q in zip(minus[::-1][::2],minus[::-1][1::2])]
        cand = sorted((plus2 + minus2),reverse=True)
        if len(cand) < K//2:
            return 0
        ans *= reduce(prod,cand[:K//2],1)
        ans %= MOD
    else:
        plus2 = [p*q for p,q in zip(plus[::2],plus[1::2])]
        minus2 = [p*q for p,q in zip(minus[::-1][::2],minus[::-1][1::2])]
        cand = sorted((plus2 + minus2),reverse=True)
        if len(cand) < K//2:
            return 0
        ans *= reduce(prod,cand[:K//2],1)
        ans %= MOD
    return ans

print(solve(N,K,A))
exit()

import random
from itertools import combinations
def ans(N,K,A):
    ans = -10**10
    for itr in combinations(range(N),K):
        t = 1
        for i in itr:
            t *= A[i]
        ans = max(ans,t)
    return ans % MOD

for i in range(100):
    N = 5 
    K = random.randint(1,N)
    A = [random.randint(-10,10) for i in range(N)]
    if solve(N,K,A) != ans(N,K,A):
        print(N,K,A)
        print(solve(N,K,A),ans(N,K,A))
        exit()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split(' '))
A = sorted(list(map(int, input().split(' '))))
mod = 10 ** 9 + 7
p = 0
for i in range(N):
    if A[i] >= 0:
        break
p = i
if (p == N - 1 and K % 2 != 0):
    ans = 1
    for i in range(K):
        ans *= A[-1 - i]
        ans %= mod
    print(ans%mod)
    exit()
minus = A[:p]
plus = sorted(A[p:],reverse=True)
len_m = len(minus)
len_p = len(plus)
m = 0
p = 0
ans = 1
while K > 0:
    if K >= 2 and m <= len_m - 2 and p <= len_p - 2:
        if minus[m] * minus[m] >= plus[p] * plus[p + 1]:
            ans *= minus[m] * minus[m + 1]
            ans %= mod
            m += 2
        else:
            ans *= plus[p] * plus[p + 1]
            ans %= mod
            p += 2
        K -= 2
    elif K >= 2 and m <= len_m - 2:
        ans *= minus[m] * minus[m + 1]
        ans %= mod
        m += 2
        K -= 2
    elif K >= 2 and p <= len_p - 2:
        ans *= plus[p] * plus[p + 1]
        ans %= mod
        p += 2
        K -= 2
    elif p <= len_p - 1:
        ans *= plus[p]
        ans %= mod
        p += 1
        K -= 1
    else:
        ans *= minus[m]
        ans %= mod
        m += 1
        K -= 1
print(ans%mod)

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
index_change = 0
ans = 1
for i in range(n-1):
    if a[i] <= 0 and a[i+1] > 0:
        index_change = i+1
        break
else:
    for i in range(1, k+1):
        ans *= a[-i]
        ans %= mod
    print(ans)
    exit()
l = 0
r = n-1
while k > 0:
    if k == 1:
        if r >= index_change:
            ans *= a[r]
            ans %= mod
            break
        else:
            ans *= a[l]*a[l+1]
            ans %= mod
            ans *= pow(a[r+1], mod-2, mod)
            ans %= mod
    else:
        left = a[l]*a[l+1]
        right = a[r]*a[r-1]
        if left >= right:
            ans *= left
            ans %= mod
            l += 2
        else:
            ans *= right
            ans %= mod
            r -= 2
        k -= 2
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
cross = 1
for i in range(k):
  cross *= a[i]
asw = cross % 1000000007
print(asw)

Submission status: Wrong Answer

Solution code:

from collections import deque



# for #!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase


# # region fastio

# BUFSIZE = 8192


# class FastIO(IOBase):
#     newlines = 0

#     def __init__(self, file):
#         self._fd = file.fileno()
#         self.buffer = BytesIO()
#         self.writable = "x" in file.mode or "r" not in file.mode
#         self.write = self.buffer.write if self.writable else None

#     def read(self):
#         while True:
#             b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
#             if not b:
#                 break
#             ptr = self.buffer.tell()
#             self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
#         self.newlines = 0
#         return self.buffer.read()

#     def readline(self):
#         while self.newlines == 0:
#             b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
#             self.newlines = b.count(b"\n") + (not b)
#             ptr = self.buffer.tell()
#             self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
#         self.newlines -= 1
#         return self.buffer.readline()

#     def flush(self):
#         if self.writable:
#             os.write(self._fd, self.buffer.getvalue())
#             self.buffer.truncate(0), self.buffer.seek(0)


# class IOWrapper(IOBase):
#     def __init__(self, file):
#         self.buffer = FastIO(file)
#         self.flush = self.buffer.flush
#         self.writable = self.buffer.writable
#         self.write = lambda s: self.buffer.write(s.encode("ascii"))
#         self.read = lambda: self.buffer.read().decode("ascii")
#         self.readline = lambda: self.buffer.readline().decode("ascii")


# sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
# input = lambda: sys.stdin.readline().rstrip("\r\n")
from bisect import bisect_left as bl
from math import log2,ceil
from heapq import heappush, heappop
from itertools import permutations
# from copy import deepcopy 
M = 1e9 + 7
def main():
    # for t in range(int(input())):
        # n = int(input())
        # d = dict()
        n,k = [int(j) for j in input().split()]
        l = [int(j) for j in input().split()]
        pos = []
        neg = []
        for i in range(n):
            if l[i]>=0:
                pos.append(l[i])
            else:
                neg.append(l[i])
        pos.sort()
        neg.sort()

        ppos = [i for i in pos]
        nneg = [j for j in neg]
        for i in range(1,len(pos)):
            ppos[i]=(ppos[i-1]*ppos[i])%M
        for i in range(1, len(neg)):
            nneg[i] *= (nneg[i-1]%M)
            # print(nneg)
            nneg[i] = nneg[i]%M
        negp = neg[::-1]
        nnegp = [j for j in negp]
        for i in range(1, len(negp)):
            nnegp[i] *= nnegp[i-1]
            nnegp[i] = nnegp[i]%M
        fans = -1*float('inf')
        if len(neg):
            nneg[0] = nneg[0]%M
            nnegp[0] = nnegp[0]%M
        # print(ppos, nnegp, nneg)
        for x in range(1,k+1):
            y = k-x
            # print(x,y,"ds")
            if x>len(ppos) or y>len(nneg):
                continue 

            tans = 1
            if y>0:
                if(y%2):
                    tans*=nnegp[y-1]
                else:
                    tans*=nneg[y-1]
            tans = tans%M*ppos[x-1]
            if y%2==0:
                fans = max(tans%M, fans)
            else:
                fans = max(tans%M-M, fans)
        if len(nneg)>=k:
            tans = 1
            y = k-1
            # print(nneg, y)
            if(y%2):
                tans*=nneg[y]
            else:
                tans*=nnegp[y]
            # tans = tans*ppos[x-1]
            if y%2==1:
                fans = max(tans%M, fans)
            else:
                fans = max(tans%M-M, fans)
        print(int(fans%M))



            # heappush(h, l[i])

        


        
        




# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

abs_a =sorted(a,key=lambda x:abs(x))
abs_ak = abs_a[-k:]

if 0 in abs_ak:
    ans=0
    
elif all( aa<0 for aa in a ):
    ans=1
    for aa in a[:k]:
        ans= ans*aa%mod
    
else:
    n_nega = sum(aa<0 for aa in abs_ak )   
    if n_nega%2==0:
        ans=1
        for c in abs_ak:
            ans = ans*c%mod
    else:    
        nokori = abs_a[:-k]
        
        maxposi=0
        maxnega=0
        found_posi=False
        found_nega=False
        for i in nokori[::-1]:
            if i<0 and not found_nega:
                    maxnega=i
                    found_nega=True
            if i>0 and not found_posi:
                    maxposi=i
                    found_posi=True
            if found_posi and found_nega:
                break

        minposi=float("inf")
        minnega=float("inf")
        found_posi_inabsak=False
        found_nega_inabsak=False
        for i in abs_ak:
            if i<0 and not found_nega_inabsak:
                    minnega=i
                    found_nega_inabsak = True
            if i>0 and not found_posi_inabsak:
                    minposi=i
                    found_posi_inabsak = True
            if found_posi_inabsak and found_nega_inabsak:
                break
        
#         (found_nega and found_posi and found_posi_inabsak and found_nega_inabsak
        
        if abs(maxnega/minposi) <= abs(maxposi/minnega
                                      ) or not found_nega or not found_posi_inabsak:
            ans=1
            swap=False
            for c in abs_ak:
                if c==minnega and not swap:
                    ans = ans*maxposi%mod
                    swap=True
                else:
                    ans = ans*c%mod
        else:
            ans=1
            swap=False
            for c in abs_ak:
                if c==minposi and not swap:
                    ans = ans*maxnega%mod
                    swap=True
                else:
                    ans = ans*c%mod
print(ans%mod)

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
a.sort()
cnt = 0
if n > k:
    for x in a:
        if x < 0: cnt += 1
    if cnt%2 == 1:
        a.pop(cnt - 1)
        n -= 1

if k%2 == 1 and a[n - 1] < 0:
    if 0 in a:
        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:
        #print(a)
        ans = (ans * p)%mod
        a.pop(n - 1)
        a.pop(n - 2)
        #print(ans)
    else:
        ans = (ans * m)%mod
        a.pop(1)
        a.pop(0)
    n -= 2
if k%2 == 1:
    ans = max((ans * a[n - 1]), (ans * a[0]))
print(ans%mod)