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: Accepted

Solution code:
from heapq import heapify,heappush,heappop
N, K = map(int,input().split())
A = list(map(int, input().split()))
MOD =1_000_000_007

B = [a for a in A if a > 0]
C = [a for a in A if a<= 0]
B.sort()
C.sort(reverse = True)
ans = 1
if N == K:
  for a in A:
    ans *= a
    ans %= MOD
elif len(B) == 0 and K % 2 == 1:
  for i in range(K):
    ans *= C[i]
    ans %= MOD
else:
  if K % 2 == 1:
    ans *= B[-1]
    B.pop()
    K -= 1
  i = 0 
  j = 0
  k = 0
  while k < K:
    #print(B,C)
    flag = 0 #Bから二つとる時に0,Cから二つとる時に1,それ以外2
    if len(B) >= 2 and len(C) >= 2 and B[-1]*B[-2] < C[-1]*C[-2]:
      flag = 1
    elif len(B) <= 1 and len(C) >= 2:
      flag = 1
    elif len(B) == 1 and len(C) == 1:
      flag = 2
      
    if flag == 0:  
      ans *= B[-1]*B[-2]
      ans %= MOD
      B.pop()
      B.pop()
    
    elif flag == 1:
      ans *= C[-1]*C[-2]
      ans %= MOD
      C.pop()
      C.pop()
      
    elif flag == 2:
      ans *= C[-1]*B[-1]
      ans %= MOD
      B.pop()
      C.pop()
    
    k += 2

print(ans)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n, k = inpl()
a = inpl()
data = [[abs(i), i < 0] for i in a]
data.sort(reverse=True)
last_minus = 0
last_plus = 0
ans = 1
minus_amount = 0
for i in range(k):
    elem, sign = data[i][0], data[i][1]
    if elem == 0:
        print(0)
        exit()
    ans = ans * elem % mod
    minus_amount += sign
    if sign:
        last_minus = elem
    else:
        last_plus = elem
if minus_amount % 2 == 0:
    print(ans % mod)
    exit()
if n==k:
    print(-ans % mod)
    exit()
all_minus = 0
for t in data:
    if t[1]:
        all_minus += 1
if all_minus == n:
    ans = 1
    data.sort()
    for i in range(k):
        ans = ans * data[i][0] % mod
    ans = ans * ((-1) % mod)
    print(ans % mod)
    exit()
tmp_plus = 0
tmp_minus = 0
for i in range(k, n):
    elem, sign = data[i][0], data[i][1]
    if last_plus and sign and not tmp_minus:
        tmp_minus = elem
    elif last_minus and not sign and not tmp_plus:
        tmp_plus = elem
if tmp_plus == 0 and tmp_minus == 0:
    ans = 0
elif last_plus == 0:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
elif last_minus == 0:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
elif tmp_plus * last_plus > tmp_minus * last_minus:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
else:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
print(ans)

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
MOD=10**9+7
from collections import deque
#======================================================#
def main():
    n, k = MII()
    aa = MII()
    pos = [a for a in aa if a >= 0]
    neg = [a for a in aa if a <= 0]
    len_pos = len(pos)
    len_neg = len(neg)
    if n == k:
        res = 1
        for a in aa:
            res *= a
            res %= MOD
        print(res)
    elif len_pos == 0:
        if k%2==1:
            neg.sort(reverse=True)
        else:
            neg.sort()
        res = 1
        for i in range(k):
            res *= neg[i]
            res %= MOD
        print(res)
    else:
        pos.sort(reverse=True)
        neg.sort()
        ans = 1
        if k%2 == 1:
            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)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

mod = 10**9+7
n,k = na()
a = na()
a.sort()

ans = 1

if k == 1:
    print(a[-1])
    exit()

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

s = 0
e = -1

while k > 0:
    if k == 1:
        if a[s] >= a[e]:
            ans = ans*a[s]%mod
        else:
            ans = ans*a[e]%mod
        break
    p = a[s]*a[s+1]
    q = a[e]*a[e-1]
    if p >= q:
        ans = p%mod*ans%mod
        s+=2
    else:
        ans = q%mod*ans%mod
        e-=2
    k-=2

print(ans%mod)

Submission status: Accepted

Solution code:
from queue import PriorityQueue
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


mod = 10**9+7


def prod(l):
    ret = 1
    for e in l:
        e %= mod
        ret = (ret*e) % mod

    return ret


