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:
MOD = 10 ** 9 + 7

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

alst.sort()

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int,input().split())
    a = list(map(int,input().split()))
    p = []
    m = []
    z = []
    from collections import deque

    for aa in a:
        if aa > 0:
            p.append(aa)
            continue
        if aa < 0:
            m.append(aa)
            continue
        z.append(aa)
    if len(p) + len(m) < k or k == 0:
        print(0)
        return
    mod = 10 ** 9 + 7
    p.sort(reverse=True)
    m.sort()
    deq_p = deque(p)
    deq_m = deque(m)
    dp = [-1] * (k+1)
    dp[0] = 1
    if len(deq_p) > 0:
        dp[1] = deq_p.popleft() #% mod
    else:
        dp[1] = deq_m.popleft() #% mod
    for i in range(2,k+1):
        b1 = -1
        b2 = -1
        flg = ''
        if len(deq_p) > 0:
            p1 = deq_p.popleft()
            b1 = dp[i-1] * p1 #% mod
        else:
            flg = 'p'
        if len(deq_m) > 1:
            m1 = deq_m.popleft()
            m2 = deq_m.popleft()
            b2 = dp[i-2] * m1 * m2 #% mod
        else:
            flg = 'm'

        if b1 >= b2 :
            if flg == '':
                deq_m.appendleft(m2)
                deq_m.appendleft(m1)
                dp[i] = b1
            else:
                dp[i] = b1
        elif b2 > b1 :
            if flg == '':
                deq_p.appendleft(p1)
                dp[i] = b2
            else:
                dp[i] = b2
    print(dp[k]%mod)
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
p=[]
m=[]
z=0
a.sort(reverse=True)
for i in range(n):
    if a[i]>0:
        p.append(a[i])
    elif a[i]==0:
        z+=1
    else:
        m.append(a[i])
nump=len(p)
numm=len(m)
ans=1
if nump+numm<k:
    print(0)
elif numm<2 and nump>=k:
    for i in range(k):
        ans*=p[i]
        ans%=10**9+7
    print(ans)
elif 2*(numm//2)+nump<k:
    if z!=0:
        print(0)
    else:
        for i in range(k):
            ans*=a[i]
            ans%=10**9+7
        print(ans)
elif  nump==0:
    if z!=0 and k%2==1:
        print(0)
    elif z!=0 and numm<k:
        print(0)
    else:
        if k%2==0:
            m.sort()
            for i in range(k):
                ans*=m[i]
                ans%=10**9+7
        else:
            m.sort(reverse=True)
            for i in range(k):
                ans*=m[i]
                ans%=10**9+7
        print(ans)
else:
    if k%2==1:
        ans*=p[0]
    m.sort()
    nump=(nump-1)//2
    numm=numm//2
    nump1=0
    nump2=0
    numm1=0
    numm2=0
    for i in range(k//2):
        if nump2==nump:
            nump1=1
        else:
            nump1=p[nump2*2]*p[nump2*2+1]
        if numm2==numm:
            numm1=1
        else:
            numm1=m[numm2*2]*m[numm2*2+1]
        if numm1>nump1:
            num=numm1
            numm2+=1
        else:
            num=nump1
            nump2+=1
        ans*=num
        ans%=10**9+7
    print(ans)

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 = 1

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)
    # print(ans)
    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]
                    f%=mod
                    f3=1
                if ans[i][1]==0 and f4==-1:
                    if f1==-1:
                        f1=ans[i][0]
                    else:
                        f1*=ans[i][0]
                        f1%=mod
                        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:
from pprint import pprint
import sys

mod = 10**9 + 7

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().strip().split()))

# 0も入れておく
pos_list = []
neg_list = []
for a_i in A:
    if a_i >= 0:
        pos_list.append(a_i)
    else:
        neg_list.append(a_i)

pos_list.sort(reverse=True)
neg_list_reverse = sorted(neg_list, reverse=True)
neg_list.sort()


lp = len(pos_list)
ln = len(neg_list)

ans = -float("inf")
# 最大の正の場合
for NK in range(0, K+1, 2):
    c = 0
    tmp = 1
    for i in range(NK):
        if i >= ln:
            break
        tmp *= neg_list[i] * (-1)
        tmp %= mod
        c += 1
    for i in range(K - NK):
        if i >= lp:
            break
        tmp *= pos_list[i]
        tmp %= mod
        c += 1

    if c == K:
        ans = max(ans, tmp)
if ans != -float("inf"):
    print(ans)
    sys.exit()

# 最大がマイナスになる場合
for NK in range(1, K+1, 2):
    print(NK)
    c = 0
    tmp = 1
    for i in range(NK):
        if i >= ln:
            break
        tmp *= neg_list_reverse[i] * (-1)
        tmp %= mod
        c += 1
    for i in range(K - NK):
        if i >= lp:
            break
        tmp *= pos_list[i]
        tmp %= mod
        c += 1

    if c == K:
        tmp = tmp * (-1) % mod
        # print(tmp)
        ans = max(ans, tmp)

