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: Runtime Error

Solution code:
n, k = map(int, input().split())
aa = list(map(int, input().split()))
import numpy as np
aa = np.array(aa)
mod = 10**9+7

def mul(dd):
    ret = 1
    for d in dd:
        ret = (ret*d)%mod
    return ret

def sol(aa, n, k):
    aap = aa[aa>0]
    aam = aa[aa<0]
    if n == k:
        return mul(aa)
    if len(aam) == n and k%2==1:
        aam.sort()
        aam = aam[::-1]
        return mul(aam[:k])

    aap.sort()
    aap = aap[::-1]
    aam.sort()

    ret=1
    if k%2 >0:
        k = k-1
        ret *= aap[0]
        aap = aap[1:]

    aap2 = [aap[2*i]*aap[2*i+1] for i in range(len(aap)//2)]
    aam2 = [aam[2*i]*aam[2*i+1] for i in range(len(aam)//2)]
    ip=0
    im=0
    for i in range(k//2):
        if ip < len(aap2) and aap2[ip] >= aam2[im]:
            ret = (ret * aap2[ip])%mod
            ip += 1
        else:
            ret = (ret * aam2[im])%mod
            im += 1
    return ret%mod

print(sol(aa, n, k))

Submission status: Runtime Error

Solution code:
import functools
import operator

prod = functools.partial(functools.reduce, operator.mul)


def main():
    n, k = map(int, input())
    a = map(int, input())

    a.sort(reversed=True)
    if a[-1] >= 0:
        print(prod(a[:k]))
        return
    if a[0] == 0:
        for i, _a in enumerate(a):
            if a[i] != 0:
                break
        else:
            print(0)
            return
        if k > len(a) - ind - 1:
            print(0)
            return
        if k % 2 == 1:
            print(0)
            return
        print(prod(a[len(a)-k:])
        return
    
    left = 0
    right = len(a) - 1
    ret = 1
    i = 0
    while i < k:
        if i < k - 1:
            if a[left] * a[left+1] < a[right] * a[right-1]:
                ret *= a[right] * a[right-1]
                right -= 2
            else:
                ret *= a[left] * a[left+1]
                left += 2
            i += 2
        else:
            ret *= a[left]
            left += 1
            i += 1
    print(ret)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7

N, K = map(int, input().split())
A = list(map(int, input().split()))
negatives = []
num_zero = 0
positives = []
for a in A:
    if a < 0:
        negatives.append(a)
    elif a == 0:
        num_zero += 1
    else:
        positives.append(a)
negatives.sort(reverse=True)
positives.sort(reverse=True)

n = 0
while n + 2 <= len(negatives) and n + 2 <= K:
    n += 2
answer_is_positive = K - n <= len(positives)
if answer_is_positive:
    others = []
    if K <= len(positives):
        nums = positives[-K:]
    else:
        if (K - len(positives)) % 2 == 0:
            nums = positives[:]
        else:
            nums = positives[:-1]
        while len(nums) + len(others) < K:
            n1 = negatives.pop()
            n2 = negatives.pop()
            others.extend([n1, n2])

    while True:
        if not (2 <= len(negatives) and 2 <= len(positives)):
            break
        p1, p2 = nums[-1], nums[-2]
        n1, n2 = negatives.pop(), negatives.pop()
        if n1 * n2 <= p1 * p2:
            break
        others.extend([n1, n2])
        nums.pop()
        nums.pop()
    ans = 1
    for x in nums + others:
        ans = ans * x % MOD
elif K <= len(negatives) + len(positives):
    negatives.sort()
    nums = [negatives.pop()]
    while 2 <= len(negatives) and len(nums) + 2 <= K:
        nums.extend([negatives.pop(), negatives.pop()])
    nums.sort()
    others = []
    while len(nums) < K and positives:
        others.append(positives.pop())

    while True:
        if not (2 <= len(nums) and 2 <= len(positives)):
            break
        p1, p2 = positives[-1], positives[-2]
        n1, n2 = nums[-1], nums[-2]
        if n1 * n2 <= p1 * p2:
            break
        others.extend([p1, p2])
        nums.pop()
        nums.pop()
    ans = 1
    for x in nums + others:
        ans = ans * x % MOD
else:
    ans = 0

if 0 < num_zero and ans < 0:
    ans = 0
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
import bisect as bs
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
def adj(n): return [[] for _ in range(n)]

#整数問題セット
def gcd(numbers): return func.reduce(frac.gcd, numbers)
def lcm(numbers): return func.reduce(LCM, numbers)
def inv(a): return pow(a, MOD-2, MOD) #逆元
def comb(n,r):
    ans = 1
    for i in range(r): ans *= n-i; ans *= inv(r-i); ans %= MOD
    return ans

n,k = imap()
a = iarr()
b = np.array([[num, abs(num)] for num in a])
b = b[b[:,1][::-1].argsort(), : ]
c = b[:,0]

ans = 1
for i in range(k):
    ans *= c[i]
    ans = ans%MOD if ans>0 else -(-ans%MOD)

i = k
while ans < 0:
    ans // c[i]
    i += 1
    if i >= n: break
    ans *= c[i]
    ans = ans%MOD if ans>0 else -(-ans%MOD)
    
if ans > 0: print(ans)
else:
    ans = 1
    d = c[::-1]
    for i in range(k):
        ans *= d[i]
        ans = ans%MOD if ans<0 else -(-ans%MOD)
    ans = 0 if 0 in set(d) else ans

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right

mod = 10 ** 9 + 7
n, k = map(int, input().split())
A = list(map(int, input().split()))
# dp = [[[0] * (2) for _ in range(k+1)]for _ in range(n+1)]
# # dp[桁][数][負数の数=1,0]

A.sort()
n_minus = bisect_left(A, 0)
n_zero = bisect_right(A, 0) - n_minus
n_plus = n - n_minus - n_zero

possible_max = min(k, n_minus)
possible_min = max(k - (n_plus + n_zero), 0)
ans = 1
if possible_max == possible_min and possible_min % 2 == 1:
    if k - (possible_min) > 0 and n_zero > 0:
        print(0)
        exit()
    A_plus = A[n - (n_plus) :]
    A_minus = A[:n_minus]
    A_minus.sort(reverse=True)
    # 負の数は奇数個小さい方から選ぶ
    for i in range(possible_min):
        ans *= A_minus[i]
        ans %= mod
    for i in range(k - possible_min):
        ans *= A_plus[i]
        ans %= mod
else:
    # 正の数に成る→大きいものがほしい
    # 負の数は偶数個、これの数を決め打つ
    # 計算すると大変だから大小を考える

    A_plus = A[n - (n_plus) :]
    A_plus.sort(reverse=True)
    A_minus = A[:n_minus]

    # 負の数を使う数を決め打つ
    # 最終的に正にできるパターン
    minus_num_max = min(n_minus // 2, k // 2)
    select = k - 2 * minus_num_max
    if n_plus < select:
        print(0)
        exit()
    # 負の数にしかできないパターン
    # 遊びがない時に奇数個の負の数を選ばざるを得ない
    # その時に0があるかどうかパターン
    kouho = []
    for i in range(minus_num_max):
        if 2 * i + 1 >= n_minus:
            break
        temp = A_minus[2 * i] * A_minus[2 * i + 1]
        kouho.append((temp, -1))
    for i in range(n_plus // 2):
        temp = A_plus[2 * i] * A_plus[2 * i + 1]
        kouho.append((temp, +1))
    kouho.sort(reverse=True)
    if k % 2 == 0:
        for i in range(k // 2):
            ans *= kouho[i][0]
            ans %= mod
    else:
        cnt = 0
        i = 0
        for i in range(k // 2):
            num, f = kouho[i]
            if f == 1:
                cnt += 1
            ans *= num
            ans %= mod
        ans *= A_plus[2 * cnt]
        ans %= mod


print(ans)

Submission status: Runtime Error

Solution code:
def solmax(a,i,j):
    if j==0:
        return 1
    if i==j:
        return p[i]
    u=solmax(a,i-1,j)
    if a[i-1]>0:
        u=max(u,solmax(a,i-1,j-1)*a[i-1])
    elif a[i-1]<0:
        u=max(u,solmin(a,i-1,j-1)*a[i-1])
    else:
        u=max(u,0)
    return u
def solmin(a,i,j):
    if j==0:
        return 1
    if i==j:
        return p[i]    
    u=solmin(a,i-1,j)
    if a[i-1]>0:
        u=min(u,solmin(a,i-1,j-1)*a[i-1])
    elif a[i-1]<0:
        u=min(u,solmax(a,i-1,j-1)*a[i-1])
    else:
        u=min(u,0)
    return u
s=input().split(' ') 
n=int(s[0])
k=int(s[1])
s=input().split(' ')
a=[int(d) for d in s]
p=[1]
for i in range(n):
    p.append(p[-1]*a[i])
print(solmax(a,n,k)%1000000007)

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n,k = map(int,readline().split())
lst1 = list(map(int,readline().split()))

mod = 10**9+7

#全部使う
if n == k:
    ans = 1
    for i in lst1:
        ans *= i
        ans %= mod
    print(ans)
    exit() 

lst1.sort()
i = 0
minus = []
m = 0
while i < n and lst1[i] < 0:
    minus.append(lst1[i])
    m += 1
    i += 1
zero = 0
while i < n and lst1[i] == 0:
    zero += 1
    i += 1
plus = []
p = 0
while i < n:
    plus.append(lst1[i])
    p += 1
    i += 1

#必ず0を使う
if n-zero < k:
    print(0)
    exit()

#少なくともans<=0になる(負数にしかならない場合、0を掛けた方が良い場合)
if p==0 and not even(k):
    if zero:
        print(0)
        exit()
    else:
        ans = 1
        for i in range(k):
            ans *= minus[-1-i]
            ans %= mod
        print(ans)
        exit()

#0を使わないようにすると、ちょうど負数が奇数個になってしまう場合
if n-zero == k and not even(m):
    print(0)
    exit()

#以下、必ず正の数にできる
#まだなんか見落としあるかも…

#負数はこの時点で上位からペアとして良い
pair = []
if m >= 2:
    for i in range(0,m-1,2): #絶対値が大きい順
        pair.append(minus[i]*minus[i+1])

ans = 1
midx = 0 #cost2
pidx = 0 #cost1
plus.reverse() #降順
while k:
    if k == 1:
        if pidx < len(plus):
            ans *= plus[pidx]
            ans %= mod
            k -= 1
            pidx += 1
        else:
            print(0)
            exit()
    elif k == 2:
        if midx < len(pair) and pidx+1 < len(plus):
            if pair[midx] >= plus[pidx]*plus[pidx+1]:
                ans *= pair[midx]
                ans %= mod
                k -= 2
            else:
                ans *= plus[pidx]*plus[pidx+1]
                ans %= mod
                k -= 2

        elif midx <= len(pair):
            ans *= pair[midx]
            ans %= mod
            k -= 2
        else:
            ans *= plus[pidx]*plus[pidx+1]
            ans %= mod
            k -= 2
        
        break
    elif k >= 3:
        if midx < len(pair):
            if pidx+2 < len(plus): #max-2がある
                if pair[midx] >= plus[pidx+1]*plus[pidx+2]:
                    ans *= pair[midx]
                    ans %= mod
                    midx += 1
                    k -= 2
                else:
                    ans *= plus[pidx]
                    ans %= mod
                    pidx += 1
                    k -= 1
            elif pidx+1 < len(plus): #max-1がある
                if pair[midx] >= plus[pidx]*plus[pidx+1]:
                    ans *= pair[midx]
                    ans %= mod
                    midx += 1
                    k -= 2
                else:
                    ans *= plus[pidx]
                    ans %= mod
                    pidx += 1
                    k -= 1
            elif pidx < len(plus): #maxしかない
                if pair[midx] >= plus[pidx]:
                    ans *= pair[midx]
                    ans %= mod
                    midx += 1
                    k -= 2
                else:
                    ans *= plus[pidx]
                    ans %= mod
                    pidx += 1
                    k -= 1
            else: #plusにない
                ans *= pair[midx]
                ans %= mod
                midx += 1
                k -= 2

                
        else:
            ans *= plus[pidx]
            ans %= mod
            pidx += 1
            k -= 1

print(ans)

Submission status: Runtime Error

Solution code:
def modInverse(a, m) :
	return power(a, m - 2, m) 
      
# To compute x^y under modulo m 
def power(x, y, m) : 
      
    if (y == 0) : 
        return 1
          
    p = power(x, y // 2, m) % m 
    p = (p * p) % m 
  
    if(y % 2 == 0) : 
        return p  
    else :  
        return ((x * p) % m) 
  
# Function to return gcd of a and b 
def gcd(a, b) : 
	while a and b:
		if a>b: a%=b
		else: b%=a 
	return max(a,b)


















P = 1000000007

n,k=map(int,input().split())
a = [int(i) for i in input().split()]
ans = 1
neg = 0
for i in a:
	if i<0:neg+=1
if neg==n:
	a.sort(reverse=True)
	for i in range(k):
		ans = (ans*a[i])%P
	print(ans)
	exit(0)

a.sort()
l = 0
r = n-1
while k>0:
	if k>1:
		Ol = a[l]*a[l+1]
		Or = a[r]*a[r-1]
		if Ol > Or:
			ans = (ans*(Ol%P))%P
			l+=2
		else:
			ans = (ans*(Or%P))%P
			r-=2
		k-=2
	else:
		if a[r]==0:
			ans = (ans * modInverse(a[r+1],P))%P
			ans = (ans * (a[l]*a[l+1])%P)%P
		else: ans = (ans*a[r])%P
		k-=1
print(ans)
# ~ -1 -1 0 2 3

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit
#input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

zero = 0
for a in A:
    if a == 0:
        zero += 1

if N - zero < K:
    print(0)
    exit()
    
minus = []
plus = []
for a in A:
    if a < 0:
        minus.append(a)
    if a > 0:
        plus.append(a)

plus.sort()
minus.sort()

if K % 2:
    if len(plus):
        answer = plus.pop()
    else:
        answer = minus.pop()
    K -= 1
else:
    answer = 1
K //= 2

plus = plus[::-1]
if answer < 0:
    minus = minus[::-1]

plus2 = []
len_plus = len(plus)
for i in range(len_plus):
    if i % 2 == 0 and i + 1 < len_plus:
        plus2.append(plus[i] * plus[i + 1])
#print(plus2)

minus2 = []
len_minus = len(minus)
for i in range(len_minus):
    if i % 2 == 0 and i + 1 < len_minus:
        minus2.append(minus[i] * minus[i + 1])
#print(minus2)

ip, im = 0, 0
lp, lm = len(plus2), len(minus2)
while ip + im < K:
    if ip < lp:
        ip += 1
    else:
        im += 1
#print(ip, im)

while 1:
    if im == lm:
        break
    if ip == 0:
        break
    if minus2[im] > plus2[ip - 1]:
        im += 1
        ip -= 1

#print(ip, im)
#print(answer)

for i, p in enumerate(plus2):
    if i == ip:
        break
    answer = (answer * p) % MOD
for i, m in enumerate(minus2):
    #print(m)
    if i == im:
        break
    answer = (answer * m) % MOD

print(answer)

Submission status: Runtime Error

Solution code:
class modNumber:
    prime = 10**9 + 7
    def __init__(self, num):
        self.num = num % modNumber.prime

    def __add__(self, other):
        return modNumber(self.num + other.num)

    def __sub__(self, other):
        return modNumber(self.num - other.num)

    def __mul__(self, other):
        return modNumber(self.num*other.num)

    def __truediv__(self, other):
        return modNumber(self.num*other.reciprocal())

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

    def reciprocal(self):
        ans = modNumber(1)
        buffer = modNumber(self.num)
        exp = modNumber.prime - 2
        while exp:
            if exp & 1:
                ans = ans * buffer
            buffer = buffer * buffer
            exp = exp >> 1
        return ans.num

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

A_p = [a for a in A if a > 0]
A_p.sort(reverse=True)
A_m = [a for a in A if a < 0]
A_m.sort()
A_m = [a1*a2 for a1, a2 in zip(A_m[::2], A_m[1::2])]


result = modNumber(1)

if len(A_p) + len(A_m)*2 >= K or (len(A_p) == 0 and K%2 == 1):
    # answer is positive
    i = 0
    j = 0
    A_p.append(-float("inf"))
    A_m.append(-float("inf"))
    while K > 1:
        if A_p[i] + A_p[j] > A_m[j]:
            result = result * modNumber(A_p[i])
            i += 1
            K -= 1
        else:
            result = result * modNumber(A_m[j])
            j += 1
            K -= 2
    if K == 1:
        if i == len(A_p) - 1:
            result = result * modNumber(A_m[j])
            result = result / modNumber(A_p[-2])
        else:
            result = result * modNumber(A_p[i])
else:
    # answer is negative
    result = modNumber(-1)
    A = list(map(abs, A))
    A.sort()
    for a in A[:K]:
        result = result * modNumber(a)

# ZERO


print(result)

Submission status: Runtime Error

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

m=[]
p=[]
z=0
for i in range(n):
    if a[i]<0:
        m.append(-a[i])
    elif a[i]>0:
        p.append(a[i])
    else:
        z+=1
m=sorted(m,reverse=True)
p=sorted(p,reverse=True)

if k>len(m)+len(p):
    print(0)
    sys.exit()

if len(p)==0:
    ans=1
    if k%2==0:
        for i in range(k):
            ans*=m[i]
            ans%=mod
        print(ans)
        sys.exit()
    else:
        for i in range(k):
            if i==k-1:
                ans*=-m[-i-1]
                ans%=mod
            else:
                ans*=m[-i-1]
                ans%=mod
        print(ans)
        sys.exit()

if len(m)==0:
    ans=1
    for i in range(k):
        ans*=p[i]
        ans%=mod
    print(ans)
    sys.exit()



q=[]
if len(m)%2==0:
    for i in range(len(m)//2):
        q.append(m[2*i]*m[2*i+1])
else:
    for i in range(len(m)//2):
        q.append(m[2*i]*m[2*i+1])
    q.append(m[-1])

pp=0
qq=0
c=0
ans=1
if k%2==1:
    ans*=p[pp]
    pp+=1
    c+=1
while c<k:
    if pp<len(p) and qq<len(q):
        if p[pp]*p[pp+1]>q[qq]:
            ans*=p[pp]*p[pp+1]
            pp+=2
        else:
            ans*=q[qq]
            qq+=1
        ans%=mod
        c+=2

    elif pp>=len(p)-1:
        ans*=q[qq]
        ans%=mod
    else:
        ans*=p[pp]*p[pp+1]
        ans%=mod

print(ans)

Submission status: Runtime Error

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

positive = []
negative = []
zero = 0
for t in a:
    if t < 0:
        negative.append(t)
    elif t == 0:
        positive.append(0)
        zero += 1
    else:
        positive.append(t)
if n - zero < k:
    print(0)
    exit()

positive.sort()
negative.sort(reverse=True)

if not positive:
    ans = 1
    if k % 2 == 1:
        if zero != 0:
            print(0)
            exit()
        for i in range(k):
            ans *= negative[i]
            ans %= mod
    else:
        for i in range(k):
            ans *= negative.pop()
            ans %= mod
    print(ans)
    exit()

ans = 1
# negative 処理
check = []
if len(negative) % 2 == 1:
    negative = negative[1:]
while negative:
    check.append(negative.pop() * negative.pop())

# positive
if k % 2 == 1:
    ans *= positive.pop()
    k -= 1

if len(positive) % 2 == 1:
    positive = positive[1:]
while positive:
    check.append(positive.pop() * positive.pop())
check.sort()

for i in range(k//2):
    ans *= check.pop()
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
M = 10**9 + 7

ans = 1
posA = sorted([a for a in A if a > 0])
negA = sorted([a for a in A if a < 0])
for _ in range(K // 2):
    if len(negA) < 2:
        ans = ans * posA[-1] * posA[-2] % M
        posA.pop()
        posA.pop()
        continue

    if len(posA) < 2:
        ans = ans * negA[-1] * negA[-2] % M
        negA.pop()
        negA.pop()
        continue

    p1 = negA[-1] * negA[-2]
    p2 = posA[-1] * posA[-2]
    if p1 > p2:
        ans = ans * p1 % M
        negA.pop()
        negA.pop()
    else:
        ans = ans * p2 % M
        posA.pop()
        posA.pop()

# print(ans)

if K % 2 == 1:
    if len(negA) == 0:
        ans = ans * posA[-1] % M
    elif len(posA) == 0:
        ans = ans * negA[-1] % M    
    else:
        if ans < 0:
            ans = ans * negA[-1] % M
        else:
            ans = ans * posA[-1] % M


print(ans)

Submission status: Runtime Error

Solution code:
#                          JAI SHREE RAM

import math; from collections import *
import sys; from functools import reduce

# sys.setrecursionlimit(10**6)
def get_ints(): return map(int, input().strip().split())
def get_list(): return list(get_ints())
def get_string(): return list(input().strip().split())
def printxsp(*args): return print(*args, end="")
def printsp(*args): return print(*args, end=" ")

UGLYMOD = int(1e9)+7; SEXYMOD = 998244353; MAXN = int(1e5)

sys.stdin=open("input.txt","r");sys.stdout=open("output.txt","w")

# for _testcases_ in range(int(input())):
n, k = get_ints()
li = get_list()
pos = []
neg = []
ans = 1
zeroes = 0
for i in li:
    if i < 0: neg.append(i)
    elif i > 0: pos.append(i)
    else: zeroes += 1
lengthOfPos, lengthOfNeg = len(pos), len(neg)

if lengthOfNeg + lengthOfPos < k :
    print("0")
elif k&1 : #and (k - lengthOfPos) >= 0 and (k - lengthOfPos) & 1:
    if k > lengthOfPos:
        if zeroes:
            print("0")
        else:
            # last pr pakka negative ayega
            pos.sort(); positionOfPos = 0
            neg.sort(reverse = True); positionOfNeg = 0
            while k > 1:
                try: negpower = neg[positionOfNeg] * neg[positionOfNeg+1]
                except: negpower = float('inf')
                try: pospower = pos[positionOfPos] * pos[positionOfPos+1]
                except: pospower = float('inf')
                if pospower <= negpower:
                    positionOfPos += 2
                    ans = (ans * (pospower % UGLYMOD)) % UGLYMOD
                else:
                    ans = (ans * (negpower % UGLYMOD)) % UGLYMOD
                    positionOfNeg += 2
                k -= 2
            if k == 1:
                try: negpower = neg[positionOfNeg]
                except: negpower = float('inf')
                try: pospower = pos[positionOfPos]
                except: pospower = float('inf')
                ans = (ans * min(pospower, negpower)) % UGLYMOD
            print(ans)
            
    else:
        pos.sort(reverse = True); positionOfPos = 0
        neg.sort(); positionOfNeg = 0
        ans = 1
        while k > 1:
            try: negpower = neg[positionOfNeg] * neg[positionOfNeg+1]
            except: negpower = -float('inf')
            try: pospower = pos[positionOfPos] * pos[positionOfPos+1]
            except: pospower = -float('inf')
            if pospower >= negpower:
                positionOfPos += 2
                ans = (ans * (pospower % UGLYMOD)) % UGLYMOD
            else:
                ans = (ans * (negpower % UGLYMOD)) % UGLYMOD
                positionOfNeg += 2
            k -= 2
        if k == 1:
            ans = (ans * pos[positionOfPos]) % UGLYMOD
        print(ans)
else:
    pos.sort(reverse = True); positionOfPos = 0
    neg.sort(); positionOfNeg = 0
    ans = 1
    while k > 1:
        try: negpower = neg[positionOfNeg] * neg[positionOfNeg+1]
        except: negpower = -float('inf')
        try: pospower = pos[positionOfPos] * pos[positionOfPos+1]
        except: pospower = -float('inf')
        if pospower >= negpower:
            positionOfPos += 2
            ans = (ans * (pospower % UGLYMOD)) % UGLYMOD
        else:
            ans = (ans * (negpower % UGLYMOD)) % UGLYMOD
            positionOfNeg += 2
        k -= 2
    if k == 1:
        ans = (ans * pos[positionOfPos]) % UGLYMOD
    print(ans)







'''
>>> COMMENT THE STDIN!! CHANGE ONLINE JUDGE !!
THE LOGIC AND APPROACH IS MINE @luctivud ( UDIT GUPTA )
Link may be copy-pasted here if it's taken from other source.
DO NOT PLAGIARISE.
>>> COMMENT THE STDIN!! CHANGE ONLINE JUDGE !!
'''

Submission status: Runtime Error

Solution code:
n,k = map(int, raw_input().split(' '))
ais = map(int , raw_input().split(' '))

pos = [ai for ai in ais if ai > 0]
pos.sort(key = lambda x:-x)
neg = [-ai for ai in ais if ai < 0]
neg.sort(key = lambda x:-x)

def g(neg, k):
	i = len(neg) -1
	r = 1
	while(k):
		r *= -neg[i]
		i -=1
		k -=1
		r %= (10 ** 9) + 7
	return r
def gg(pos, k):
	r =  1
	for i in range(k):
		r *= pos[i]
		r %= (10 **9) + 7
	return r
def f(pos,neg, k):

	if len(pos) == 0: return g(neg, k)
	if len(neg) <= 1: return gg(pos, k)

	i,j = 0,0
	p = 1
	mod = (10 ** 9) + 7
	while(k >= 2):
		if j + 1 < len(neg):
			if neg[j] * neg[j+1] > pos[i] * (pos[i+1] if i+1 < len(pos) else 1):
				p *= neg[j] * neg[j+1]
				p %= mod
				j += 2
				k -= 2
			else:
				p *= pos[i]
				i +=1
				p %= mod
				k -=1
	while(k):
		p *= pos[i]
		p %+ mod
		k-=1
		i+=1
	return p
print f(pos,neg, k)

Submission status: Runtime Error

Solution code:
import sys

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

A.sort(reverse=True)

P = []
M = []
Ans = []
p = 0
m = 0

for i in range(N):
    if 0 <= A[i]:
        P.append(A[i])
    else:
        M.append(A[i])

M.sort()

if K % 2 == 1 and len(P) != 0:
    Ans.append(P[p])
    p += 1
elif K % 2 == 1 and len(P) == 0:
    M.sort(reverse=True)
elif len(M) == 0:
    answer = 1
    for i in range(K):
        answer = (answer * P[i]) % 1000000007

    print(answer)
    sys.exit()

while len(Ans) < K:

    #Mのストックがもうない時
    if m+1 >= len(M):
        Ans.append(P[p])
        if len(Ans) == K:
            break
        Ans.append(P[p + 1])
        p += 2
    elif p+1 >= len(P):
        Ans.append(M[m])
        if len(Ans) == K:
            break
        Ans.append(M[m + 1])
        m += 2
    elif m >= len(M):
        Ans.append(P[p])
        p += 1
    elif p >= len(P):
        Ans.append(M[m])
        m += 1
    else:
        if P[p]*P[p+1] < M[m]*M[m+1]:
            Ans.append(M[m])
            Ans.append(M[m+1])
            m += 2
        else:
            Ans.append(P[p])
            Ans.append(P[p + 1])
            p += 2

answer = 1
for i in range(K):
    answer = (answer * Ans[i]) % 1000000007

print(answer)

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

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

def smp_solve(arr, n):
    ans = 1
    for i in range(n):
        ans *= arr[i]
        ans %= mod
    return ans

def compare_two_give_max(pos, neg, pos_pair, neg_pair, K):
    i = 0
    j = 0
    ans = 1
    neg_last = True
    while i < len(pos_pair) and j < len(neg_pair) and K > 0:
        if pos_pair[i] > neg_pair[j]:
            ans *= pos_pair[i]
            i += 1
            neg_last = False
        else:
            ans *= neg_pair[j]
            j += 1
            neg_last = True
        K -= 2
        ans %= mod

    while K > 0 and i == len(pos_pair) and j < len(neg_pair):
        # negがなくなるまでタス
        ans *= neg_pair[j]
        j += 1
        K -= 2
        ans %= mod
        neg_last = True

    while K > 0 and i < len(pos_pair) and j == len(neg_pair):
        # posがなくなるまでタス
        ans *= pos_pair[i]
        i += 1
        K -= 2
        ans %= mod
        neg_last = False

    if K == -1:
        if neg_last:
            # 足しすぎた分をわる
            ans *= gyaku(neg_pair[j-1])
            ans *= pos[2*i]
            # TODO: iがoutOfArray
            ans %= mod
        else:
            ans *= gyaku(pos_pair[2*i-1])
            ans %= mod
    return ans, K

def main():
    global cnt
    N, K = LI()
    A = LI()
    if N == K:
        ans = smp_solve(A, N)
        print(ans)
        return

    neg = []
    pos = []
    zero_exist = False
    for a in A:
        if a < 0:
            neg.append(a)
        elif a > 0:
            pos.append(a)
        else:
            zero_exist = True
    neg = sorted(neg) # -12, -3
    pos = sorted(pos)[::-1] # 4, 3, 2, 1
    if len(pos) == 0:
        ans = 1
        neg = neg[::-1] # -3, -12
        for n in neg[:K]:
            ans *= n
            ans %= mod
        if zero_exist:
            ans *= 0
        print(ans % mod)
        return

    if len(neg) == 0:
        ans = 1
        for p in pos[:K]:
            ans *= p
            ans %= mod
        print(ans % mod)
        return


    neg_paired = []
    pos_paired = []

    i = 0
    neg_amari = -inf
    while i+1 < len(neg):
        neg_paired.append(neg[i] * neg[i+1])
        i += 2
    if len(neg) % 2 == 1:
        neg_amari = neg[-1]

    i = 0
    pos_amari = -inf
    while i+1 < len(pos):
        pos_paired.append(pos[i] * pos[i+1])
        i += 2
    if len(pos) % 2 == 1:
        pos_amari = pos[-1]

    # print('pos: ', pos)
    # print('neg: ', neg)
    # print('pos_pair: ', pos_paired)
    # print('neg_pair: ', neg_paired)
    if len(pos_paired) == 0 and len(neg_paired) == 0:
        if K == 1:
            cnt *= pos_amari
        elif K == 2:
            if zero_exist:
                cnt = 0
            else:
                cnt = pos_amari * neg_amari


    else:
        res, k = compare_two_give_max(pos, neg, pos_paired, neg_paired, K)
        # print('res: ', res)
        # print('k: ', k)
        cnt *= res
        if k > 1:
            if pos_amari != -inf:
                cnt *= pos_amari
            elif neg_amari != -inf:
                if zero_exist:
                    cnt *= 0
                else:
                    cnt *= neg_amari
    print(cnt % mod)
    return

main()