def main():
    n, k = geta(int)
    a = list(geta(int))

    p, n, z = [], [], 0
    for ai in a:
        if ai > 0:
            p.append(ai)
        elif ai < 0:
            n.append(-ai)
        else:
            z += 1

    ans = 1
    p.sort()
    n.sort()


    if len(p) + len(n) < k:
        print(0)
        exit()
    elif len(p) + len(n) == k:
        if len(n) & 1 == 0:
            print(prod(p) * prod(n) % mod)
            exit()
        else:
            if z > 0:
                print(0)
                exit()
            else:
                print(-prod(p)*prod(n) % mod)
                exit()

    if k & 1 == 1:
        if len(p) == 0:
            if z > 0:
                print(0)
                exit()
            else:
                print(-prod(n[0:k]) % mod)
                exit()
        else:
            k -= 1
            ans = p.pop() % mod

    q = []

    n = n[::-1]
    for i in range(len(n)//2):
        q.append(n[2*i]*n[2*i+1])

    p = p[::-1]
    for i in range(len(p)//2):
        q.append(p[2*i]*p[2*i+1])

    q.sort(reverse=True)

    ans = ans * (prod(q[:k//2])) % mod

    print(ans % mod)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!python3

import numpy as np

LI = lambda: list(map(int, input().split()))

# input
N, K = LI()
A = np.array(LI())

MOD = 10 ** 9 + 7


def main():
    if np.count_nonzero(A == 0) > N - K:
        print(0)
        return
    m = A[A < 0] * -1
    p = A[A > 0]
    m = np.sort(m)[::-1]
    p = np.sort(p)[::-1]
    mn = len(m)
    pn = len(p)
    i, j = 0, 0
    for _ in range(K):
        if i >= mn:
            j += 1
            continue
        if j >= pn:
            i += 1
            continue
        if m[i] < p[j]:
            j += 1
        else:
            i += 1
    if i % 2 == 1:
        if i < mn and j > 0:
            if j < pn:
                x = m[i - 1] * m[i]
                y = p[j - 1] * p[j]
                if x < y:
                    i -= 1
                    j += 1
                else:
                    i += 1
                    j -= 1
            else:
                i += 1
                j -= 1
        elif j < pn - 1:
            i -= 1
            j += 1
    if i % 2 == 0:
        ans = 1
        for x in m[:i]:
            ans = ans * x % MOD
        for x in p[:j]:
            ans = ans * x % MOD
    else:
        if 0 in A:
            ans = 0
        else:
            ans = -1
            for x in m[mn - i:]:
                ans = ans * x % MOD
            for x in p[pn - j:]:
                ans = ans * x % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MOD = 10**9+7

n, k = [int(_) for _ in input().split()]

a = [int(_) for _ in input().split()]

m = list(filter(lambda x: x < 0, a))
p = list(filter(lambda x: x > 0, a))

m.sort()
p.sort(reverse=True)


if len(p)+len(m) < k:
    print(0)
    exit()
if len(p)+len(m) == k:
    ans = 1
    for p_ in p:
        ans = (ans*p_) % MOD
    for q_ in m:
        ans = (ans*q_) % MOD
    print(ans)
    exit()

if len(p) == 0 and k % 2 == 1:
    ans = 1
    for i in range(k):
        ans = (ans*m[-i-1]) % MOD
    if 0 in a:
        ans *= 0
    print(ans)
    exit()

i, j = 0, 0
if k % 2 == 1:
    d = p.pop(-1)
m.append(0)
m.append(0)
p.append(0)
p.append(0)
# print(p, m)
ans = 1
for c in range(k//2):
    # print(i, j)
    if m[i]*m[i+1] >= p[j]*p[j+1]:
        ans = (ans*m[i]*m[i+1]) % MOD
        i += 2
    else:
        ans = (ans*p[j]*p[j+1]) % MOD
        j += 2

if k % 2 == 1:
    ans = (ans*max(p[j], d)) % MOD


if ans > MOD:
    ans -= MOD
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun May  3 16:22:00 2020

@author: neb0123
"""

def maxProductSubarrayOfSizeK(A, n, k): 
    A.sort() 
    product = 1
  
    if (A[n - 1] == 0 and (k & 1)): 
        return 0
  
    if (A[n - 1] <= 0 and (k & 1)) : 
        for i in range(n - 1, n - k - 1, -1): 
            product *= A[i] 
            product %= (10**9 + 7)
        return product 

    i = 0
    j = n - 1

    if (k & 1): 
        product *= A[j] 
        product %= (10**9 + 7)
        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 
            product %= (10**9 + 7)
            i += 2
          
        else : 
            product *= right_product
            product %= (10**9 + 7) 
            j -= 2

    return product

if __name__ == "__main__":
    N,K = map(int, input().split(' '))
    A = list(map(int,input().split(' ')))
    print(maxProductSubarrayOfSizeK(A,N,K))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    if N == K:
        ans = 1
        for a in A:
            ans *= a
            ans %= MOD
        print(ans)
        return

    B = []
    n_plus = 0
    for a in A:
        if a >= 0:
            B.append((a, True))
            n_plus += 1
        else:
            B.append((-a, False))

    if n_plus == 0:
        if K % 2 == 0:
            A.sort()
        else:
            A.sort(reverse=True)
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= MOD
        print(ans)
        return

    B.sort(key=lambda x: x[0], reverse=True)
    cnt = 0
    prev_minus = None
    prev_plus = None
    for i in range(K):
        b, flag = B[i]

        if flag:
            prev_plus = b
        else:
            cnt += 1
            prev_minus = b

    if prev_plus == 0:
        print(0)
        return

    if cnt % 2 == 0:
        ans = 1
        for i in range(K):
            b, flag = B[i]
            ans *= b
            ans %= MOD
        print(ans)
        return

    next_minus = None
    next_plus = None
    for i in range(K, N):
        b, flag = B[i]
        if flag:
            if next_plus is None:
                next_plus = b
        else:
            if next_minus is None:
                next_minus = b

        if b == 0:
            if next_minus is None:
                next_minus = 0

    if next_plus is not None and prev_minus is not None:
        ans1 = 1
        ignored = False
        for i in range(K):
            b, flag = B[i]

            if ignored or prev_minus != b:
                ans1 *= b
                ans1 %= MOD
                continue

            if prev_minus == b:
                ignored = True

        ans1 *= next_plus
        ans1 %= MOD
    else:
        ans1 = -INF

    if next_minus is not None and prev_plus is not None:
        ans2 = 1
        ignored = False
        for i in range(K):
            b, flag = B[i]

            if ignored or prev_plus != b:
                ans2 *= b
                ans2 %= MOD
                continue

            if prev_plus == b:
                ignored = True

        ans2 *= next_minus
        ans2 %= MOD
    else:
        ans2 = -INF

    if ans1 == -INF:
        print(ans2)
    elif ans2 == -INF:
        print(ans1)
    else:
        if prev_minus * next_minus > prev_plus * next_plus:
            print(ans2)
        else:
            print(ans1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n, k = inpl()
a = inpl()
data = [[abs(i), i < 0] for i in a]
all_minus = 0
for t in data:
    if t[1]:
        all_minus += 1
if all_minus == n and k%2!=0:
    ans = 1
    data.sort()
    for i in range(k):
        ans = ans * data[i][0] % mod
    ans=ans*((-1)%mod)
    print(ans % mod)
    exit()
data.sort(reverse=True)
last_minus = 0
last_plus = 0
ans = 1
minus_amount = 0
for i in range(k):
    elem, sign = data[i][0], data[i][1]
    if elem == 0:
        print(0)
        exit()
    ans = ans * elem % mod
    minus_amount += sign
    if sign:
        last_minus = elem
    else:
        last_plus = elem
if minus_amount % 2 == 0:
    print(ans%mod)
    exit()
if n==k:
    print(-ans % mod)
    exit()
tmp_plus = 0
tmp_minus = 0
for i in range(k, n):
    elem, sign = data[i][0], data[i][1]
    if last_plus and sign and not tmp_minus:
        tmp_minus = elem
    elif last_minus and not sign and not tmp_plus:
        tmp_plus = elem
if tmp_plus == 0 and tmp_minus == 0:
    ans = 0
elif last_plus == 0:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
elif last_minus == 0:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
elif tmp_plus * last_plus > tmp_minus * last_minus:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
else:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
print(ans)

Submission status: Accepted

Solution code:
M = 1000000007
n, k = map(int, input().split())
l = list(map(int, input().split()))
k1 = k
pos = []
neg = []
zero = []
for i in l:
    if i > 0: pos.append(i)
    if i < 0: neg.append(i)
    if i == 0: zero.append(i)
pos.sort(reverse = True)
neg.sort()


if k == 1:
    if len(pos) > 0: print(pos[0] % M)
    elif len(zero) > 0: print(0)
    else: print(neg[0] % M)
    exit(0)

check = 0
if k % 2 == 1:
    check = 1
    k -= 3

p1, p2 = 0, 0
n1, n2 = len(pos), len(neg)

ans = 1
ch1, ch2 = 1, 1
while 1:
    if k == 0: break
    
    if p1 + 1 >= n1: ch1 = 0 
    if p2 + 1 >= n2: ch2 = 0
    
    if ch1 and ch2:
        k -= 2
        t1 = pos[p1] * pos[p1 + 1]
        t2 = neg[p2] * neg[p2 + 1]
        if t1 >= t2:
            p1 += 2
            ans = (ans * t1) % M
        else:
            p2 += 2
            ans = (ans * t2) % M
    elif ch1:
        k -= 2
        t1 = pos[p1] * pos[p1 + 1]
        ans = (ans * t1) % M
        p1 += 2
    elif ch2:
        k -= 2
        t2 = neg[p2] * neg[p2 + 1]
        ans = (ans * t2) % M
        p2 += 2
    else: break

if k != 0:
    if len(zero) > 0: ans = 0
    else:
        ans = (ans * pos[p1]) % M
        ans = (ans * neg[p2]) % M
else:
    ch1, ch2 = 1, 1
    if check:
        if p1 + 2 >= n1: ch1 = 0 
        if p2 + 1 >= n2: ch2 = 0
        
        if ch1 and ch2:
            t1 = pos[p1] * pos[p1 + 1] * pos[p1 + 2]
            t2 = neg[p2] * neg[p2 + 1] * pos[p1]
            if t1 >= t2:
                ans = (ans * t1) % M
            else:
                ans = (ans * t2) % M
        elif ch1:
            t1 = pos[p1] * pos[p1 + 1] * pos[p1 + 2]
            ans = (ans * t1) % M
        elif ch2:
            if p1 < n1:
                t2 = neg[p2] * neg[p2 + 1] * pos[p1]
                ans = (ans * t2) % M
            else:
                if len(zero) > 0: ans = 0
                else:
                    tmp = []
                    for i in range(n):
                        if l[i] >= 0: tmp.append([l[i], 1])
                        else: tmp.append([-l[i], 0])
                    tmp.sort()
                    Ans = 1
                    for i in range(k1):
                        if tmp[i][1] == 1: Ans = (Ans * tmp[i][0]) % M
                        else: Ans = (Ans * tmp[i][0] * -1) % M
                    ans = Ans
        else:
            if len(zero) > 0: ans = 0
            else:
                t2 = neg[p2] * pos[p1] * pos[p1 + 1]
                ans = (ans * t2) % M
print(ans)

Submission status: Accepted

Solution code:
def main():
    mod=1000000007
    inv=lambda x: pow(x,mod-2,mod)
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    B=A[::-1]
    ans=1
    if A[-1]<=0:
        if k%2==0:
            for a in A[:k]:
                ans*=a
                ans%=mod
        else:
            for a in B[:k]:
                ans*=a
                ans%=mod
        return ans
    if n==k:
        for a in A:
            ans*=a
            ans%=mod
        return ans
    Neg=[]; Pos=[]
    zero=0
    for a in A:
        if a>0:
            Pos.append(a)
        elif a<0:
            Neg.append(a)
        else:
            zero+=1
    if zero>n-k:
        return 0
    pos=len(Pos); neg=len(Neg)
    if neg==0:
        for a in B[:k]:
            ans*=a
            ans%=mod
        return ans
    for _ in range(zero):
        Neg.append(0)
    Neg.reverse()
    Pos.reverse()
    cnt=k
    while cnt>pos:
        cnt-=2
    Pos=Pos[:cnt]
    for p in Pos:
        ans*=p
        ans%=mod
    for _ in range(k-cnt):
        ans*=Neg.pop()
        ans%=mod
    while len(Pos)>=2 and len(Neg)>=2:
        p1=Pos.pop()
        p2=Pos.pop()
        n1=Neg.pop()
        n2=Neg.pop()
        if p1*p2<=n1*n2:
            ans*=inv(p1)*inv(p2)
            ans*=n1
            ans%=mod
            ans*=n2
            ans%=mod
        else:
            break
    return ans
    
if __name__=='__main__':
    print(main())

Submission status: Accepted

Solution code:
from queue import PriorityQueue
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


mod = 10**9+7


def prod(l):
    ret = 1
    for e in l:
        e %= mod
        ret = (ret*e) % mod

    return ret


def main():
    n, k = geta(int)
    a = list(geta(int))

    p, n, z = [], [], 0
    for ai in a:
        if ai > 0:
            p.append(ai)
        elif ai < 0:
            n.append(-ai)
        else:
            z += 1

    ans = 1
    p.sort()
    n.sort()
    if k & 1 == 1:
        if len(p) == 0:
            if z > 0:
                print(0)
                exit()
            else:
                print(-prod(n[0:k]) % mod)
                exit()
        else:
            k -= 1
            ans = p.pop() % mod

    if len(p) + len(n) < k:
        print(0)
        exit()

    if len(n) & 1 == 1 and (len(p) + len(n) == k):
        if z > 0:
            print(0)
            exit()
        else:
            print(-prod(p) * prod(n) % mod)
            exit()

    q = []

    n = n[::-1]
    for i in range(len(n)//2):
        q.append(n[2*i]*n[2*i+1])

    p = p[::-1]
    for i in range(len(p)//2):
        q.append(p[2*i]*p[2*i+1])

    q.sort(reverse=True)

    ans = ans * (prod(q[:k//2])) % mod

    print(ans % mod)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

A.sort(reverse=True)

deque = deque()
for a in A:
    deque.append(a)

ans = 1
cnt = 0
if K%2 == 1:
    ans *= deque.popleft()
    cnt += 1
    
if ans <= 0:
    for i in range(K-1):
        ans *= deque.popleft()
        ans %= mod
else:
    while cnt < K:
        x1 = deque.popleft()
        x2 = deque.popleft()
        deque.appendleft(x2)
        deque.appendleft(x1)
        y1 = deque.pop()
        y2 = deque.pop()
        if x1*x2 < y1*y2:
            ans *= y1*y2
            ans %= mod
            cnt += 2
        else:
            ans *= x1*x2
            ans %= mod
            if deque:
                x1 = deque.popleft()
            if deque:
                x2 = deque.popleft()
            deque.append(y2)
            deque.append(y1)
            cnt += 2
            
print(ans)

Submission status: Accepted

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

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

    a.sort()
    ret = 1
    if k % 2 == 0 or a[-1] >= 0:
        l = 0
        r = -1
        mlt1 = a[0] * a[1]
        mlt2 = a[-2] * a[-1]
        for _ in range(k//2):
            if mlt1 >= mlt2:
                ret *= mlt1 % mod
                l += 2
                if l <= n-2:
                    mlt1 = a[l+1] * a[l]
            else:
                ret *= mlt2 % mod
                r -= 2
                if r >= -n+1:
                    mlt2 = a[r-1] * a[r]
            ret %= mod

        if k % 2 == 1:
            ret *= a[r]
            ret %= mod

    else:
        for i in range(k):
            ret *= a[n-1-i]
            ret %= mod

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split(' '))
A = sorted(list(map(int, input().split(' '))))
mod = 10 ** 9 + 7
p = 0
for i in range(N):
    if A[i] >= 0:
        break
p = i
if (p == N - 1 and K % 2 != 0):
    ans = 1
    for i in range(K):
        ans *= A[-1 - i]
        ans %= mod
    print(ans%mod)
    exit()
minus = A[:p]
plus = sorted(A[p:],reverse=True)
len_m = len(minus)
len_p = len(plus)
m = 0
p = 0
ans = 1
while K > 0:
    if K >= 2 and m <= len_m - 2 and p <= len_p - 2:
        if minus[m] * minus[m+1] >= plus[p] * plus[p + 1]:
            ans *= minus[m] * minus[m + 1]
            ans %= mod
            m += 2
        else:
            ans *= plus[p] * plus[p + 1]
            ans %= mod
            p += 2
        K -= 2
    elif K >= 2 and m <= len_m - 2:
        ans *= minus[m] * minus[m + 1]
        ans %= mod
        m += 2
        K -= 2
    elif K >= 2 and p <= len_p - 2:
        ans *= plus[p] * plus[p + 1]
        ans %= mod
        p += 2
        K -= 2
    elif p <= len_p - 1:
        ans *= plus[p]
        ans %= mod
        p += 1
        K -= 1
    else:
        ans *= minus[m]
        ans %= mod
        m += 1
        K -= 1
print(ans%mod)