print(ans)

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()]
    pv,nv,zr=[],[],[]
    for x in a:
        if x>0:
            pv.append(x)
        if x<0:
            nv.append(x)
        if x==0:
            zr.append(x)
    mod=10**9+7
    def posv(a,k):
        a.sort(lambda v:abs(v),reverse=True)
        ans=1
        nv,pv=1,-1
        for x in a:
            if k==0:
                break
            if x>0:
                if pv>0:
                    ans=(ans*pv)%mod
                    k-=1
                pv=x
            if x<0:
                if nv<0 and k>1:
                    ans=(ans*nv*x)%mod
                    k-=2
                    nv=1
                else:
                    nv=x
        if k==0:
            return (ans,True)
        if k==1 and pv>0:
            return (ans*pv%mod,True)
        return (ans*nv%mod,False)
    ans=posv(a,k)
    if ans[1]:
        print(ans[0])
        exit(0)
    
    if zr:
        print(0)
        exit(0)
    
    ans=1
    a=a[::-1]
    for x in a[:k]:
        ans=(ans*x)%mod
    print(ans)
 
# 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:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N,K = LI()
    A = LI()

    ans = 1
    ma = max(A)
    if ma <= 0 and K % 2:
        x = sorted(A,reverse=True)
        for i in range(K):
            ans = (ans * A[i]) % MOD
        print(ans)
        return

    x = sorted(A, key=lambda x: abs(x), reverse=True)
    m = 0
    for i in range(K):
        ans = (ans * x[i]) % MOD
        if x[i] < 0 :m += 1

    if K == N or m % 2 == 0:
        print(ans)
        return
    if x[K] == 0:
        print(0)
        return
    else:
        if m == K:
            ans = (ans * pow(x[K-1],MOD-2,MOD) * max(x[K:])) % MOD

        else:
            K1 = -1
            for i in range(K+1,N):
                if x[K] * x[i] < 0:
                    K1 = i

            f1 = 0.0
            f2 = 0.0
            i0 = -1
            i1 = -1
            for i in range(K-1,-1,-1):
                if x[i] * x[K] < 0:
                    i0 = i
                    f1 = x[K] / x[i]
                    break

            if K1 >= 0:
                for i in range(K-1,-1,-1):
                    if x[i] * x[K1] < 0:
                        i1 = i
                        f2 = x[K1] / x[i]
                        break

            if abs(f1) >= abs(f2):
                ans = (ans * pow(x[i0],MOD-2,MOD) * x[K]) & MOD
            elif i1 >= 0:
                ans = (ans * pow(x[i1],MOD-2,MOD) * x[K1]) & MOD

        print(ans)
        return



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def main():
    from collections import Counter
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    posi = [a for a in A if a > 0]
    nega = [a for a in A if a < 0]
    posi.sort(reverse=True)
    nega.sort(reverse=True)
    A.sort(reverse=True, key=abs)
    if len(posi) + len(nega) < K:
        # 0を含まなければいけないとき
        return print(0)

    ans = modint(1)
    if K % 2 == 1 and len(posi) < K:
        # 結果が負数
        # 絶対値が小さいやつをK個取ってくる
        A.sort(key=abs)
        for a in A[:K]:
            ans *= a
    else:
        # 結果が正になるように注意しなければいけない
        # skipしてかけるものがなくなったらこわい
        # 負数がK以下の奇数個しかないとハマる
        if sum(a < 0 for a in A[:K]) % 2 == 0:
            for a in A[:K]:
                ans *= a
        else:
            ans1 = []  # 正を取り除く
            ans2 = []  # 負を取り除く
            posi = [a for a in A[:K] if a > 0]
            nega = [a for a in A[:K] if a < 0]
            p_remove = False
            for a in A[:K][::-1]:
                if a > 0 and not p_remove:
                    p_remove = True
                    continue
                ans1.append(a)
            n_remove = False
            for a in A[:K][::-1]:
                if a < 0 and not n_remove:
                    n_remove = True
                    continue
                ans2.append(a)
            mul1 = 0  # 一番大きい正
            mul2 = 0  # 　一番大きい負
            for a in A[K:]:
                if mul1 == 0 and a > 0:
                    mul1 = a
                if mul2 == 0 and a < 0:
                    mul2 = a
                if mul1 != 0 and mul2 != 0:
                    break
            ans1.append(mul2)
            ans2.append(mul1)
            s1 = sum(abs(a) for a in ans1)
            s2 = sum(abs(a) for a in ans2)

            if len(posi) == 0 or mul2 == 0:
                for a in ans2:
                    ans *= a
            elif len(nega) == 0 or mul1 == 0:
                for a in ans1:
                    ans *= a
            else:
                from random import randint
                if s1 < s2:
                    for a in ans2:
                        ans *= a
                elif s1 > s2:
                    for a in ans1:
                        ans *= a
                elif randint(0, 1) == 0:
                    for a in ans2:
                        ans *= a
                else:
                    for a in ans1:
                        ans *= a

    print(int(ans) % MOD)


