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 = [int(hoge) for hoge in input().split()]
A = [int(hoge) for hoge in input().split()]
#必然、マイナスの数は偶数個がいい
Plus = []
Minus = []
Zero = 0
for a in A:
    if a > 0:
        Plus.append(a)
    elif a < 0:
        Minus.append(-a)
    else:
        Zero += 1
Plus.sort(reverse=True)
Minus.sort(reverse=True)
Nonzero = N - Zero
ans = 1
#ノンゼロ<K...必ずゼロ
#ノンゼロ == K ...マイナスが偶数→全部掛け
#                 マイナスが奇数→ゼロがあればゼロ、なければ全部掛け
#ノンゼロ > K:
#   Kが偶数→2つずつペアにしてデカい順にかける
#   Kが奇数→2つずつペアにするが、プラスのラスト1つを存在しないものとして扱う。
#   余ったらプラスの最小のやつをかける
if Nonzero < K:
    ans = 0
elif Nonzero == K:
    if K%2 and Zero:
        ans = 0
    else:
        ans = 1
        for a in A:
            ans *= a
            ans %= MOD
else:
    if K%2 == 0:
        Duet = []
        for n,p in enumerate(Plus):
            if n%2 == 0:
                cur = p
            else:
                Duet.append((cur*p , "Plus" ))
        for n,p in enumerate(Minus):
            if n%2 == 0:
                cur = p
            else:
                Duet.append((cur*p , "Minus" ))
        Duet.sort(reverse=True)
        ans = 1
        for i in range(K//2):
            ans *= Duet[i][0]
            ans %= MOD
    else:
        if len(Plus) > 0:
            Duet = []
            for n,p in enumerate(Plus):
                if n==len(Plus)-1:
                    break
                if n%2 == 0:
                    cur = p
                else:
                    Duet.append((cur*p , True ))
            for n,p in enumerate(Minus):
                if n%2 == 0:
                    cur = p
                else:
                    Duet.append((cur*p , False ))
            Duet.sort(reverse=True)
            ans = 1
            P = 0
            M = 0
            for i in range(K//2):
                ans *= Duet[i][0]
                ans %= MOD
                if Duet[i][1] == "Plus":
                    P += 1
                else:
                    M += 1
            ans *= Plus[2*P]
            ans %= MOD
        else:
            for i in range(K):
                ans *= A[i]
                ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
N,K = [int(hoge) for hoge in input().split()]
A = [int(hoge) for hoge in input().split()]
#必然、マイナスの数は偶数個がいい
Plus = []
Minus = []
Zero = 0
for a in A:
    if a > 0:
        Plus.append(a)
    elif a < 0:
        Minus.append(-a)
    else:
        Zero += 1
Plus.sort(reverse=True)
Minus.sort(reverse=True)
Nonzero = N - Zero
ans = 1
#ノンゼロ<K...必ずゼロ
#ノンゼロ == K ...マイナスが偶数→全部掛け
#                 マイナスが奇数→ゼロがあればゼロ、なければ全部掛け
#ノンゼロ > K:
#   Kが偶数→2つずつペアにしてデカい順にかける
#   Kが奇数→2つずつペアにするが、プラスのラスト1つを存在しないものとして扱う。
#   余ったらプラスの最小のやつをかける
if Nonzero < K:
    ans = 0
elif Nonzero == K:
    if K%2 and Zero:
        ans = 0
    else:
        ans = 1
        for a in A:
            ans *= a
            ans %= MOD
else:
    if K%2 == 0:
        Duet = []
        for n,p in enumerate(Plus):
            if n%2 == 0:
                cur = p
            else:
                Duet.append((cur*p , "Plus" ))
        for n,p in enumerate(Minus):
            if n%2 == 0:
                cur = p
            else:
                Duet.append((cur*p , "Minus" ))
        Duet.sort(reverse=True)
        ans = 1
        for i in range(K//2):
            ans *= Duet[i][0]
            ans %= MOD
    else:
        if len(Plus) > 0:
            Duet = []
            for n,p in enumerate(Plus):
                if n==len(Plus)-1:
                    break
                if n%2 == 0:
                    cur = p
                else:
                    Duet.append((cur*p , "Plus" ))
            for n,p in enumerate(Minus):
                if n%2 == 0:
                    cur = p
                else:
                    Duet.append((cur*p , "Minus" ))
            Duet.sort(reverse=True)
            ans = 1
            P = 0
            M = 0
            for i in range(K//2):
                ans *= Duet[i][0]
                ans % MOD
                if Duet[i][1] == "Plus":
                    P += 1
                else:
                    M += 1
            ans *= Plus[2*P]
            ans %= MOD
        else:
            for i in range(K):
                ans *= A[i]
                ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
N,K = [int(hoge) for hoge in input().split()]
A = [int(hoge) for hoge in input().split()]
#必然、マイナスの数は偶数個がいい
Plus = []
Minus = []
Zero = 0
for a in A:
    if a > 0:
        Plus.append(a)
    elif a < 0:
        Minus.append(-a)
    else:
        Zero += 1
Plus.sort(reverse=True)
Minus.sort(reverse=True)
Nonzero = N - Zero
ans = 1
#ノンゼロ<K...必ずゼロ
#ノンゼロ == K ...マイナスが偶数→全部掛け
#                 マイナスが奇数→ゼロがあればゼロ、なければ全部掛け
#ノンゼロ > K:
#   Kが偶数→2つずつペアにしてデカい順にかける
#   Kが奇数→2つずつペアにするが、プラスのラスト1つを存在しないものとして扱う。
#   余ったらプラスの最小のやつをかける
if Nonzero < K:
    ans = 0
elif Nonzero == K:
    if K%2 and Zero:
        ans = 0
    else:
        ans = 1
        for a in A:
            ans *= a
            ans %= MOD
else:
    if K%2 == 0:
        Duet = []
        for n,p in enumerate(Plus):
            if n%2 == 0:
                cur = p
            else:
                Duet.append(((cur*p)%MOD , "Plus" ))
        for n,p in enumerate(Minus):
            if n%2 == 0:
                cur = p
            else:
                Duet.append(((cur*p)%MOD , "Minus" ))
        Duet.sort(reverse=True)
        ans = 1
        for i in range(K//2):
            ans *= Duet[i][0]
            ans %= MOD
    else:
        if len(Plus) > 0:
            Duet = []
            for n,p in enumerate(Plus):
                if n==len(Plus)-1:
                    break
                if n%2 == 0:
                    cur = p
                else:
                    Duet.append(((cur*p)%MOD , "Plus" ))
            for n,p in enumerate(Minus):
                if n%2 == 0:
                    cur = p
                else:
                    Duet.append(((cur*p)%MOD , "Minus" ))
            Duet.sort(reverse=True)
            ans = 1
            P = 0
            M = 0
            for i in range(K//2):
                ans *= Duet[i][0]
                ans % MOD
                if Duet[i][1] == "Plus":
                    P += 1
                else:
                    M += 1
            ans *= Plus[2*P]
            ans %= MOD
        else:
            for i in range(K):
                ans *= A[i]
                ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n , k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9 + 7
ans = 1
plus = []
minus = []

if n == k:
    for i in range(n):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()
    
for i in range(n):
    if a[i] >= 0:
        plus.append(a[i])
    elif a[i] < 0:
        minus.append(a[i])

if not plus and k % 2 == 1:
    minus.sort(reverse=True)
    for i in range(k):
        ans *= minus[i]
        ans %= mod
    print(ans)
    exit()

plus.sort(reverse=True)
minus.sort()
plus = deque(plus)
minus = deque(minus)

cou = []
while True:
    if len(cou) == k:
        break
    elif len(cou) == k-1:
        cou.append(plus.popleft())
        break
    else:
        if len(plus)>=2 and len(minus)>=2:
            p1 = plus.popleft()
            p2 = plus.popleft()
            m1 = minus.popleft()
            m2 = minus.popleft()
            if p1*p2 > m1*m2:
                cou.append(p1)
                plus.appendleft(p2)
                minus.appendleft(m2)
                minus.appendleft(m1)
            else:
                cou.append(m1)
                cou.append(m2)
                plus.appendleft(p2)
                plus.appendleft(p1)
        elif len(plus) < 2:
            m1 = minus.popleft()
            m2 = minus.popleft()
            cou.append(m1)
            cou.append(m2)
        elif len(minus) < 2:
            p1 = plus.popleft()
            cou.append(p1)

Submission status: Wrong Answer

Solution code:
from collections import deque
n , k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9 + 7
ans = 1
plus = []
minus = []

if n == k:
    for i in range(n):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()
    
for i in range(n):
    if a[i] >= 0:
        plus.append(a[i])
    elif a[i] < 0:
        minus.append(a[i])

if not plus and k % 2 == 1:
    minus.sort(reverse=True)
    for i in range(k):
        ans *= minus[i]
        ans %= mod
    print(ans)
    exit()

plus.sort(reverse=True)
minus.sort()
plus = deque(plus)
minus = deque(minus)

cou = []
while True:
    if len(cou) == k:
        break
    elif len(cou) == k-1:
        cou.append(plus.popleft())
        break
    else:
        if len(plus)>=2 and len(minus)>=2:
            p1 = plus.popleft()
            p2 = plus.popleft()
            m1 = minus.popleft()
            m2 = minus.popleft()
            if p1*p2 > m1*m2:
                cou.append(p1)
                cou.append(p2)
                minus.appendleft(m2)
                minus.appendleft(m1)
            else:
                cou.append(m1)
                cou.append(m2)
                plus.appendleft(p2)
                plus.appendleft(p1)
        elif len(plus) < 2:
            m1 = minus.popleft()
            m2 = minus.popleft()
            cou.append(m1)
            cou.append(m2)
        elif len(minus) < 2:
            p1 = plus.popleft()
            p2 = plus.popleft()
            cou.append(p1)
            cou.append(p2)
        
for i in cou:
    ans *= i
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n , k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9 + 7
a.sort(reverse=True)
ans = 1
plus = []
minus = []

if n == k:
    for i in range(n):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()
    
for i in range(n):
    if a[i] >= 0:
        plus.append(a[i])
    elif a[i] < 0:
        minus.append(a[i])
if not plus and k % 2 == 1:
    minus.sort(reverse=True)
    for i in minus:
        ans *= i
        ans %= mod
    print(ans)
    exit()
plus.sort(reverse=True)
minus.sort()
plus = deque(plus)
minus = deque(minus)
cou = []
while True:
    if len(cou) == k:
        break
    elif len(cou) == k-1:
        cou.append(plus.popleft())
        break
    else:
        if len(plus)>=2 and len(minus)>=2:
            p1 = plus.popleft()
            p2 = plus.popleft()
            m1 = minus.popleft()
            m2 = minus.popleft()
            if p1*p2 > m1*m2:
                cou.append(p1)
                cou.append(p2)
                minus.appendleft(m2)
                minus.appendleft(m1)
            else:
                cou.append(m1)
                cou.append(m2)
                plus.appendleft(p2)
                plus.appendleft(p1)
        elif len(plus) < 2:
            m1 = minus.popleft()
            m2 = minus.popleft()
            cou.append(m1)
            cou.append(m2)
        elif len(minus) < 2:
            p1 = plus.popleft()
            p2 = plus.popleft()
            cou.append(p1)
            cou.append(p2)
        
for i in cou:
    ans *= i
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
    can_positive = False
    if len(p) > 0:
        if k<n:
            can_positive = True
        else:
            can_positive = len(m) % 2 == 0
    else:
        can_positive=k%2==0
    if not can_positive:
        m.sort(reverse=True)
        return m[:k]
    p.sort()
    m.sort(reverse=True)
    a = [p.pop()] if k % 2 else [1]
    while len(p) >= 2:
        a.append(p.pop()*p.pop())
    while len(m) >= 2:
        a.append(m.pop()*m.pop())
    return a[:1] + sorted(a[1:], reverse=True)[:(k-k%2)//2]

mod = 10**9+7
n, k = list(map(int, input().split()))
m, p = [], []
for i in map(int, input().split()):
    if i < 0:
        m.append(i)
    else:
        p.append(i)
ans = 1
for i in solve():
    ans = ans * i % mod
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import numpy
import random

def calp():
    limit = 10 #int(1e9)
    '''
    n = 10   #int(2e5)
    k = 6    #int(1e5+9e4)
    x = []
    for i in range(n):
        x.append(random.randint(-limit,limit))
    '''
    n,k = map(int,input().split())
    x = list(map(int,input().split()))
    #print(x)

    if n == k:
        p = 1
        for i in x:
            p *= i
        return p
    x.append(0)
    x.sort()
    m = x.index(0)
    x1 =x[0:m]
    x2 =x[m+1:]
    #print(x1,x2)
    if len(x1)==n:
        if k%2 == 0:
            p = numpy.prod(x1[:k])
            return p
        else:
            #print(x1[-k:])
            p = numpy.prod(x1[-k:])
            return p

    p = 1
    if k%2 ==1:
        p *= x2[-1]
        x2.pop(-1)
        k -= 1

    x1b,x2b = [],[]
    for i in range(0,2*int(len(x1)/2),2):
        x1b.append(x1[i]*x1[i+1])
    for i in reversed(range(0,2*int(len(x2)/2),2,)):
        x2b.append(x2[i]*x2[i+1])
    #print(x1b,x2b)
    t1l = len(x1b)
    t2l = len(x2b)
    t1,t2 = 0,0
    while k > 0:
        if t1l > t1 and t2l > t2:
            if x1b[t1] >= x2b[t2]:
                p *= x1b[t1]
                t1 += 1
            else:
                p *= x2b[t2]
                t2 += 1
            k -= 2
        elif t1l > t1:
            p *= x1b[t1]
            t1 += 1
            k -= 2
        elif t2l > t2:
            p *= x2b[t2]
            t1 += 1
            k -= 2
        #else:
            #print("what is the situation?")
            #print(t1,t2,t1l,t1b,x1b,x2b)
            #break
    return p                

a =calp()                    
#print(a)            
print(a % (int(1e9)+7))

Submission status: Wrong Answer

Solution code:
def solve():
    can_positive = False
    if len(p) > 0:
        if k<n:
            can_positive = True
        else:
            can_positive = len(m) % 2 == 0
    else:
        can_positive=k%2==0
    if not can_positive:
        return sorted(p+m)[:k]
    p.sort()
    m.sort(reverse=True)
    a = [p.pop()] if k % 2 else [1]
    while len(p) >= 2:
        a.append(p.pop()*p.pop())
    while len(m) >= 2:
        a.append(m.pop()*m.pop())
    return a[:1] + sorted(a[1:], reverse=True)[:(k-k%2)//2]

mod = 10**9 + 7
n, k = list(map(int, input().split()))
m, p = [], []
for i in map(int, input().split()):
    if i < 0:
        m.append(i)
    else:
        p.append(i)
ans = 1
for i in solve():
    ans = ans * i % mod
print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
    can_positive = False
    if len(p) > 0:
        can_positive=True
    else:
        can_positive=k%2==0
    if not can_positive:
        return sorted(m)[:k]
    p.sort()
    m.sort(reverse=True)
    a = [p.pop()] if k % 2 else [1]
    while len(p) >= 2:
        a.append(p.pop()*p.pop())
    while len(m) >= 2:
        a.append(m.pop()*m.pop())
    return a[:1] + sorted(a[1:], reverse=True)[:(k-k%2)//2]

mod = 10**9 + 7
n, k = list(map(int, input().split()))
m, p = [], []
for i in map(int, input().split()):
    if i < 0:
        m.append(i)
    else:
        p.append(i)
ans = 1
for i in solve():
    ans = ans * i % mod
print(ans)

Submission status: Wrong Answer

Solution code:
    #n,k,*a=map(int,open(0).read().split())
n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
print(a)
mod=10**9+7
ans=1
i=0
j=-1
kk=k
while kk>1:
    if a[i]*a[i+1]>a[j]*a[j-1]:
        ans=ans*a[i]*a[i+1]%mod
        i+=2
        kk-=2
    else:
        ans=ans*a[j]%mod
        j-=1
        kk-=1
if kk==1:
    ans=ans*a[j]%mod

if a[-1]<0 and k%2==1:
    ans=1
    for i in a[n-k:]:
        ans=ans*i%mod
print(ans)

Submission status: Wrong Answer

Solution code:
def checkio(numbers_array):
    return sorted(numbers_array, key=lambda x: abs(x))

MOD = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))

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

a = checkio(a)
a = a[::-1]



ans = 1
neg = 1
pos = -1

for i in range(k):
    ans *= a[i]
    ans %= MOD
    if a[i] > 0:
        pos = a[i]
    else:
        neg = a[i]

if ans >= 0:
    print(ans)

else:
    ans1 = ans / pos
    ans2 = ans / neg
    for i in range(k, n):
        if a[i] >= 0:
            ans1 *= a[i]
            ans1 %= MOD
            break
    for i in range(k, n):
        if a[i] < 0:
            ans2 *= a[i]
            ans2 %= MOD
            break

    print(max(ans1, ans2))

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
# mod の逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

# 正,負 で分ける
b=[]
c=[]
for i in a:
    if i>=0:
        b.append(i)
    else:
        c.append(i)

b.sort(reverse=True)
c.sort()
ans=1
if k==n:
    for i in range(n):
        ans*=a[i]
        ans%=mod

elif k%2==1 and len(c)==n:
    c.sort(reverse=True)
    for i in range(k):
        ans*=c[i]
        ans%=mod

else:
    x=k
    # プラスの配列をどこまで進めたか
    v=0
    # マイナスの配列をどこまで進めたか？
    w=0
    for i in range(k):
        if x>=2:
            x-=2
            if v+2<=len(b) and w+2<=len(c):
                if b[v]*b[v+1]>c[w]*c[w+1]:
                    ans*=b[v]*b[v+1]
                    v+=2
                else:
                    ans*=c[w]*c[w+1]
                    w+=2


            elif v+2<=len(b):
                ans*=b[v]*b[v+1]
                v+=2

            else:
                ans*=c[w]*c[w+1]
                w+=2

            ans%=mod
            if x==0:
                break
        else:
            ans*=b[v]
            ans%=mod
            break
print(ans%mod)

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
# mod の逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

# 正,負 で分ける
b=[]
c=[]
for i in a:
    if i>=0:
        b.append(i)
    else:
        c.append(i)

b.sort(reverse=True)
c.sort()
ans=1
if k==n:
    for i in range(n):
        ans*=a[i]
        ans%=mod

elif k%2==1 and len(c)==n:
    c.sort(reverse=True)
    for i in range(k):
        ans*=c[i]
        ans%=mod

else:
    x=k
    # プラスの配列をどこまで進めたか
    v=0
    # マイナスの配列をどこまで進めたか？
    w=0
    for i in range(k):
        if x>=2:
            x-=2
            if v+2<=len(b) and w+2<=len(c):
                if b[v]*b[v+1]>c[w]*c[w+1]:
                    ans*=b[v]*b[v+1]
                    v+=2
                else:
                    ans*=c[w]*c[w+1]
                    w+=2


            elif v+2<=len(b):
                ans*=b[v]*b[v+1]
                v+=2

            else:
                ans*=c[w]*c[w+1]
                w+=2
                
            ans%=mod
            if x==0:
                break
        else:
            ans*=b[v]
            ans%=mod
            break
print(ans)

Submission status: Wrong Answer

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

mod=10**9+7
# mod の逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

if k%2==0:
    ans = 1
    for i in range(n):
        a[i]=abs(a[i])
    a.sort(reverse=True)
    for i in range(k):
        ans*=a[i]
        ans%=mod
    print(ans)
else:
    # 正,負,0で分ける
    b=[]
    c=[]
    d=[]
    for i in a:
        if i>0:
            b.append(i)
        elif i<0:
            c.append(i)
        else:
            d.append(i)
    b.sort(reverse=True)
    c.sort()

    if len(b)>0 and k-((len(b)//2)*2+len(b)%2)<=len(c):
        # 累積積
        b1=[1]
        c1=[1]
        x=1
        y=1
        for i in range(len(b)):
            x*=b[i]
            modinv(x,mod)
            b1.append(x)
        for i in range(len(c)):
            y*=abs(c[i])
            modinv(y,mod)
            c1.append(y)
        ans=0
        for i in range(len(b)):
            if i%2==0 and k-i<=len(c):
                cnt=b1[i+1]*c1[k-i-1]
                ans=max(cnt,ans)
        print(ans%mod)

    elif len(b)+len(c)<k:
        print(0)
    else:
        ans=1
        c.sort(reverse=True)
        for i in range(k):
            ans*=c[i]
            ans%=mod
        print(ans%mod)

Submission status: Wrong Answer

Solution code:
import copy
from sys import exit
n, k = map(int, input().split())
A = list(map(int, input().split()))

mod = 10**9 + 7

plus = []
minus = []
for a in A:
    if a >= 0:
        plus.append(a)
    else:
        minus.append(a)
plus.sort()
minus.sort(reverse=True)

def is_ans_plus():
    if len(plus) > 0:
        if n == k:
            if len(minus) % 2 == 0:
                return True
            else:
                return  False
        else:
            return True
    else:
        if k % 2 == 0:
            return True
        else:
            return False

ans = 1
if is_ans_plus():
    if k % 2 == 1:
        ans *= plus.pop()
        k -= 1
    for i in range(k // 2):
        plus_pair, minus_pair = -1, -1
        if len(plus) >= 2:
            plus_pair = plus[-1] * plus[-2]
        if len(minus) >= 2:
            minus_pair = minus[-1] * minus[-2]
        if plus_pair >= minus_pair:
            ans *= plus_pair
            plus.pop()
            plus.pop()
        else:
            ans *= minus_pair
            minus.pop()
            minus.pop()
        ans %= mod
    ans = 1
else:
    ans = -1
    A = sorted([abs(a) for a in A])
    for i in range(k):
        ans *= A[i]
        ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
from collections import defaultdict, deque
from decimal import *
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))
mod=1000000007

'''E Multiplication 4'''
n,k=rm()
a=rl()
pos=[]
negInit=[]
for i in a:
    if i>=0:
        pos.append(i)
    elif i<0:
        negInit.append(i)

pos.sort(reverse=True)
negInit.sort()
negLen=len(negInit)
if negLen!=0:
    negIncr=[negInit[0]]
    negDecr=[negInit[-1]]

for i in range(1,len(pos)):
    pos[i]=(pos[i-1]*pos[i])
if negLen!=0:
    for j in range(1,negLen):
        negIncr.append(negIncr[-1]*negInit[j])
        negDecr.append(negDecr[-1]*negInit[negLen-j-1])

if len(pos)==0:
    if k%2==0:
        print(negIncr[k-1]%mod)
    else:
        print(negDecr[k-1]%mod)
elif negLen==0:
    print(pos[k-1]%mod)
elif k==len(a):
    ans=1
    for i in a:
        ans*=i
    print(ans)
else:
    maxi=-math.inf
    for i in range(0,k+1,2):
        if i==0:
            if k-i<=len(pos):
                maxi=max(maxi,pos[k-i-1])
        elif k-i==0:
            if i<=negLen:
                maxi=max(maxi,negIncr[i-1])
        elif i<=negLen and k-i<=len(pos):
            maxi=max(maxi,negIncr[i-1]*pos[k-i-1])
    print(maxi)

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
from collections import defaultdict, deque
from decimal import *
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))
mod=1000000007

'''E Multiplication 4'''
n,k=rm()
a=rl()
pos=[]
negInit=[]
for i in a:
    if i>=0:
        pos.append(i)
    elif i<0:
        negInit.append(i)

pos.sort(reverse=True)
negInit.sort()
negLen=len(negInit)
if negLen!=0:
    negIncr=[negInit[0]]
    negDecr=[negInit[-1]]

for i in range(1,len(pos)):
    pos[i]=(pos[i-1]*pos[i])
if negLen!=0:
    for j in range(1,negLen):
        negIncr.append(negIncr[-1]*negInit[j])
        negDecr.append(negDecr[-1]*negInit[negLen-j-1])

if len(pos)==0:
    if k%2==0:
        print(negIncr[k-1]%mod)
    else:
        print(negDecr[k-1]%mod)
elif negLen==0:
    print(pos[k-1]%mod)
else:
    maxi=-math.inf
    for i in range(0,k+1,2):
        if i==0:
            if k-i<=len(pos):
                maxi=max(maxi,pos[k-i-1])
        elif k-i==0:
            if i<=negLen:
                maxi=max(maxi,negIncr[i-1])
        elif i<=negLen and k-i<=len(pos):
            maxi=max(maxi,negIncr[i-1]*pos[k-i-1])
    print(maxi)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A_ascend = sorted(A)
A_descend = sorted(A, reverse=True)
A_ascend_minus = 0
A_descend_minus = 0
mul_ascend = A_ascend[0]
mul_descend = A_descend[0]
for i in range(K):
  if str(A_ascend[i]) == "-":
    A_ascend_minus += 1
  if str(A_descend[i]) == "-":
    A_descend_minus += 1
if A_ascend_minus % 2 == 1:
  mul_ascend = 0
if A_descend_minus % 2 == 1:
  mul_descend = 0

for i in range(1, K):
  mul_ascend = mul_ascend * A_ascend[i] % (10**9+7)
  mul_descend = mul_descend * A_descend[i] % (10**9+7)

print(max(mul_ascend, mul_descend))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A_ascend = sorted(A)
A_descend = sorted(A, reverse=True)
mul_ascend = A_ascend[0]
mul_descend = A_descend[0]

for i in range(1, K):
  mul_ascend *= A_ascend[i]
  mul_descend *= A_descend[i]
  muls = [mul_ascend, mul_descend]
  for mul in muls:
    if mul < 0:
      mul = -1 * (abs(mul) % (10**9+7))
    else:
      mul = mul % (10**9+7)

max_mul = max(mul_ascend, mul_descend)
print(max_mul % (10**9+7))

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
from collections import defaultdict, deque
from decimal import *
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))
mod=1000000007

'''E Multiplication 4'''
n,k=rm()
a=rl()
pos=[]
neg=[]
for i in a:
    if i>=0:
        pos.append(i)
    elif i<0:
        neg.append(i)

pos.sort(reverse=True)
neg.sort()
negg=neg[::-1]

for i in range(1,len(pos)):
    pos[i]=(pos[i-1]*pos[i])
for j in range(1,len(neg)):
    neg[j]=(neg[j-1]*neg[j])
    negg[j]=(negg[j-1]*negg[j])

if len(pos)==0:
    if k%2==0:
        print(neg[k-1]%mod)
    else:
        print(negg[k-1]%mod)
elif len(neg)==0:
    print(pos[k-1]%mod)
else:
    maxi=-math.inf
    for i in range(0,k+1,2):
        if i==0:
            if k-i<=len(pos):
                maxi=max(maxi,pos[k-i-1])
        elif k-i==0:
            if i<=len(neg):
                maxi=max(maxi,neg[i-1])
        elif i<=len(neg) and k-i<=len(pos):
            maxi=max(maxi,neg[i-1]*pos[k-i-1])
    print(maxi)

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
from collections import defaultdict, deque
from decimal import *
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))
mod=1000000007

'''E Multiplication 4'''
n,k=rm()
a=rl()
pos=[]
neg=[]
for i in a:
    if i>=0:
        pos.append(i)
    elif i<0:
        neg.append(i)

pos.sort(reverse=True)
neg.sort()
negg=neg[::-1]

for i in range(1,len(pos)):
    pos[i]=(pos[i-1]*pos[i])
for j in range(1,len(neg)):
    neg[j]=(neg[j-1]*neg[j])
    negg[j]=(negg[j-1]*negg[j])

if len(pos)==0:
    if k%2==0:
        print(neg[k-1]%mod)
    else:
        print(negg[k-1]%mod)
elif len(neg)==0:
    print(pos[k-1]%mod)
else:
    maxi=-math.inf
    for i in range(0,k+1,2):
        if i==0:
            if k-i<=len(pos):
                maxi=max(maxi,pos[k-i-1])
        elif k-i==0:
            if i<=len(neg):
                maxi=max(maxi,neg[i-1])
        elif i<=len(neg) and k-i<=len(pos):
            maxi=max(maxi,neg[i-1]*pos[k-i-1])
    print(maxi)

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
from collections import defaultdict, deque
from decimal import *
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))
mod=1000000007

