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



flg = 0
plus_num = 0
for i in a:
    if i>0:
        plus_num+=1
minus_num = n-plus_num


if minus_num ==1 and k==n:
    flg = 1
if minus_num >=2 and plus_num>=1 and n-plus_num%2==1 and k==n:
    flg = 1
if  minus_num >=2  and plus_num==0 and k%2==1:
    flg = 2



if flg == 1:
    ans = 1
    for i in a:
        ans*=i
        ans %= (10**9+1)
if flg ==2:
    abs_a = sorted(a, key=abs)
    ans = 1
    for i in range(k):
        ans*=abs_a[i]
        ans %= (10**9+7)
else:
    abs_a = sorted(a, key=abs)
    abs_a.reverse()
    min_minus = 0
    ans = 1
    for i in range(k):
        if abs_a[i]>=0:
            ans*=abs_a[i]
            ans %= (10**9+7)
        else:
            ans *= abs_a[i]
            ans %= (10**9+7)
            min_minus = abs_a[i]
    if ans <0:
        ans /=min_minus
        while True:
            for i in range(k,n):
                if abs_a[i]>=0:
                    ans*=abs_a[i]
                    ans %= (10**9+7)
                    break
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    def solve():
        ret = 1
        for i in range(n):
            if L[i][2]:
                ret *= L[i][0]
                ret %= MOD
        return ret % MOD

    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    MOD = 10 ** 9 + 7
    INF = float('inf')
    L = []
    p, m = 0, 0
    for a in A:
        if a < 0:
            m += 1
            L.append([abs(a), -1, False])
        else:
            L.append([a, 1, False])
    L = sorted(L, key= lambda x: x[0], reverse=True)
    pm = 1
    lp, lm = None, None
    for i in range(k):
        L[i][2] = True
        pm *= L[i][1]
        if L[i][1] >= 0:
            lp = i
        else:
            lm = i
    if pm >= 0:
        ans = solve()
    else:
        ans1, ans2 = -INF, -INF
        if lp:
            j = k
            while j < n:
                if L[j][1] < 0:
                    L[lp][2] = False
                    L[j][2] = True
                    ans1 = solve()
                    L[lp][2] = True
                    L[j][2] = False
                    break
                j += 1
        if lm:
            j = k
            while j < n:
                if L[j][1] >= 0:
                    L[lm][2] = False
                    L[j][2] = True
                    ans2 = solve()
                    L[lm][2] = True
                    L[j][2] = False
                    break
                j += 1
        ans = max(ans1, ans2)
        if ans1 == ans2 == -INF:
            L = sorted(L, key=lambda x: x[0])
            ans = 1
            for i in range(k):
                ans *= L[i][0]
                ans %= MOD
            ans = -1 * ans % MOD
    print(ans % MOD)
main()

Submission status: Wrong Answer

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

mainasu=[]
purasu=[]
zero=[]
for aa in a:
    if aa==0:
        zero.append(aa)
    elif aa>0:
        purasu.append(aa)
    else:
        mainasu.append(aa*(-1))

#ゼロを選ばないといけない絶対ゼロ
if len(purasu)+len(mainasu)<k:
    print(0)
    exit()
mod=10**9+7

#プラスがない
if len(purasu)==0:
    #奇数個選択しないといけない
    if k%2==1:
        if len(zero)>0:
            print(0)
            exit()
        else:
            mainasu.sort()
            cnt=0
            ans=1
            while cnt<k:
                ans=ans*mainasu[cnt]%mod
                cnt+=1
            ans=abs(ans-mod)
    #偶数個選択可能
    else:
        if len(mainasu)%2==0:
            mainasu.sort(reverse=True)
            cnt=0
            ans=1
            while cnt<k:
                ans=ans*mainasu[cnt]%mod
                cnt+=1
        else:
            print(0)
            exit()
    print(ans%mod)
    exit()


purasu.sort(reverse=True)
mainasu.sort(reverse=True)