if __name__ == '__main__':
    main()

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]
    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 * B[N-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:
import sys
import  math
import fractions
from collections import defaultdict
import heapq
from bisect import bisect_left,bisect

stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

mod=10**9+7
N,K=nm()
A=nl()
A2=[0 for i in range(N)]
Ah=[1 for i in range(N)]
for i in range(N):
    if(A[i]<0):
        Ah[i]=-1
    A2[i]=abs(A[i])

ans=1
A2.sort(reverse=True)
for i in range(K):
    ans*=(A2[i]*Ah[i])%mod

if(0<=ans):
    print(ans)
    sys.exit(0)

a_c=K-1
if(Ah[K-1]==-1):
    ans1=1
    for i in range(K-1):
        ans1*=(A2[i]*Ah[i])%mod
    while(a_c==1):
        a_c+=1
        if(Ah[a_c]==1):
            ans*=A[a_c]
        ans1=1
    a_c=K-1
    while(a_c==-1):
        a_c-=1
        if(Ah[a_c]==1):
            inds=a_c
    for i in range(K):
        if(i!=inds):
            ans2*=(A2[i]*Ah[i])%mod
    a_c=K-1
    while(a_c==1):
        a_c+=1
        if(Ah[a_c]==-1):
            ans2*=A[a_c]
    print(max(ans1,ans2))
    sys.exit(0)

a_c=K-1
if(Ah[K-1]==1):
    ans1=1
    for i in range(K-1):
        ans1*=(A2[i]*Ah[i])%mod
    while(a_c==1):
        a_c+=1
        if(Ah[a_c]==-1):
            ans*=A[a_c]
        ans1=1
    a_c=K-1
    ans2=1
    while(a_c==1):
        a_c-=1
        if(Ah[a_c]==-1):
            inds=a_c
    for i in range(K):
        if(i!=inds):
            ans2*=(A2[i]*Ah[i])%mod
    a_c=K-1
    while(1):
        a_c+=1
        if(Ah[a_c]==1):
            ans2*=A[a_c]
    print(max(ans1,ans2))
    sys.exit(0)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
S = []
p = N 
for i in range(N):
    if A[i] > 0:
        p = i
        break
D = A[:p]
B = []
for i in D:
    B.append(-i)
B.sort()
b = len(B)
C = A[p:]
for i in range(p):
    S.append(-A[i])
for i in range(p,N):
    S.append(A[i])
S.sort()
i = 0
while B:
    if S[i] == B[0]:
        S[i] = -S[i]
        B.pop(0)
    i += 1
def pow(a,b,mod):
    if b == 0:
        return 1
    else:
        if b % 2 == 0:
            return (pow(a,b//2,mod))**2%mod
        else:
            return (a*(pow(a,(b-1)//2,mod))**2)%mod
f = 0
p = 0
q = 0
mod = 10**9+7
ans = 1
if b == N:
    ans = 1
    for i in range(K):
        ans *= S[i]
        ans %= mod
    print(ans)
    quit()
for i in range(K):
    j = N - i - 1
    if S[j] < 0:
        q = S[j]
        f += 1
    else:
        p = S[j]
    ans *= S[j]
    ans = ans % mod
r = 0
s = 0
for i in range(K,N):
    j = N - i - 1
    if S[j] < 0:
        r = min(S[j],r)
    else:
        s = max(S[j],s)
if N == K:
    print(ans)
    quit()
if f % 2 == 0:
    print(ans)
    quit()
if r*q > s*q:
    ans *= r
    ans %= mod
    d = pow(p,mod-2,mod)
    ans *= d
    ans %= mod
else:
    ans *= s
    ans %= mod
    d = -pow(-q,mod-2,mod)
    ans *= d
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from collections import deque
from decimal import *
import queue

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,K = inputMap()
	A = inputList()

	A.sort()
	A = A[::-1]
	ans = 1
	for i in range(K):
		ans = (ans * A[i]) % mod

	print(ans)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
def resolve():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    pls = [i for i in A if i > 0]
    ms = [i for i in A if i <0]
    pls.sort(reverse=True)
    ms.sort(reverse=False)
    A.sort(key = lambda x : abs(x),reverse=True)
    if len(pls)+len(ms) < K:
        print(0)
        return
    if len(pls) == 0 and K %2 == 1:
        x=1
        for i in list(reversed(ms))[:K]:
            x*= abs(i)
            x%= 10**9+7

        print((-x)%10**9+7)
        return
    if len(pls)+len(ms) == K and K %2==1:
        print(0)
        return

    pc = 0
    mc = 0
    for i in range(K):
        if pc >= len(pls):
            mc+=1
        elif mc >= len(ms):
            pc+=1
        elif pls[pc] > abs(ms[mc]):
            pc +=1
        else:
            mc +=1

    if mc%2  !=0:
        aplan=0
        bplan=0
        if mc < len(ms)-1:
            aplan = abs(ms[mc] / pls[pc-1])
        if pc < len(pls)-1:
            bplan = abs(pls[pc]/ms[mc-1])
        
        if aplan>bplan:
            pc -=1
            mc +=1
        else:
            pc +=1
            mc -=1
    result=1
    for i in pls[:pc]:
        result*=i
        result%=10**9+7
    for i in ms[:mc]:
        result*=abs(i)
        result%=10**9+7
    print(result)



resolve()

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
    
if 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)