'''E Multiplication 4'''
n,k=rm()
a=rl()
pos=[]
neg=[]
for i in a:
    if i>=0:
        pos.append(i)
    elif i<0:
        neg.append(i)

pos.sort(reverse=True)
negg=neg[:]
negg.sort(reverse=True)
neg.sort()

for i in range(1,len(pos)):
    pos[i]=(pos[i-1]*pos[i])
for j in range(1,len(neg)):
    neg[j]=(neg[j-1]*neg[j])
    negg[j]=(negg[j-1]*negg[j])

if len(pos)==0:
    if k%2==0:
        print(neg[k-1]%mod)
    else:
        print(negg[k-1]%mod)
elif len(neg)==0:
    print(pos[k-1]%mod)
else:
    maxi=-math.inf
    for i in range(0,k+1,2):
        if i==0:
            if k-i<=len(pos):
                maxi=max(maxi,pos[k-i-1])
        elif k-i==0:
            if i<=len(neg):
                maxi=max(maxi,neg[i-1])
        elif i<=len(neg) and k-i<=len(pos):
            maxi=max(maxi,neg[i-1]*pos[k-i-1])
    print(maxi)

Submission status: Wrong Answer

Solution code:
import heapq
mod = 10**9+7

N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a > 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
M.sort()
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0

if len(P)==0 and K%2 == 1:
    for i in range(K):
        ans2 = ans2 * M[i] % mod 

else:
    while i < K-1:
        if(len(P)>=2 and len(M)>=2):
            if(P[0]*P[1]<M[0]*M[1]):
                i +=2
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
            else:
                i +=1
                ans2 = -ans2*heapq.heappop(P)%mod
        elif len(P)==1:
            if len(M)>=2 and -P[0] < M[0]*M[1]:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 2
            else:
                ans2 = -ans2*heapq.heappop(P)%mod
                i += 1
        elif len(P)==0:
            if len(M)>=2:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 2
        elif len(M)<=1:
            ans2 = -ans2*heapq.heappop(P)%mod
            i += 1
    while i < K:
        i += 1
        if len(P)>=1:
            ans2 = -ans2*heapq.heappop(P)%mod
        else:
            ans2 = ans2*heapq.heappop(M)%mod

print(ans2)