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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

MOD = 10**9+7


def main(input, print):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    plus = []
    neg = []
    for i in range(n):
        if a[i] < 0:
            neg.append(a[i])
        else:
            plus.append(a[i])
    is_ans_plus = False
    if len(plus) > 0:
        if n == k:
            is_ans_plus = len(neg) % 2 == 0
        else:
            is_ans_plus = True
    else:
        is_ans_plus = k % 2 == 0
    ans = 1
    if is_ans_plus:
        neg = sorted(neg, key=abs, reverse=True)
        plus = sorted(plus, key=abs, reverse=True)
        pair = []
        for i in range(1, len(neg), 2):
            pair.append(neg[i-1]*neg[i])
        s = 1
        if k % 2 == 1:
            ans = plus[0]
            s = 2
        for i in range(s, len(plus), 2):
            pair.append(plus[i-1]*plus[i])
        pair = sorted(pair, reverse=True)
        for i in range(k//2):
            ans = ans * pair[i] % MOD
    else:
        a = sorted(a, key=abs)
        for i in range(k):
            ans = ans * a[i] % MOD

    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Solution (Python):
n, k = (int(x) for x in input().split())
A = list(int(x) for x in input().split())
MOD = 10**9 + 7
A.sort()

l = 0
r = n - 1
sign = 1  
ans = 1
if k % 2 == 1:
    ans = A[r]
    r -= 1
    k -= 1
    if ans < 0:
        sign = -1

while k:
    x = A[l] * A[l + 1]
    y = A[r] * A[r - 1]
    if x * sign > y * sign:
        ans *= x % MOD
        ans %= MOD
        l += 2
    else:
        ans *= y % MOD
        ans %= MOD
        r -= 2
    k -= 2

print(ans)

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

if max(a) < 0:
    a.sort()
    ans = 1
    if k % 2 == 0:
        for e in a[:k]:
            ans *= e
            ans %= mod
    else:
        for e in a[-k:]:
            ans *= e
            ans %= mod

    print(ans)

elif k == n:
    ans = 1
    for e in a:
        ans *= e
        ans %= mod

    print(ans)

else:
    neg = []
    pos = []
    for e in a:
        if e < 0:
            neg.append(e)
        else:
            pos.append(e)

    neg.sort()
    pos.sort(reverse=True)

    ans = 1
    if k % 2:
        ans *= pos.pop(0)
        k -= 1

    nums = [e1 * e2 for e1, e2 in zip(neg[::2], neg[1::2])]
    nums += [e1 * e2 for e1, e2 in zip(pos[::2], pos[1::2])]

    nums.sort(reverse=True)
    for e in nums[:k//2]:
        ans *= e
        ans %= mod

    print(ans)

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



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

S = []
T = []
for a in A:
    if a < 0:
        T.append(a)
    else:
        S.append(a)

ls = len(S)
lt = len(T)
ok = False

if ls > 0:
    if N == K:
        ok = lt % 2 == 0
    else:
        ok = True
else:
    ok = K % 2 == 0

ans = 1
if not ok:
    A = sorted(A, key=lambda x: abs(x))
    for a in A[:K]:
        ans *= a
        ans %= MOD
else:
    S = sorted(S)
    T = sorted(T, reverse=True)
    if K % 2 == 1: 
        ans *= S.pop()
        ans %= MOD
    p = []
    
    
    while len(S) >= 2:
        x = S.pop()  
        y = S.pop()
        p.append(x * y)
    while len(T) >= 2:
        x = T.pop()  
        y = T.pop()
        p.append(x * y)
    p = sorted(p, reverse=True)
    for i in range(K // 2):
        ans *= p[i]
        ans %= MOD
print(ans % MOD)

Solution (Python):
n,k = map(int,input().split())
A = list(map(int,input().split()))

mod = 10**9 + 7

A.sort(key = lambda x:abs(x),reverse = True)
ans = 1
last = -1
lastp = -1
cnt = 0
for a in A:
    if a >= 0:break
else:
    if k&1:
        for i in range(k):
            ans *= A[n-i-1]
            ans %= mod
    else:
        for i in range(k):
            ans *= A[i]
            ans %= mod
    print(ans)
    exit()
for i in range(k):
    ans *= A[i]
    ans %= mod
    if A[i] < 0:
        last = i
        cnt += 1
    if A[i] > 0:
        lastp = i
if n == k:
    print(ans%mod)
    exit()
if cnt&1:
    first = 0
    firstp = 0
    for a in A[k:]:
        if a > 0 and firstp == 0:
            firstp = a
        if a < 0 and first == 0:
            first = a
    if first == 0 and firstp == 0:
        ans = 0
    elif first == 0 or lastp == -1:
        ans *= pow(A[last],mod-2,mod)*firstp%mod
        ans %= mod
    elif firstp == 0:
        ans *= pow(A[lastp],mod-2,mod)*first%mod
        ans %= mod
    else:
        if A[lastp]*firstp <= A[last]*first:
            ans *= pow(A[lastp],mod-2,mod)*first%mod
            ans %= mod
        else:
            ans *= pow(A[last],mod-2,mod)*firstp%mod
            ans %= mod
print(ans%mod)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    pos = []
    neg = []
    for a in aa:
        if a < 0: neg.append(a)
        else: pos.append(a)
    pn = len(pos)
    nn = len(neg)
    if min(k,nn) // 2 * 2 + pn < k:
        aa.sort(key=lambda x: abs(x))
        print(cal(aa[:k]))
    else:
        pos.sort()
        neg.sort(reverse=True)
        ans = pos.pop() if k & 1 else 1
        mul = []
        while len(pos) > 1: mul.append(pos.pop() * pos.pop())
        while len(neg) > 1: mul.append(neg.pop() * neg.pop())
        mul.sort(reverse=True)
        print(ans * cal(mul[:k // 2]) % md)

def cal(xx):
    res=1
    for x in xx:
        res=res*x%md
    return res

md=10**9+7
n,k=MI()
aa=LI()
main()

Solution (Python):
from heapq import *
from collections import deque

N,K,*A = map(int, open(0).read().split())
pos = []
zero = 0
neg = []
count = K
m = 1000000007
for x in A:
    if x > 0:
        pos.append(x)
    elif x == 0:
        zero += 1
    else:
        neg.append(x)
if K == N:
    ans = A[0] % m
    for x in A[1:]:
        ans = (ans*x) % m
    print(ans)
elif K % 2 == 1 and len(pos) == 0:
    if zero > 0:
        print(0)
    else:
        ai = [x * (-1) for x in A]
        heapify(ai)
        ans = (heappop(ai)*(-1)) % m
        for i in range(K-1):
            ans = (ans*heappop(ai)*(-1)) % m
        print(ans)
elif K > N - zero:
    print(0)
else:
    heapify(neg)
    ans = 1
    negpos = []
    for i in range(len(neg)//2):
        temp = heappop(neg)
        negpos.append(temp*heappop(neg))
    dnp = deque(negpos)
    posi = [x * (-1) for x in pos]
    heapify(posi)
    if len(posi) > 0:
        t1 = heappop(posi) * (-1)
    else:
        t1 = 1
    if len(posi) > 0:
        t2 = heappop(posi) * (-1)
    else:
        t2 = 1
    for i in range(K):
        if count > 1:
            if len(dnp) > 0:
                if t1 > dnp[0]:
                    if count > 2:
                        ans = (ans*t1) % m
                        t1 = t2
                        if len(posi) > 0:
                            t2 = heappop(posi) * (-1)
                        else:
                            t2 = 1
                        count -= 1
                    else:
                        if t2 == 1 and len(posi) == 0:
                            ans = (ans*dnp.popleft()) % m
                            count -= 2
                        else:
                            ans = (ans*t1) % m
                            t1 = t2
                            if len(posi) > 0:
                                t2 = heappop(posi) * (-1)
                            else:
                                t2 = 1
                            count -= 1
                else:
                    if t1 * t2 > dnp[0]:
                        if count != 3:
                            ans = (ans*t1*t2) % m
                            if len(posi) > 0:
                                t1 = heappop(posi) * (-1)
                            else:
                                t1 = 1
                            if len(posi) > 0:
                                t2 = heappop(posi) * (-1)
                            else:
                                t2 = 1
                            count -= 2
                        else:
                            if len(posi) > 0:
                                t3 = heappop(posi) * (-1)
                                M = max(t1*t2*t3,dnp[0]*t1)
                                ans = (ans*M) % m
                                break
                            else:
                                ans = (ans*dnp.popleft()*t1) % m
                                break
                    else:
                        ans = (ans*dnp.popleft()) % m
                        count -= 2
            else:
                ans = (ans*t1) % m
                if len(posi) > 0:
                    t1 = t2
                    t2 = heappop(posi) * (-1)
                else:
                    t1 = t2
                count -= 1
        elif count == 1:
            ans = (ans*t1) % m
            break
        else:
            break
    print(ans)

Solution (Python):

def resolve():
    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:
            M.append(a)
        else:
            P.append(a)
    p_n = len(P)
    m_n = len(M)
    
    ok = False
    if p_n > 0:
        if N == K:
            ok = (m_n%2==0) 
        else:
            ok = True
    
    else:
        ok = (K % 2 == 0) 

    ans = 1
    
    if not ok:
        
        A.sort(key=lambda x:abs(x))
        for i in range(K):
            ans *= A[i]
            ans %= MOD
    else:
        P.sort()
        M.sort(reverse=True)
        if K%2== 1:
            ans *= P.pop()
            ans %= MOD
        pair = []
        
        while len(P) >= 2:
            x = P.pop()
            x *= P.pop()
            pair.append(x)
        while len(M) >= 2:
            x = M.pop()
            x *= M.pop()
            pair.append(x)
        pair.sort(reverse=True)
        for i in range(K//2):
            ans *= pair[i]
            ans %= MOD
    ans %= MOD
    print(ans)

if __name__ == "__main__":
    resolve()

Solution (Python):
N, K, *A = map(int, open(0).read().split())

MOD = 10 ** 9 + 7
s = []  
t = []  
for i in range(N):
    if A[i] < 0:
        t.append(A[i])
    else:
        s.append(A[i])
        
ok = False  
if len(s) > 0:
    if N == K:
        ok = len(t) % 2 == 0
    else:
        ok = True
else:
    ok = K % 2 == 0

ans = 1
if not ok:
    x = sorted(A, key=lambda x: abs(x))
    for i in range(K):
        ans = ans * x[i] % MOD
else:
    s.sort()
    t.sort(key=lambda x: abs(x))
    if K % 2 == 1:
        ans = ans * s.pop() % MOD
        
    p = []
    while len(s) >= 2:
        x = s.pop() * s.pop()
        p.append(x)
    
    while len(t) >= 2:
        x = t.pop() * t.pop()
        p.append(x)

    p.sort(reverse=True)
    for i in range(K // 2):
        ans = ans * p[i] % MOD
    
print(ans)

Solution (Python):

import sys
MOD = 10**9 + 7
def main(N, K, A):
    neg = pos = zer = 0
    for a in A:
        if a < 0: neg += 1
        elif a > 0: pos += 1
        else: zer += 1
    

    if N - K < zer:
        
        return 0
    N -= zer
    A = sorted([a for a in A if a != 0], key=lambda x: abs(x))

    if (pos == 0 and K & 1) or (neg & 1 and N == K):
        
        if zer:
            
            return 0
        else:
            ans = Mint(1)
            for i in range(K):
                ans *= abs(A[i])
            return -ans

    
    A.reverse()
    positives = []
    negatives = []
    
    for i in range(K):
        if A[i] > 0: positives.append(A[i])
        else: negatives.append(A[i])

    if len(negatives) & 1:
        
        
        nn = [negatives.pop()]
        pp = []
        rem = 1
        if positives:
            
            pp.append(positives.pop())
            rem = 2

        
        for i in range(K, N):
            if A[i] < 0: nn.append(A[i])
            else: pp.append(A[i])
        
        

        if rem == 2:
            
            if len(nn) >= 2 and len(pp) < 2:
                
                negatives.append(nn[0])
                negatives.append(nn[1])
            elif len(pp) >= 2 and len(nn) < 2:
                
                positives.append(pp[0])
                positives.append(pp[1])
            elif len(pp) >= 2 and len(nn) >= 2:
                
                if pp[0] * pp[1] > nn[0] * nn[1]:
                    positives.append(pp[0])
                    positives.append(pp[1])
                else:
                    negatives.append(nn[0])
                    negatives.append(nn[1])
            else:
                
                assert False
        else:
            
            positives.append(pp[0])

    
    ans = Mint(1)
    for p in positives:
        ans *= p
    for n in negatives:
        ans *= abs(n)
    return ans

class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % MOD
        return self

    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other)) % MOD
        if self.value < 0: self.value += MOD
        return self

    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj

    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self

    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self

    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj

    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    input = sys.stdin.readline
    N, K = map(int, input().split())
    *A, = map(int, input().split())
    print(main(N, K, A))

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
from copy import deepcopy
mod = 10**9 + 7

n, k = map(int, input().split())
a = [int(x) for x in input().split()]
a = sorted(a, key=lambda x: abs(x))[::-1]
a_plus = [int(x) for x in a if x > 0]
a_minus = [int(x) for x in a if x < 0]
a_abs = [abs(x) for x in a]

def calc(x):
    res = 1
    for i in x:
        res*=abs(i)
        res %= mod 
    return res

max_a = a[:k]
max_a_minus = []
max_a_plus = []
minus_cnt = 0

for i in max_a:
    if i == 0:
        print(0)
        sys.exit()
    if i < 0:
        minus_cnt += 1
        max_a_minus.append(i)
    else:
        max_a_plus.append(i)

if minus_cnt % 2 == 0:
    print(calc(max_a))
    sys.exit()

plus_cnt = k - minus_cnt

if len(a_minus) <= minus_cnt and len(a_plus) <= plus_cnt:
    ans = -float('inf')
elif len(a_minus) <= minus_cnt:
    if len(max_a_minus) == 0:
        ans = -float("inf")
    else:
        max_a_minus.pop()
        max_a_plus.append(a_plus[plus_cnt])
        ans = calc(max_a_plus + max_a_minus)
elif len(a_plus) <= plus_cnt:
    if len(max_a_plus) == 0:
        ans = -float("inf")
    else:
        max_a_plus.pop()
        max_a_minus.append(a_minus[minus_cnt])
        ans = calc(max_a_minus + max_a_plus)
else:
    flag1 = 1
    flag2 = 1
    if len(max_a_minus) == 0:
        ans1 = -float("inf")
        flag1 = 0
    if len(max_a_plus) == 0:
        ans2 = -float("inf")
        flag2 = 0
    if flag1:
        c1 = deepcopy(max_a_minus)
        c2 = deepcopy(max_a_plus)
        d1 = abs(c1.pop()); d2 = abs(a_plus[plus_cnt])
        c2.append(a_plus[plus_cnt])
        ans1 = calc(c1 + c2)
    if flag2:
        c3 = deepcopy(max_a_minus)
        c4 = deepcopy(max_a_plus)
        d3 = abs(c4.pop()); d4 = abs(a_minus[minus_cnt])
        c3.append(a_minus[minus_cnt])
        ans2 = calc(c3 + c4)
    if flag1 and flag2:
        ans = ans1 if d2*d3 > d1*d4 else ans2
    else:
        ans = max(ans1, ans2)

a_abs = a_abs[::-1]
ans2 = -calc(a_abs[:k])
if ans != -float("inf"):
    print(ans%mod)
else:
    print(ans2%mod)

Solution (Python):
n,k,*a=map(int,open(0).read().split())
a.sort()
p=a.pop
s=b=~k%2or p()
i=0
for _ in k//2*'_':
 x=a[i]*a[i+1]
 if x*b>a[-1]*a[-2]*b:s*=x;i+=2
 else:s*=p()*p()
 s%=10**9+7
print(s)

Solution (Python):
n,k,*a=map(int,open(i:=0).read().split())
a.sort()
s=b=~k%2or a.pop()
j=1
for _ in k//2*'_':
 if(x:=a[i]*a[i+1])*b>(y:=a[-j]*a[~j])*b:s*=x;i+=2
 else:s*=y;j+=2
 s%=10**9+7
print(s)

Solution (Python):
n,k,*a=map(int,open(i:=0).read().split())
a.sort()
p=a.pop
s=b=~k%2or p()
j=1
for _ in k//2*'_':
 if(x:=a[i]*a[i+1])*b>(y:=a[-j]*a[~j])*b:s*=x;i+=2
 else:s*=y;j+=2
 s%=10**9+7
print(s)

Solution (Python):
n,k,*a=map(int,open(i:=0).read().split())
a.sort()
p=a.pop
s=b=~k%2or p()
for _ in k//2*'_':
 if(x:=a[i]*a[i+1])*b>a[-1]*a[-2]*b:s*=x;i+=2
 else:s*=p()*p()
 s%=10**9+7
print(s)

Solution (Python):
n,k,*a=map(int,open(i:=0).read().split())
a.sort()
p=a.pop
s=b=~k%2or p()
for _ in k//2*'_':
 x=a[i]*a[i+1]
 if x*b>a[-1]*a[-2]*b:s*=x;i+=2
 else:s*=p()*p()
 s%=10**9+7
print(s)

Solution (Python):
import sys
from collections import deque

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


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

    pos = [a for a in A if a >= 0]
    neg = [a for a in A if a < 0]

    pos.sort()
    neg.sort(reverse=True)

    if N == K:
        vec = A
    elif N == len(neg):
        if K & 1:
            vec = neg[:K]
        else:
            vec = neg[-K:]
    else:
        vec = []
        if K & 1:
            vec.append(pos.pop())

        tmp = []
        while len(neg) >= 2:
            tmp.append(neg.pop() * neg.pop())
        while len(pos) >= 2:
            tmp.append(pos.pop() * pos.pop())

        tmp.sort(reverse=True)
        vec.extend(tmp[: K // 2])

    ans = 1
    for a in vec:
        ans = ans * a % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
M=10**9+7
n,k,*a=map(int,open(y:=0).read().split())
a.sort()
s=1
a=a[-k*(a[-1]<0<k%2):]
while k-y>1:
 if(t:=a[y]*a[y+1])>a[-1]*a[-2]:s=s*t%M;y+=2
 else:s=s*a.pop()%M;k-=1
if k-y:s*=a[-1]
print(s%M)

Solution (Python):
import sys
from collections import deque

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


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

    pos = [a for a in A if a >= 0]
    neg = [a for a in A if a < 0]

    pos.sort()
    neg.sort(reverse=True)

    if N == K:
        vec = A
    elif N == len(neg):
        if K & 1:
            vec = neg[:K]
        else:
            vec = neg[-K:]
    else:
        ans_pos = []
        ans_neg = []
        for _ in range(K):
            if not pos:
                ans_neg.append(neg.pop())
            elif not neg:
                ans_pos.append(pos.pop())
            elif pos[-1] > -neg[-1]:
                ans_pos.append(pos.pop())
            else:
                ans_neg.append(neg.pop())

        if (len(ans_neg) & 1) and ((not ans_pos) or (ans_pos[-1] != 0)):
            if not pos or not ans_neg:
                drop_pos = True
            elif not neg or not ans_pos:
                drop_pos = False
            else:
                drop_pos = pos[-1] * ans_pos[-1] < neg[-1] * ans_neg[-1]

            if drop_pos:
                ans_neg.append(neg.pop())
                ans_pos.pop()
            else:
                ans_pos.append(pos.pop())
                ans_neg.pop()

        vec = ans_pos + ans_neg

    ans = 1
    for a in vec:
        ans = ans * a % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
M=10**9+7
n,k,*a=map(int,open(y:=0).read().split())
a.sort()
x=s=1
a=a[-k*(a[-1]<0<k%2):]
while x+y<k:
 if(t:=a[y]*a[y+1])>a[-x]*a[~x]:s=s*t%M;y+=2
 else:s=s*a[-x]%M;x+=1
print(s*(x+y-k or a[-x])%M)

Solution (Python):
M=10**9+7
n,k,*a=map(int,open(y:=0).read().split())
a.sort()
x=s=1
while x+y<k:
 if(t:=a[y]*a[y+1])>a[-x]*a[~x]:s=s*t%M;y+=2
 else:s=s*a[-x]%M;x+=1
s*=x+y-k or a[-x]
if a[-1]<0<k%2:
 s=1
 for i in a[-k:]:s=s*i%M
print(s%M)

Solution (Python):
import sys
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
MOD=10**9+7
plus=[]
minus=[]
zero=[]
for i in range(n):
  if a[i]>0:
    plus.append(a[i])
  if a[i]<0:
    minus.append(a[i])
  if a[i]==0:
    zero.append(a[i])
if k==n:
  ans=1
  for i in range(k):
    ans=(ans*a[i])%MOD
  print(ans)
  sys.exit()
if len(plus)==0:
  if k%2!=0:
    a.reverse()
  ans=1
  for i in range(k):
    ans=(ans*a[i])%MOD
  print(ans)
  sys.exit()
if len(plus)+len(minus)<k:
  print(0)
  sys.exit()
m=len(minus)
minus.sort()
plus.reverse()
plpointer=k
if k>len(plus):
  plpointer=2*(len(plus)//2)
  if k%2==1:
    if plpointer+1<=len(plus):
      plpointer+=1
    else:
      plpointer-=1
mnpointer=k-plpointer
while mnpointer<m-1 and plpointer>=2 and minus[mnpointer]*minus[mnpointer+1]>plus[plpointer-1]*plus[plpointer-2]:
  mnpointer+=2
  plpointer-=2
ans=1
for i in range(mnpointer):
  ans=(ans*minus[i])%MOD
for i in range(plpointer):
  ans=(ans*plus[i])%MOD
print(ans)

Solution (Python):
M=10**9+7
n,k,*a=map(int,open(y:=0).read().split())
a.sort()
x=s=1
r=k
while r>1:
 if(t:=a[y]*a[y+1])>a[-x]*a[~x]:s=s*t%M;y+=2;r-=2
 else:s=s*a[-x]%M;x+=1;r-=1
if r:s*=a[-x]
if a[-1]<0<k%2:
 s=1
 for i in a[-k:]:s=s*i%M
print(s%M)

Solution (Python):
def main():
    M=10**9+7
    n,k,*a=map(int,open(0).read().split())
    x,y=[],[]
    for i in a:
        if i>0:x+=i,
        if i<0:y+=i,
    if len(x)+len(y)<k or k%2 and not x and len(y)<n:
        print(0)
        return
    if n==k or k%2 and not x:
        c=1
        for i in sorted(x+y)[-k:]:
            c=c*i%M
        print(c)
        return
    x=sorted(x)[::-1][:k]
    i=len(x)
    y.sort()
    m=len(y)
    j=k-i
    if j%2:
        x=x[:-1]
        i-=1
        j+=1
    x+=y[:j]
    while i>1 and j+1<m and x[i-1]*x[i-2]<y[j]*y[j+1]:
        x[i-1],x[i-2]=y[j],y[j+1]
        i-=2
        j+=2
    c=1
    for i in x:
        c=c*i%M
    print(c)
main()

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

Solution (Python):
import sys
input = sys.stdin.readline
mod  = int(1e9+7)

n,k = map(int,input().split())
L = list(map(int,input().split()))
ans = 1 
if k==n:
    for i in L:
        ans*=i
        ans%=mod
    print(ans%mod)
    sys.exit()

pos = []
neg = []
for i in L:
    if i>=0:
        pos.append(i)
    else:
        neg.append(i)

pos.sort(reverse=True)
neg.sort()

if len(pos) == 0 and k%2!=0:
    for i in range(1,k+1):
        ans *= neg[-i]
        ans %= mod
    print(ans%mod)
    sys.exit()

if k%2!=0:
    ans*=pos.pop(0)
    k-=1

l=[]
for i in range(1,len(pos),2):
    l.append(pos[i]*pos[i-1])
    
for i in range(1,len(neg),2):
    l.append(neg[i]*neg[i-1])

l.sort(reverse = True)
for i in range(k//2):
    ans *= l[i]
    ans %= mod
print(ans%mod)

Solution (Python):
import copy

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

mod = 10**9 + 7

Am, Ap = [], []
pm = [0, 0]
B = []

def ans(A):
  ans = 1
  for x in A:
    ans *= x
    ans %= mod
  return ans

if N == K:
  print(ans(A))
  exit()

for x in A:
  if x < 0:
    Am.append(-x)
    B.append((-x, 1))
    pm[0] += 1
  else:
    Ap.append(x)
    B.append((x, 0))
    pm[1] += 1

Am.sort()

if pm[0] == N:
  if K%2 == 0:
    print(ans(Am[N-K:]))
  else:
    print((-1 * ans(Am[:K]))%mod)
  exit()

P = []
B.sort(reverse = True)

cnt = 0

p_min = (-1, -1)
m_min = (-1, -1)

for i in range(K):
  P.append(B[i][0])
  cnt ^= B[i][1]
  if B[i][1] == 0:
    p_min = (B[i][0], i)
  else:
    m_min = (B[i][0], i)

if cnt == 0:
  print(ans(P))
  exit()

P1 = copy.deepcopy(P)
P2 = copy.deepcopy(P)

p_max = (-1, -1)
m_max = (-1, -1)

for i in range(K, N):
  if B[i][1] == 0:
    p_max = (B[i][0], i)
    break

for i in range(K, N):
  if B[i][1] == 1:
    m_max = (B[i][0], i)
    break

Flag1 = False
Flag2 = False

if p_min[1] != -1 and m_max[1] != -1:
  Flag1 = True
  P1[p_min[1]] = 1
  P1.append(m_max[0])
  ans1 = ans(P1)

if m_min[1] != -1 and p_max[1] != -1:
  Flag2 = True
  P2[m_min[1]] = 1
  P2.append(p_max[0])
  ans2 = ans(P2)

if Flag1 and Flag2:
  if m_min[0]*m_max[0] > p_min[0]*p_max[0]:
    print(ans1)
  else:
    print(ans2)
elif Flag1:
  print(ans1)
else:
  print(ans2)

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,k,*a = map(int,read().split())

pos = []
neg = []
MOD = 10**9+7

for i in a:
    if i >= 0: pos.append(i)
    else: neg.append(i)

if n==k:
    ans = 1
    for i in a:
        ans *= i
        ans %= MOD
    print(ans)

elif pos == []: 
    if k%2==0:
        neg.sort()
        ans = 1
        for i in range(k):
            ans *= neg[i]
            ans %= MOD
        print(ans)
    else:
        neg.sort(reverse=True)
        ans = 1
        for i in range(k):
            ans *= neg[i]
            ans %= MOD
        print(ans%MOD)
            
else: 
    pos.sort()
    neg.sort(reverse=True)
    if k&1:
        ans = pos.pop()%MOD
    else:
        ans = 1
    
    res = []
    while len(pos)>1:
        x,y=pos.pop(),pos.pop()
        res.append(x*y)
    while len(neg)>1:
        x,y=neg.pop(),neg.pop()
        res.append(x*y)

    res.sort(reverse=True)
    for i in range(k//2):
        ans *= res[i]
        ans %= MOD
    print(ans)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
a,b,i=0,1,0
mod=10**9+7
ans=1
while i<K-1:
  if A[a]*A[a+1]>A[-b]*A[-b-1]:
    ans*=A[a]*A[a+1]
    ans%=mod
    a+=2
    i+=2
  else:
    ans*=A[-b]
    ans%=mod
    b+=1
    i+=1
if i==K-1:
  ans*=A[-b]
  ans%=mod
if A[-1]<0 and K%2==1:
  ans=1
  for i in A[N-K:]:
    ans*=i
    ans%=mod
print(ans%mod)