p_pos=0
m_pos=0
cnt=0
ans=1
while cnt<k:
    #マイナスもプラスも選択可能
    #print(">>",cnt)
    if p_pos<len(purasu) and m_pos+1<len(mainasu):
        #print("1")
        #ラスト1個しか選べない
        if cnt==k-1:
            ans=ans*purasu[p_pos]
            ans=ans%mod
            cnt+=1
            p_pos+=1
        #複数個選べる
        else:
            #マイナスの方が大きい
            if purasu[p_pos]<=mainasu[m_pos+1]:
                tmp=(mainasu[m_pos]%mod)*(mainasu[m_pos+1]%mod)
                tmp=tmp%mod
                ans=ans*tmp
                ans=ans%mod
                m_pos+=2
                cnt+=2
            else:
                ans=ans*purasu[p_pos]
                ans=ans%mod
                cnt+=1
                p_pos+=1

    #プラスのみ選べる
    elif p_pos<len(purasu):
        #print("2>>",len(purasu),p_pos)
        ans=ans*purasu[p_pos]
        ans=ans%mod
        cnt+=1
        p_pos+=1

    #マイナスのみ2個選べる
    elif m_pos+1<len(mainasu) and cnt+1<k:
        #print("3")
        tmp=(mainasu[m_pos]%mod)*(mainasu[m_pos+1]%mod)
        tmp=tmp%mod
        ans=ans*tmp
        ans=ans%mod
        m_pos+=2
        cnt+=2
    #マイナスのみ1個選べる
    elif m_pos<len(mainasu):
        #print("4")
        #ゼロがある
        if len(zero)>0:
            print(0)
            exit()
        else:
            ans=ans*mainasu[m_pos]*(-1)
            #print("mainasu",ans)
            m_pos+=1
            cnt+=1
    #print(ans)

print(ans%mod)

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
        k-=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:
n,k = map(int,input().split())
a = list(map(int,input().split()))
sorted(a, key=lambda x: abs(x))
mod = 10**9 + 7
a.reverse()
ans = 1
kk = 0
for i in range(k):
    if a[i] < 0:
        kk += 1
if kk %2 == 0:
    for i in range(k):
        ans = ans*abs(a[i])%mod
    print(ans)
else:
    ans = 1
    plus = -1
    for i in range(n):
        if a[i] > 0:
            plus = 1
            break
    if plus == 1:
        for i in range(k-1):
            ans = ans*abs(a[i])%mod
        for j in range(i,n):
            if a[j] > 0:
                print(ans*a[j]%mod)
    else:
        for i in range(n):
            if a[i] == 0:
                plus = 0
                break
        if plus == 0:
            print(0)
        else:
            a.reverse()
            for i in range(k):
                ans = ans*a[i]%mod
            print(ans)

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,k=LI()
  l=LI()

  zero_contain=False
  if l.count(1):
    zero_contain=True

  al=[]
  for x in l:
    al.append((abs(x),x))

  al=sorted(al,key=lambda x:x[0],reverse=True)

  zero=False
  minus=0

  ansl=[]
  for ax,x in al[:k]:
    if x==0:
      zero=True
    if x<0:
      minus+=1
    ansl.append(x)

  ans=1
  for x in ansl:
    if x==0:
      ans=0
      break
    elif x>0:
      pass
    else:
      ans*=-1

  if ans>0:
    ans=1
    for x in ansl:
      ans*=x
      ans%=mod
    return ans
  elif ans<0:
    for x in ansl[::-1]:
      if x<0:
        t=x
        ansl2=copy.deepcopy(ansl)
        ansl2.remove(t)
        break
    ff=False
    for ax,x in al[k:]:
      if x>=0:
        ansl2.append(x)
        ff=True
        break
    if not ff:
      ansl2=[]
      for ax,x in al[::-1][:k]:
        ansl2.append(x)

    ans2=1
    for x in ansl2:
      ans2*=x
      ans2%=mod

    # print(ans,ans2)

    ans=1
    for x in ansl:
      ans*=x
      ans%=mod

    return max(ans,ans2)
  else:
    return 0

# main()
print(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()))
S = sorted(A, key=abs, reverse=True)
X = 1
pm = 0
for i in range(K - 1):
    if S[i] < 0:
        pm = 1 - pm
    X = X * abs(S[i]) % MOD
    X = X % MOD
for i in range(K - 1, N):
    if pm == 0:
        if S[i] > 0:
            Y = X * S[i] % MOD
            print(Y % MOD)
            sys.exit()
    else:
        if S[i] < 0:
            Y = X * abs(S[i]) % MOD
            print(Y % MOD)
            sys.exit()

if S[0] > 0:
    pm = 0
else:
    pm = 1
for i in range(K - 2, 0, -1):
    if pm == 0:
        if S[i] < 0:
            X = 1
            for j in range(K):
                if j == i:
                    continue
                X = X * abs(S[j]) % MOD
                X = X % MOD
            print(X % MOD)
            sys.exit()
    if pm == 1:
        if S[i] > 0:
            X = 1
            for j in range(K):
                if j == i:
                    continue
                X = X * abs(S[j]) % MOD
                X = X % MOD
            print(X % MOD)
            sys.exit()

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

