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:
'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineering College

'''
from os import path
import sys
from functools import cmp_to_key as ctk
from collections import deque,defaultdict as dd 
from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
from itertools import permutations
from datetime import datetime
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input()
def mi():return map(int,input().split())
def li():return list(mi())
abc='abcdefghijklmnopqrstuvwxyz'
mod=1000000007
#mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]

def bo(i):
    return ord(i)-ord('a')

file = 0

def solve():
    



    # for _ in range(ii()):

    n,k=mi()
    a=li()
    pos,neg=[],[]
    zero=0
    for i in a:
        if i<0:
            neg.append(i)
        if i>0:
            pos.append(i)
        if i==0:
            zero+=1
    if n==k:
        ans1=1
        for i in a:
            ans1*=i
            ans1%=mod
        print(ans1)
        exit(0)

    if k>(len(pos)+len(neg)):
        print(0)
        exit(0)
    
    if len(pos)==0 and k%2:
        if zero:
            print(0)
        else:
            neg.sort(reverse=True)
            ans1=1
            for i in range(k):
                ans1*=neg[i]
                ans1%=mod
            print(ans1)
        exit(0)
    ans=[]

    for i in pos:
        ans.append([i,0])
    for i in neg:
        ans.append([abs(i),1])
    ans.sort(reverse=True)
    f=-1
    f1=-1
    c=0
    for i in range(k):
        if ans[i][1]:
            c+=1
            f=i
        else:
            f1=i
    if c%2:
        if len(ans)==k:
            print(0)


        else:
            ans1=1
            for i in range(k):
                if i==f or i==f1:
                    continue
                ans1*=ans[i][0]
                ans1%=mod

            if(f1!=-1):
                f1=ans[f1][0]
            f=ans[f][0]
            f3,f4=-1,-1
            for i in range(k,len(ans)):
                if ans[i][1] and f3==-1:
                    f*=ans[i][0]
                    f3=1
                if ans[i][1]==0 and f4==-1:
                    if f1==-1:
                        f1=ans[i][0]
                    else:
                        f1*=ans[i][0]
                        f4=1
                if f3!=-1 and f4!=-1:
                    break
            if f3==-1:
                ans1*=f1
                ans1%=mod
            elif(f4==-1):
                ans1*=f
                ans1%=mod
            elif(f>f1):
                ans1*=f
                ans1%=mod
            else:
                ans1*=f1
                ans1%=mod
            print(ans1)

    else:
        ans1=1
        for i in range(k):
            ans1*=ans[i][0]
            ans1%=mod
        print(ans1)

























  
















if __name__ =="__main__":

    if(file):

        if path.exists('input1.txt'):
            sys.stdin=open('input1.txt', 'r')
            sys.stdout=open('output1.txt','w')
        else:
            input=sys.stdin.readline
    solve()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
li_a = list(map(int, input().split()))
mod = 10**9+7
li = []
lll = 0
for i in li_a:
    if i < 0:
        li.append((abs(i), -1))
        lll += 1
    else:
        li.append((i, 1))
li.sort()
if lll == n:
    ans = 1
    for i in range(k):
        ans *= -li[i][0]
        ans %= mod
    print(ans)
    exit()
ans = 1
guki = 1
for i in range(n-1, n-k-1, -1):
    ans *= li[i][0]
    ans %= mod
    guki *= li[i][1]
if guki > 0:
    print(ans)
else:
    P, M, p, m = 10**6, 1000000, 1000000, 1000000
    P1, M1, p1, m1 = True, True, True, True
    for i in range(n-k, n-1):
        if li[i][1] > 0:
            Plus = li[i][0]
            P = i
            P1 = False
            break
    for i in range(n-k, n-1):
        if li[i][1] < 0:
            Mini = li[i][0]
            M = i
            M1 = False
            break
    for i in range(n-k, -1, -1):
        if li[i][1] > 0:
            plus = li[i][0]
            p = i
            p1 = False
            break
    for i in range(n-k, -1, -1):
        if li[i][1] < 0:
            mini = li[i][0]
            m = i
            m1 = False
            break
    ans1 = 1
    ans2 = 1
    if not P1 and not m1:
        for i in range(n-1, n-k-1, -1):
            if i == P:
                continue
            ans1 *= li[i][0]
            ans1 %= mod
        ans1 *= li[m][0]
        ans1 %= mod
    if not p1 and not M1:
        for i in range(n-1, n-k-1, -1):
            if i == M:
                continue
            ans1 *= li[i][0]
            ans1 %= mod
        ans2 *= li[p][0]
        ans2 %= mod
    if p1 or P1 or M1 or m1:
        print(max(ans1, ans2))
    else:
        ans = 1
        for i in range(k):
            ans *= -li[i][0]
            ans %= mod
        print(ans)

Submission status: Wrong Answer

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

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

B=[]
C=[]
Z=[]

for a in A:
    if a>0:
        B.append(a)
    elif a<0:
        C.append(-a)
    else:
        Z.append(0)

B.sort(reverse=True)
C.sort(reverse=True)

if K==len(B)+len(C):
    ANS=1
    for b in B:
        ANS=ANS*b%mod
    for c in C:
        ANS=ANS*(-c)%mod

    if len(C)%2==1 and Z!=[]:
        print(0)
    else:
        print(ANS)
    sys.exit()

if K>len(B)+len(C):
    print(0)
    sys.exit()

if B==[]:
    if Z==[] and K%2==0:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
            
    elif Z==[] and K%2==1:
        C.reverse()
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
        print(-ANS%mod)
        
    elif K%2==1:
        print(0)
    else:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod

    sys.exit()

if K<=len(B):
    S=1
    for i in range(K):
        S=S*B[i]%mod

    ind=0
    while True:
        if ind+1<len(C) and K-2-ind>=0 and C[ind]*C[ind+1]>B[K-1-ind]*B[K-2-ind]:
            S=S*C[ind]*C[ind+1]*pow(B[K-1-ind]*B[K-2-ind],mod-2,mod)%mod
            ind+=2
        else:
            break

    print(S%mod)

else:
    if (K-len(B))%2==0:
        S=1
        for i in range(len(B)):
            S=S*B[i]%mod

        for j in range(K-len(B)):
            S=S*C[j]%mod

        ind=K-len(B)

    else:
        S=1
        for i in range(len(B)-1):
            S=S*B[i]%mod

        for j in range(K-len(B)+1):
            S=S*C[j]%mod

        ind=K-len(B)+1
        

    while True:
        if ind+1<len(C) and K-2-ind>=0 and C[ind]*C[ind+1]>B[K-1-ind]*B[K-2-ind]:
            S=S*C[ind]*C[ind+1]*pow(B[K-1-ind]*B[K-2-ind],mod-2,mod)%mod
            ind+=2
        else:
            break

    print(S%mod)

Submission status: Wrong Answer

Solution code:
from math import log, log10, log2

def solve():
    MOD = 10**9 + 7

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

    numPos, num0, numNeg = 0, 0, 0
    for A in As:
        if A > 0:
            numPos += 1
        elif A == 0:
            num0 += 1
        else:
            numNeg += 1

    if numPos + numNeg < K:
        ans = 0
    else:
        posAs, negAs = [], []
        prod = 1
        for A in As:
            if A > 0:
                posAs.append(A)
                prod *= A
                prod %= MOD
            elif A < 0:
                negAs.append(A)
                prod *= A
                prod %= MOD
        N = numPos + numNeg

        if K == N and prod < 0:
            if num0 > 0:
                ans = 0
            else:
                ans = prod

        elif K%2 != 0 and numPos == 0:
            if num0 > 0:
                ans = 0
            else:
                negAs.sort(reverse=True)
                ans = 1
                for A in negAs[:K]:
                    ans *= A
                    ans %= MOD

        else:
            posAs.sort(reverse=True)
            negAs.sort()
            acc = 0
            accPoss = [acc]
            for A in posAs:
                acc += log(A)
                accPoss.append(acc)
            acc = 0
            accNegs = [acc]
            for A in negAs:
                acc += log(-A)
                accNegs.append(acc)

            ans = -1
            xMax = -1
            for x in range(0, K+1, 2):
                y = K - x
                if x > numNeg or y > numPos:
                    break
                prod = accNegs[x] + accPoss[y]
                if prod > ans:
                    ans = prod
                    xMax = x

            ans = 1
            for A in negAs[:xMax]:
                ans *= A
                ans %= MOD
            for A in posAs[:K-xMax]:
                ans *= A
                ans %= MOD

    print(ans % MOD)


solve()

Submission status: Wrong Answer

Solution code:
def solution():
    n, k = map(int, input().split())
    a_list = sorted(list(map(int, input().split())),
                    key=lambda a: abs(a), reverse=True)
    # import numpy as np
    # a_list = sorted([int(el) for el in np.random.randint(-(10**9), 10**9, 2*10**5)],
    #                 key=lambda a: abs(a), reverse=True)
    # print(a_list[:10])
    # n, k = 2*10**5, 2*10**5


    MOD = 10 ** 9 + 7

    num0 = a_list.count(0)
    if n - k < num0:
        return 0

    a_neg = [a for a in a_list if a < 0]
    a_pos = [a for a in a_list if a > 0]

    if all([a<0 for a in a_list]) and k%2 == 1:
        if 0 in a_list:
            return 0
        ans = 1
        a_list = reversed(a_list)
        for i, a in enumerate(a_list):
            ans *= a % MOD
            if i == k - 1:
                return ans % MOD
    else:
        ans = 1
        pn = 1
        for i, a in enumerate(a_list):
            # print(1111, i, a, ans, pn)
            if i>=k-1:
                if pn < 0 and a >= 0:
                    continue
                else:
                    ans *= a % MOD
                    return ans % MOD
            ans *= a % MOD
            pn *= 1 if a>0 else -1

print(solution())

Submission status: Wrong Answer

Solution code:
s=list(map(int,input().split()))
b=s[1]
m=list(map(int,input().split()))
m.sort(reverse=True)
product=1
M = 10**9+7
for i in range(b):
    product=(product*m[i])/M
print(product)

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
    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 pm == -1 and 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:

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


arr = [ int(i) for i in input().split() ]


mod = (10**9)+7

pre = [ 0 for i in range(n) ]
suff = [ 0 for i in range(n+1) ]

pre[0] = arr[0]

for i in range(1, n):
	pre[i] = pre[i-1] * arr[i]

suff[n] = 1
suff[n-1] = arr[n-1]

for i in range(n-2,-1,-1):
	suff[i] = suff[i+1] * arr[i]

max_ans = suff[n-k]


for i in range(k):
	fromLeft = k - i 
	ans = pre[i] * suff[n-fromLeft + 1]
	max_ans = max(max_ans, ans)

max_ans %= mod
print(max_ans)

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)
    exit()
tmp_plus = 0
tmp_minus = 0
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 last_plus == 0:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
elif last_minus == 0:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
elif tmp_plus / last_minus > tmp_minus / last_plus:
    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:
import math
ans=1
ans_list=[]
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
B=A

for  i in range(int(K/2)):
    if A[0]*A[1]>=A[-1]*A[-2]:
        ans=ans*A[0]*A[1]
        del A[1]
        del A[0]
    else:
        ans=ans*A[-1]*A[-2]
        del A[-2]
        del A[-1]
if K%2>0:
    ans=ans*A[0]

if N-K==1 and K%2==1:
    ans=ans*A[0]
    if abs(B[0])>abs(B[-1]):
        ans=ans/B[0]
    else:
        ans=ans/B[1]

print(int(ans%1000000007))

Submission status: Wrong Answer

Solution code:
P = 1000000007

n,k=map(int,input().split())
a = [int(i) for i in input().split()]
ans = 1
neg = 0
for i in a:
	if i<0:neg+=1
if neg==n:
	a.sort(reverse=True)
	for i in range(k):
		ans = (ans*a[i])%P
	print(ans)
	exit(0)

a.sort()
l = 0
r = n-1
while k>0:
	if k>1:
		Ol = a[l]*a[l+1]
		Or = a[r]*a[r-1]
		if Ol > Or:
			ans = (ans*(Ol%P))%P
			l+=2
		else:
			ans = (ans*(Or%P))%P
			r-=2
		k-=2
	else:
		ans = (ans*a[r])%P
		k-=1
print(ans)
# ~ 5 4
# ~ 0 -1 -2 -3 -4
# ~ 7 6
# ~ -1 -2 -3 0 1 2 3
# ~ -1 -2 -3 -4 -5

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] == 1:
                    K -= 1
                    ans *= -A[i]
                    ans %= mod
                if K == 0:
                    break
            else:
                ans = 1
                for i in range(N-K_, N):
                    ans *= -A[i]
                    ans %= mod
                print(ans)
                exit()
            print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
#pyrival orz
import os
import sys
from io import BytesIO, IOBase

"""
    for _ in range(int(input())):
    n,m=map(int,input().split())
    n=int(input())
    a = [int(x) for x in input().split()]
"""

def main():
    n,k=map(int,input().split())
    a = [int(x) for x in input().split() if x!='0']
    fl=n-len(a)
    # print(fl)
    mod=10**9+7
    a.sort(key=lambda v:-abs(v))
    def ft(a):
        ans=1
        for x in a:
            ans=(ans*x)%mod
        return ans
    
    # print(a)
    def solve(a,k,fl):
        ans=1
        nv=1
        for x in a:
            if k==0:
                break
            if x>0:
                ans=(ans*x)%mod
                k-=1
            if x<0:
                if nv!=1 and k>1:
                    k-=2
                    ans=(ans*x*nv)%mod
                    nv=1
                elif nv==1:
                    nv=x
        if k and fl:
            return (0,False)
        if k==1:
            assert(nv!=1)
            return (ans*nv%mod,True)
        assert(k==0)
        return (ans,False)
    
    pv,nv=0,0
    for x in a:
        if x>0:
            pv+=1
        if x<0:
            nv+=1
    
    n=len(a)
    if k>n:
        print(0)
        exit(0)
    
    if k==n:
        if nv%2 and fl:
            print(0)
        else:
            print(ft(a))
        exit(0)
    
    if nv==0:
        print(ft(a[:k]))
        exit(0)
    
    if pv==0 and k%2==0:
        print(ft(a[:k]))
        exit(0)
    
    if pv==0 and k%2:
        if fl:
            print(0)
        else:
            a=a[::-1]
            print(ft(a[:k]))
        exit(0)
    
    ans=solve(a,k,fl)
    if ans[1]:
        a=a[::-1]
        ans=solve(a,k,fl)
    print(ans[0])
# 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")

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

from fractions import Fraction

MODULUS = 10**9+7

def all_negative(arr):
    for _, s in arr:
        if s != -1: return False
    return True

def has_negative(arr):
    for _, s in arr:
        if s == -1: return True
    return False

def has_positive(arr):
    for _, s in arr:
        if s == 1: return True
    return False

def largest_negative(arr):
    candidates = []
    for a, s in arr:
        if s == -1: candidates += [a]
    return max(candidates)

def largest_positive(arr):
    candidates = []
    for a, s in arr:
        if s == 1: candidates += [a]
    return max(candidates)

def smallest_negative(arr):
    candidates = []
    for a, s in arr:
        if s == -1: candidates += [a]
    return min(candidates)

def smallest_positive(arr):
    candidates = []
    for a, s in arr:
        if s == 1: candidates += [a]
    return min(candidates)

def prod(arr, MODULUS=None):
    ret = 1
    for a in arr:
        ret *= a
        if MODULUS is not None:
            ret = ret % MODULUS
    return ret

def sgn(x):
    if x == 0: return 0
    if x > 0: return 1
    if x < 0: return -1
    assert(False)

N, K = input().split(' ')
K = int(K)

A = input().split(' ')
A = list(map(int, A))
A = [(abs(a), sgn(a)) for a in A]
A = sorted(A)[::-1]

# print(f"A={A}")

if prod(s for (_, s) in A[0:K]) in [0, 1]:
    print(prod([a for (a, _) in A[0:K]], MODULUS))
    exit(0)

chosen, not_chosen = A[0:K], A[K:]

penalty_one = float("-inf")
if has_positive(not_chosen):
    penalty_one = Fraction(largest_positive(not_chosen), smallest_negative(chosen))

penalty_two = float("-inf")
if has_positive(chosen) and has_negative(not_chosen):
    penalty_two = Fraction(largest_negative(not_chosen), smallest_positive(chosen))

if penalty_one == float("-inf") and penalty_two == float("-inf"):
    if all_negative(chosen) and all_negative(not_chosen):
        A = A[::-1]
        print(prod([a*s for (a, s) in A[0:K]], MODULUS))
    else:
        print(0)
    exit(0)

start = prod([a for (a, _) in chosen], MODULUS)

# print(penalty_one, penalty_two)

penalty = max(penalty_one, penalty_two)

start *= penalty.numerator
start *= pow(penalty.denominator, MODULUS-2, MODULUS)

start = ((start % MODULUS) + MODULUS) % MODULUS

print(start)

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def rev(i):
    ni = i
    ans = 1
    t = 10**9+5
    mod = 10**9+7
    while t > 0:
        if t&1:
            ans = (ans*ni)%mod
        t >>= 1
        ni = (ni**2)%mod
    return ans

def main():
    n,k = map(int,ipt().split())
    a = [(abs(int(i)),int(i)) for i in ipt().split()]
    Mi = 10**9
    Ma = -10**9
    mod = 10**9+7
    a.sort(reverse=True)
    if n == k:
        ans = 1
        for i in a:
            ans = (ans*i[1])%mod
        print(ans)
        exit()
    for i in a:
        if Ma < i[1]:
            Ma = i[1]
        if Mi > i[1]:
            Mi = i[1]
    if Ma < 0 and k&1:
        ans = 1
        for i,ai in enumerate(a[::-1]):
            ans = (ans*ai[0])%mod
            if i == k-1:
                break
        print((-ans)%mod)
        exit()
    pp = None
    pm = None
    ans = 1
    s = 1
    for i,ai in enumerate(a[:k:]):
        ans = ans*ai[0]%mod
        if ai[1] == 0:
            print(0)
            exit()
        elif ai[1] > 0:
            pp = ai[0]
        else:
            pm = ai[0]
            s *= -1
    if s == 1:
        print(ans)
        exit()
    np = 0
    nm = 0
    for ai in a[k::]:
        if ai[1] > 0 and not np:
            np = ai[0]
        elif ai[1] < 0 and not nm:
            nm = ai[0]
        if np and nm:
            break
    if pp == None:
        if np == None:
            print(0)
        else:
            print(np)
    elif nm == None and np == None:
        print(0)
    elif nm == None:
        print(ans*rev(pm)*np%mod)
    elif np == None:
        print(ans*rev(pp)*nm%mod)
    else:
        if nm*pm < np*pp:
            print(ans*rev(pm)*np%mod)
        else:
            print(ans*rev(pp)*nm%mod)



    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
A_minus = []
A_plus = []
A_zero = []
for i in A:
    if i < 0:
        A_minus.append(i)
    elif i > 0:
        A_plus.append(i)
    else:
        A_zero.append(i)
A_plus.sort(reverse=True)
A_minus.sort()
ans = 1
while K > 0:
    if K > 1:
        if (len(A_plus) >= 2) & (len(A_minus) >= 2):
            if (A_plus[0] * A_plus[1] >= A_minus[0] * A_minus[1]):
                a0 =  A_plus.pop()
                a1 = A_plus.pop()
            else:
                a0 = A_minus.pop()
                a1 = A_minus.pop()
            ans *= a0 * a1
            K -= 2
            ans = ans % mod
            continue
    if len(A_plus) >= 1:
        a0 = A_plus.pop()
        ans *= a0
        K -= 1
        continue
    elif len(A_minus) >= 1:
        a0 = A_minus.pop(-1)
        ans *= a0
        K -= 1
    elif len(A_zero) >= 1:
        ans *= 0
        K -= 1
    ans = ans % mod
print(ans % mod)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 10**9 + 7

n, k = map(int, input().split())
a = [int(item) for item in input().split()]
# Use all
if n == k:
    ans = 1
    for item in a:
        ans *= item
        ans %= MOD
    print(ans)
    exit()
plus = 0; minus = 0; zero = 0
p = []; m = []
for item in a:
    if item > 0:
        plus += 1
        p.append(item)
    elif item == 0:
        zero += 1
    else:
        minus += 1
        m.append(-item)
p.sort()
m.sort()
# plus only, minus only
if plus == 0:
    if zero:
        print(0)
        exit()
    ans = 1
    for item in m[:k]:
        ans *= -item
        ans %= MOD
    print(ans)
    exit()
if minus == 0:
    if plus >= k:
        ans = 1
        for item in p:
            ans *= item
            ans %= MOD
        print(ans)
        exit()
    else:
        print(0)
        exit()

# Can make it positive
if k <= (minus // 2) * 2 + plus:
    if k % 2 == 0:
        ans = 1
    else:
        ans = p.pop()
        k -= 1
    for i in range(k // 2):
        pval = 0; mval = 0
        if len(p) > 1:
            pval = p[-1] * p[-2]
        if len(m) > 1:
            mval = m[-1] * m[-2]
        if pval > mval:
            p.pop(); p.pop()
            ans *= pval
            ans %= MOD
        else:
            m.pop(); m.pop()
            ans *= mval
            ans %= MOD
    print(ans)
    exit()
# Cannot make positive
else:
    if zero > 0:
        print(0)
        exit()
    else:
        # Not occur
        exit()

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
m,p=[],[]
pr=10**9+7
z=0
for i in A:
    if i>=0:
        p.append(i)
    elif i:
        m.append(i)
    else:
        z+=1
lm=len(m)
m.sort()
p.sort(reverse=1)
lp=len(p)
if N==K:
    a=1
    for i in A:
        a=a*i%pr
    print(a)
    exit()
mm,pp=[],[]
for i in range(1,lm,2):
    mm.append((m[i-1]*m[i]%pr,0,i))
for i in range(1,lp,2):
    pp.append((p[i-1]*p[i]%pr,1,i))
l=mm+pp
l.sort(reverse=1)
def gya(n):
    return pow(n,pr-2,pr)
mt,pt=-1,-1
a=1
if len(l)*2>=K:
    for i in l[:K//2]:
        a=a*i[0]%pr
        if i[1]:
            pt=i[2]
        else:
            mt=i[2]
    if K%2:
        if pt<lp-1:
            a=a*p[pt+1]%pr
        elif pt==-1:
            a=1
            m=m[::-1]
            for i in m[:K]:
                a=a*i%pr
        else:
            a=a*gya(p[pt])*m[mt+1]*m[mt+2]%pr
else:
    for i in l:
        a=a*i[0]%pr
        if i[1]:
            pt=i[2]
        else:
            mt=i[2]
    a=a*p[pt+1]%pr
print(a)