Submission status: Wrong Answer

Solution code:
import heapq
from collections import deque
from functools import reduce

MOD = 10**9+7
n, k = map(int, input().split())
a = list(map(int, input().split()))
plus = [i for i in a if i > 0]
plus.sort(reverse=True)
minus = [i for i in a if i < 0]
minus.sort(reverse=True)
zero = [i for i in a if i == 0]

res = 1
if len(plus) + len(minus) < k:
    res = 0
    print(res % MOD)
    exit()
if len(plus) + len(minus) == k:
    if len(minus) % 2 == 0:
        res = reduce(lambda a, b: a * b, plus, 1) * reduce(lambda a, b: a * b, minus, 1)
        print(res % MOD)
        exit()
    else:
        res = 0
        print(res % MOD)
        exit()
elif len(minus) == 0:
    res = reduce(lambda a,b: a*b, plus[:k])
    print(res%MOD)
    exit()
elif len(plus) == 0:
    if k % 2 == 0:
        res = reduce(lambda a, b: a*b, minus[-k:])
        print(res%MOD)
        exit()
    else:
        if len(zero) > 0:
            res = 0
        else:
            res = reduce(lambda a,b: a*b, minus[:k])
        print(res%MOD)
        exit()
else:
    plus = deque([-i for i in plus])
    minus = deque(minus)
    c_p = deque([])
    c_m = deque([])
    last_p = False
    while len(c_p)+len(c_m) < k:
        if len(plus) > 0:
            can_p = plus.popleft()
        else:
            can_p = 10**9+1
        if len(minus) > 0:
            can_m = minus.popleft()
        else:
            can_m = 10**9+1
        if can_p < can_m:
            c_p.append(-can_p)
            minus.appendleft(can_m)
            last_p = True
        else:
            c_m.append(-can_m)
            plus.appendleft(can_p)
            last_p = False
    if len(c_m) % 2 == 0:
        res = reduce(lambda a, b: a * b, c_p, 1) * reduce(lambda a, b: a * b, c_m, 1)
        print(res % MOD)
        exit()
    if last_p:
        # 最大の負を入れる/一番小さい負を除いて最大の正を入れる
        if len(minus) > 0:
            c_p.pop()
            can_m = minus.popleft()
            c_m.append(-can_m)
        else:
            c_m.pop()
            can_p = plus.popleft()
            c_p.append(-can_p)
    else:
        # 最大の正を入れる/一番小さい正を除いて最大の負を入れる
        if len(plus) > 0:
            c_m.pop()
            can_p = plus.popleft()
            c_p.append(-can_p)
        else:
            c_p.pop()
            can_m = minus.popleft()
            c_m.append(-can_m)
    res = reduce(lambda a, b: a * b, c_p, 1) * reduce(lambda a, b: a * b, c_m, 1)
    print(res % MOD)

Submission status: Wrong Answer

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

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, K, XS):
    "void()"

    posi = [x for x in XS if x >= 0]
    nega = [x for x in XS if x < 0]

    nega.sort(reverse=True)
    posi.sort()

    if K == N:
        # no choice
        ret = 1
        for i in range(N):
            ret *= XS[i]
            ret %= MOD
        return ret

    if not posi and K % 2:
        # negative answer
        # find smallest abs
        ret = 1
        for i in range(K):
            ret *= nega[i]
            ret %= MOD
        return ret

    ret = 1
    while K:
        # debug(": K, nega, posi", K, nega, posi)
        if K >= 2:
            if len(posi) >= 2:
                v = posi[-1] * posi[-2]
                if len(nega) >= 2:
                    w = nega[-1] * nega[-2]
                else:
                    w = -INF
                if v > w:
                    posi.pop()
                    posi.pop()
                    ret *= v
                    ret %= MOD
                else:
                    nega.pop()
                    nega.pop()
                    ret *= w
                    ret %= MOD

            else:
                v = nega.pop()
                v *= nega.pop()
                ret *= v
                ret %= MOD

            K -= 2
        else:
            if posi:
                ret *= posi[-1]
            else:
                ret *= nega[0]
            K -= 1
    return ret


def main():
    N, K = map(int, input().split())
    XS = list(map(int, input().split()))
    print(solve(N, K, XS))


T1 = """
4 2
1 2 -3 -4
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    12
    """


T2 = """
4 3
-1 -2 -3 -4
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    1000000001
    """


T3 = """
2 1
-1 1000000000
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    1000000000
    """


T4 = """
10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    999983200
    """


def _test():
    import doctest
    doctest.testmod()


T5 = """
3 2
1 1 -1
"""


def test_T5():
    """
    >>> as_input(T5)
    >>> main()
    1
    """


T6 = """
3 2
1 -1 -1
"""


def test_T6():
    """
    >>> as_input(T6)
    >>> main()
    1
    """


T7 = """
3 2
2 -1 -1
"""


def test_T7():
    """
    >>> as_input(T7)
    >>> main()
    1
    """


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Wrong Answer

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

f = 0
b = -1
k = 0
if K == 1:
    print(max(sA)%(10**9+7))
    exit()

res = 1
m = max(sA)
while k < K:
    if m > 0 | (K % 2 == 0 & m != 0):
        if K - k >= 2:
            if A[f]*A[f+1] <= A[b]*A[b-1]:
                res *= A[b]*A[b-1]% (10**9 + 7)
                b = b - 2
                k += 2
            else:
                res *= A[f]% (10**9 + 7)
                f = f + 1
                k += 1
        else:
            res *= A[f]% (10**9 + 7)
            f = f + 1
            k += 1
    else:
        k = K
        for a in range(K):
            res *= sA[a]

print(res % (10**9 + 7))

Submission status: Wrong Answer

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

mod = 10**9 + 7

minus = []
plus = []
zero = []
new_ls = []
for i in ls:
    if i > 0:
        plus.append(i)
        new_ls.append(i)
    elif i < 0:
        minus.append(i)
        new_ls.append(-i)
    else:
        zero.append(i)
        new_ls.append(i)

ans = 1
new_ls.sort()
minus.sort()
plus.sort()
if (len(plus) == 0 and k%2 == 1) or (len(minus)%2 == 1 and k == n):
    if len(zero) != 0:
        ans = 0
    else:
        for i in range(k):
            ans *= new_ls[i]
            ans %= mod
        ans = mod - ans
elif k%2 == 0:
    m_ind = 0
    p_ind = 0
    for i in range(k//2):
        if m_ind+1 < len(minus) and p_ind+1 < len(plus):
            if minus[m_ind] * minus[m_ind+1] > plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]:
                ans *= minus[m_ind] * minus[m_ind+1]
                ans %= mod
                m_ind += 2
            else:
                ans *= plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]
                ans %= mod
                p_ind += 2
        elif m_ind+1 < len(minus):
            ans *= minus[m_ind] * minus[m_ind+1]
            ans %= mod
            m_ind += 2
        elif p_ind+1 < len(plus):
            ans *= plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]
            ans %= mod
            p_ind += 2
        #else:
else:
    m_ind = 0
    p_ind = 0
    for i in range(k//2):
        if m_ind+1 < len(minus) and p_ind+1 < len(plus):
            if minus[m_ind] * minus[m_ind+1] > plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]:
                ans *= minus[m_ind] * minus[m_ind+1]
                ans %= mod
                m_ind += 2
            else:
                ans *= plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]
                ans %= mod
                p_ind += 2
        elif m_ind+1 < len(minus):
            ans *= minus[m_ind] * minus[m_ind+1]
            ans %= mod
            m_ind += 2
        elif p_ind+1 < len(plus):
            ans *= plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]
            ans %= mod
            p_ind += 2
        #else:
    ans *= plus[len(plus)-p_ind-1]
    ans %= mod

print(ans)

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:
                if s1 < s2:
                    for a in ans2:
                        ans *= a
                elif s1 > s2:
                    for a in ans1:
                        ans *= a
                else:
                    s1_3 = sum(abs(a) <= 5 for a in ans1)
                    s2_3 = sum(abs(a) <= 5 for a in ans2)
                    if s1_3 < s2_3:
                        for a in ans2:
                            ans *= a
                    elif s1_3 > s2_3:
                        for a in ans1:
                            ans *= a
                    else:
                        for a in ans1:
                            ans *= a
    print(int(ans) % MOD)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# Required function 
n, k = map(int, input().split())
A = list(map(int, input().split()))
# print(len(A))
A.sort() 
product = 1
mod = 1000000007
if (A[n - 1] == 0 and (k & 1)): 
    print(0)
elif (A[n - 1] <= 0 and (k & 1)) : 
    for i in range(n - 1, n - k + 1, -1): 
        product *= A[i] 
    print(product % mod)
else:
    i = 0
    j = n - 1
    if (k & 1): 
        product *= A[j] 
        j-= 1
        k-=1
    k >>= 1
    for itr in range( k) : 
        left_product = A[i] * A[i + 1] 
        right_product = A[j] * A[j - 1] 
        if (left_product > right_product) : 
            product *= left_product 
            i += 2
            
        else : 
            product *= right_product 
            j -= 2
    # print(product)
    print(product % mod)

Submission status: Wrong Answer

Solution code:
import sys, math,os
from io import BytesIO, IOBase
#data = BytesIO(os.read(0,os.fstat(0).st_size)).readline
# from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
# from decimal import Decimal
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write(' '.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
#sys.setrecursionlimit(100000 + 1)
INF = 10**9
mod = 10**9 + 7


n,k=mdata()
a=mdata()
n1,p=-1,-1
a1=[(abs(a[i]),a[i]) for i in range(n)]
a1.sort(reverse=True)
ans=1
c=1
for i in range(k):
    if a1[i][1]>0:
        p=i
    elif a1[i][1]<0:
        n1=i
        c*=-1
    else:
        c=0
    ans=(ans*a1[i][1])%mod
if c>=0:
    out(ans%mod)
else:
    m=-INF
    b1=0
    b2=0
    for i in range(k,n):
        if a1[i][1]>=0 and b1==0:
            u1,v1=a1[n1][1],a1[i][1]
            b1=1
            c=1
        if a1[i][1]<0 and p!=-1 and b2==0:
            u2,v2=a1[p][1],a1[i][1]
            b2=1
            c=1
    if c<0:
        ans=1
        for i in range(k):
            ans = (ans*a1[n-i-1][1])%mod
    else:
        if b1==1 and b2==1:
            if v1/u1<v2/u2:
                ans=ans*pow(u1,mod-2,mod)*v1
            else:
                ans = ans * pow(u2, mod - 2, mod) * v2
        elif b1==1:
            ans = ans * pow(u1, mod - 2, mod) * v1
        else:
            ans = ans * pow(u2, mod - 2, mod) * v2
    out(ans%mod)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

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

if N == 2 and K == 1:
    M = max(A)
    print(M % mod)
    exit()

a = 0  # 0の個数
b = 0
c = 0
B = []
C = []
D = []
for i in range(N):
    if A[i] == 0:
        a += 1
    elif A[i] > 0:
        b += 1
        B.append(A[i])
        D.append(A[i])
    else:
        c += 1
        C.append(A[i])
        D.append(A[i])
if N-a < K:
    print(0)
    exit()

ans = 1

if c == N and K % 2 == 1:
    C = sorted(C,reverse=True)
    for i in range(K):
        ans *= C[i]
        ans %= mod
    print(ans)
    exit()
if K == N:
    for i in range(N):
        ans *= A[i]
        ans %= mod
    print(ans)
    exit()
if b == 0 and K % 2 == 1:
    print(0)
    exit()

d = b + c
E = [(abs(D[i]),D[i]) for i in range(d)]
E = sorted(E,reverse=True)

if K == 1:
    print(max(A) % mod)
    exit()
if K == 2:
    if N == 3:
        M = max([E[0][1]*E[1][1],E[0][1]*E[2][1],E[1][1]*E[2][1]])
        print(M % mod)
        exit()
    else:
        M = max([E[0][1] * E[1][1], E[0][1] * E[2][1], E[1][1] * E[2][1],E[0][1] * E[3][1],E[1][1] * E[3][1],E[2][1] * E[3][1]])
        print(M % mod)
        exit()



r = 0
if K >= 3:
    for i in range(K-2):
        if E[i][1] < 0:
            r += 1
        ans *= E[i][0]
        ans %= mod

if K == N-1:
    x = E[K-2][1]
    y = E[K-1][1]
    z = E[K][1]
    a1 = x
    a1 *= y
    a2 = x
    a2 *= z
    a3 = y
    a3 *= z
    if r % 2 == 0:
        M = max([a1,a2,a3])
    else:
        M = min([a1,a2,a3])
    print((ans*M) % mod)
    exit()

else:
    x = E[K-2][1]
    y = E[K-1][1]
    z = E[K][1]
    w = E[K+1][1]
    a1 = x
    a1 *= y
    a2 = x
    a2 *= z
    a3 = y
    a3 *= z
    a4 = x
    a4 *= w
    a5 = y
    a5 *= w
    a6 = z
    a6 *= w
    if r % 2 == 0:
        M = max([a1,a2,a3,a4,a5,a6])
    else:
        M = min([a1,a2,a3,a4,a5,a6])
    print((ans*M) % mod)
    exit()