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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

class ModInt(int):

    MOD = 10 ** 9 + 7

    def __add__(self, other):
        self = ModInt(int.__add__(self, other) % ModInt.MOD)
        return self

    def __mul__(self, other):
        self = ModInt(int.__mul__(self, other) % ModInt.MOD)
        return self

def mysplit(data):
    ps = [] # include 0
    ms = []
    for d in data:
        if d < 0:
            ms.append(ModInt(d))
        else:
            ps.append(ModInt(d))
    return list(reversed(sorted(ps))), sorted(ms)

def small_abs(ms, k):
    ans = ModInt(1)
    ms = list(reversed(ms))
    for i in range(k):
        ans *= ms[i]
    return ans

def take_p(ans, k, ps, pk):
    ans *= ps[pk]
    pk += 1
    return ans, k - 1, pk

def take_m(ans, k, ms, mk, sign_p):
    ans *= ms[mk]
    mk += 1
    return ans, k - 1, mk, sign_p

def take_all_m(ans, k, ms, mk, sign_p):
    while k > 0:
        ans, k, mk, sign_p = take_m(ans, k, ms, mk, sign_p)
    return ans

def solve(data, k):
    ps, ms = mysplit(data)
    if len(ps) == 0:
        return small_abs(ms, k)
    ans = ModInt(1)
    sign_p = True
    pk = 0
    mk = 0
    while k > 0:
        if pk == len(ps) - 1: # last p
            if k % 2 == 1:
                ans, k, pk = take_p(ans, k, ps, pk)
                k -= 1
                #print('hoge') # debug
            return take_all_m(ans, k, ms, mk, sign_p)
        if mk >= len(ms) or ps[pk] > -1 * ms[mk]:
            ans, k, pk = take_p(ans, k, ps, pk)
        else:
            ans, k, mk, sign_p = take_m(ans, k, ms, mk, sign_p)
    return ans



if __name__ == '__main__':
    n, k = list(map(int, input().split()))
    data = list(map(int, input().split()))
    ans = solve(data, k)
    #print('ans') # debug
    print(ans)



    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
n,k = map(int,input().split())
a_list = sorted(map(int,input().split()))
mod = 10**9+7
if n-k < a_list.count(0):
    print(0)
    sys.exit()
if sum([1 for a in a_list if np.sign(a)==-1])==k:
    a_list.sort(key = abs)
    ans = 1
    for num in a_list[:k]:
        ans *= num
        ans %= mod
    print(ans)
    sys.exit()
else:
    a_list.sort(key = abs,reverse = True)
    add = 1
    remove = 1
    if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
        nagative_big = [num for num in a_list[:k] if np.sign(num)==-1]
        positive_big = [num for num in a_list[:k] if np.sign(num)!=-1]
        negative_small = [num for num in a_list[k:] if np.sign(num)==-1]
        positive_small = [num for num in a_list[k:] if np.sign(num)!=-1]
        
        if len(negative_big)==0 or len(positive_small):
            remove = min(positive_big)
            add = min(negative_small)
        elif len(positive_big)==0 or len(negative_small):
            remove = max(negative_big)
            add = max(positive_small)
        else:
            if max(positive_small)/max(negative_big) < min(negative_small)/min(positive_big):
                remove = max(negative_big)
                add = max(positive_small)
            else:
                remove = positive_big
                add = negative_small
ans = 1
for num in a_list[:k]:
    ans *= num
    ans %= mod
    
if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
    ans *= add
    ans %= mod
    ans *= pow(remove, mod-2, mod)
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True, key = lambda x: abs(x))
mod = 10**9+7
nega = 0
posi = 0
zero = 0
for i in range(n):
    if a[i] > 0:
        posi += 1
    elif a[i] == 0:
        zero += 1
    else:
        nega += 1

if n == k:
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod
    if nega%2 == 1:
        ans *= -1

elif posi == 0:

    if k % 2 == 0:
        ans = 1
        for i in range(k):
            ans *= abs(a[i])
            ans %= mod

    else:
        if zero > 0:
            ans = 0
        else:
            a.reverse()
            ans = 1
            for i in range(k):
                ans *= abs(a[i])
                ans %= mod

            ans *= -1


else:
    posi = 0
    nega = 0
    zero = 0
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod

    for i in range(k):
        if a[i] > 0:
            posi += 1
        elif a[i] < 0:
            nega += 1
        else:
            zero += 1

    if zero > 0:
        ans = 0

    elif nega % 2 != 0:
        minposi = 0
        minnega = 0
        for i in range(k-1, -1, -1):
            if a[i] > 0:
                if minposi == 0:
                    minposi = a[i]
            else:
                if minnega == 0:
                    minnega = a[i]

        maxposi = 0
        maxnega = 0
        flag = 0
        for i in range(k, n):
            if a[i] > 0:
                if maxposi == 0:
                    maxposi = a[i]
            elif a[i] < 0:
                if maxnega == 0:
                    maxnega = a[i]

        if maxnega == 0:
            pp


        if abs(minposi*maxposi) <= abs(minnega*maxnega):
            ans *= pow(abs(minposi), mod-2, mod)
            ans *= abs(maxnega)

        else:
            ans *= pow(abs(minnega), mod-2, mod)
            ans *= abs(maxposi)



print(ans % mod)

Submission status: Runtime Error

Solution code:
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
import math
import fractions
import collections
import itertools
import pprint
from collections import deque
N,K=map(int,input().split())
A=list(map(int,input().split()))
ans=1
p=10**9+7
ab=[]
for i in range(N):
    ab.append([abs(A[i]),i])
ab.sort(key=lambda x:x[0],reverse=True)
micount=0
ans=1
for i in range(K):
    if A[ab[i][1]]<0:
        micount=micount+1
    ans=(ans*ab[i][0])%p
if micount%2==0:
    print(ans)
else:
    for i in range(N-K,N):
        if A[ab[i][1]]<0:
            divind=i
            break
    mulind=0
    for i in range(N-K-1,-1,-1):
        if A[ab[i][1]]>=0:
            mulind=i
            break
    ans=(ans*modinv(A[divind],p)*A[mulind])%p
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
n,k = map(int,input().split())
a_list = sorted(map(int,input().split()))
mod = 10**9+7
if n-k < a_list.count(0):
    print(0)
    exit()
if sum([1 for a in a_list if np.sign(a)==-1])==k:
    a_list.sort(key = abs)
    ans = 1
    for num in a_list[:k]:
        ans *= num
        ans %= mod
    print(ans)
    exit()
else:
    a_list.sort(key = abs,reverse = True)
    add = 1
    remove = 1
    if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
        nagative_big = [num for num in a_list[:k] if np.sign(num)==-1]
        positive_big = [num for num in a_list[:k] if np.sign(num)!=-1]
        negative_small = [num for num in a_list[k:] if np.sign(num)==-1]
        positive_small = [num for num in a_list[k:] if np.sign(num)!=-1]
        
        if len(negative_big)==0 or len(positive_small):
            remove = min(positive_big)
            add = min(negative_small)
        elif len(positive_big)==0 or len(negative_small):
            remove = max(negative_big)
            add = max(positive_small)
        else:
            if max(positive_small)/max(negative_big) < min(negative_small)/min(positive_big):
                remove = max(negative_big)
                add = max(positive_small)
            else:
                remove = positive_big
                add = negative_small
ans = 1
for num in a_list[:k]:
    ans *= num
    ans %= mod
    
if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
    ans *= add
    ans %= mod
    ans *= pow(remove, mod-2, mod)
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
modulo = 10 ** 9 + 7
*arr, = map(int, input().split())
inverses = [pow(v, modulo - 2, modulo) for v in arr]
neg_cnt = 0
for v in arr:
    if v < 0:
        neg_cnt += 1


def max_pos(arr):
    arr.sort(key=lambda obj: abs(obj), reverse=True)

    neg = []
    pos = []
    res = 1
    for i in range(k):
        res *= arr[i]
        res %= modulo
        if arr[i] < 0:
            neg.append(i)
        else:
            pos.append(i)

    if len(neg) % 2 == 0:
        return res

    next_neg = i
    next_pos = i
    while next_neg < len(arr) and arr[next_neg] >= 0:
        next_neg += 1

    while next_pos < len(arr) and arr[next_pos] < 0:
        next_pos += 1

    prev_neg = neg[-1]
    prev_pos = -1 if not pos else pos[-1]

    if (prev_pos == -1 or abs(arr[next_pos] * arr[prev_neg]) > abs(arr[prev_pos] * arr[next_neg])) and next_pos != len(arr):
        return (res * arr[next_pos] * inverses[prev_neg]) % modulo
    return (res * arr[next_neg] * inverses[prev_pos]) % modulo

def min_pos(arr):
    arr.sort(key=lambda obj: abs(obj))

    neg = []
    pos = []
    res = 1
    for i in range(k):
        res *= arr[i]
        res %= modulo
        if arr[i] < 0:
            neg.append(i)
        else:
            pos.append(i)

    if len(neg) % 2 == 1:
        return res

    next_neg = i
    next_pos = i
    while next_neg < len(arr) and arr[next_neg] >= 0:
        next_neg += 1

    while next_pos < len(arr) and arr[next_pos] < 0:
        next_pos += 1

    prev_neg = neg[-1]
    prev_pos = -1 if not pos else pos[-1]

    if (prev_pos == -1 or abs(arr[next_pos] * arr[prev_neg]) < abs(arr[prev_pos] * arr[next_neg])) and next_pos != len(arr):
        print(next_pos)
        return (res * arr[next_pos] * inverses[prev_neg]) % modulo
    return (res * arr[next_neg] * inverses[prev_pos]) % modulo


if neg_cnt == n and k % 2 == 1:
    print(min_pos(arr))
elif k == 1:
    print(max(arr) % modulo)
else:
    print(max_pos(arr))

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush
mod = 10**9+7
n, k = map(int, input().split())
a = [int(x) for x in input().split()]


def sgn(x):
    if x > 0:
        return 0
    elif x < 0:
        return 1
    else:
        return 2


pl = []
mn = []
zr = []

for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mn.append(-x)
    else:
        zr.append(x)

pl = sorted(pl, reverse=True)
mn = sorted(mn, reverse=True)


b = [(abs(a[i]), sgn(a[i])) for i in range(n)]
b = sorted(b, reverse=True)

c = [0, 0, 0]
for i in range(k):
    c[b[i][1]] += 1
    if c[2] > 1:
        print(0)
        exit()


def solve(c):
    ans = 1
    for i in range(c[0]):
        ans *= pl[i]
        ans %= mod
    for i in range(c[1]):
        ans *= mn[i]
        ans %= mod
    return ans


if c[1] % 2 == 0:
    print(solve(c))
elif c[0] < len(pl):
    c[0] += 1
    c[1] -= 1
    print(solve(c))
elif 0 < c[0] and c[0] == len(pl) and c[1] < len(mn):
    c[0] -= 1
    c[1] += 1
    print(solve())
else:
    if len(zr) > 0:
        print(0)
        exit()
    else:
        tmp = 1
        for i in range(k):
            tmp *= mn[-i-1]
            tmp %= mod
        print((-tmp) % mod)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
A=[int(i) for i in input().split()]
A.sort()
P=[i for i in A if i<0]
Q=[i for i in A if i>0][::-1]
c=0
S=1
lim = 10**9+7
while c < k:
    if len(P)>1:
        p = P[0]*P[1]
    elif len(P)==1:
        p = P[0]
    else:
        p = 0
    if len(Q)>1:
        q = Q[0]*Q[1]
    elif len(Q)==1:
        q = Q[0]
    else:
        q = 0
    if p<q or c == k-1:
        S*= Q.pop(0)
        S%= lim
        c+=1
    else:
        S*= P.pop(0)
        S%= lim
        S*= P.pop(0)
        S%= lim
        c+=2
print(S)

Submission status: Runtime Error

Solution code:
import copy

n, k = map(int, input().split())
a = list(map(int, input().split()))
d = []
for i in range(n):
    d.append([abs(a[i]), i])
d = sorted(d, reverse=True, key=lambda x: x[0])

b = sorted(a, reverse=True)
frag = True
ans = 1
for i in range(n):
    if(a[i] > 0):
        frag = False
for i in range(k):
    ans *= a[d[i][1]]
    if(ans < 0):
        u = d[k-1][1]
        ans //= u
        j = k
        if(u > 0):
            while(d[j][1] > 0):
                j += 1
        else:
            while(d[j][1] < 0):
                j += 1
            ans *= d[j][1]
MOD = 1000000007

ans = 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

P = []
M = []
zero = 0
for a in A:
    if a > 0:
        P.append(a)
    elif a < 0:
        M.append(a)
    else:
        zero += 1

if len(P) + len(M) < K:
    print(0)
    exit()

P.sort(reverse=True)
M.sort()

if len(P) + zero == N:
    ans = 1
    for k in range(K):
        ans *= P[k]
        ans %= MOD
    print(ans)
    exit()

if len(M) + zero == N:
    ans = 1
    if K % 2 == 0:
        for k in range(K):
            ans *= M[k]
            ans %= MOD
        print(ans)
    else:
        if zero > 0:
            print(0)
        else:
            for k in range(len(M) - 1, len(M) - 1 - K, -1):
                ans *= M[k]
                ans %= MOD
            print(ans)
    exit()


cur_p = 0
cur_m = 0
ans = 1
for k in range(K):
    if cur_p == len(P):
        ans *= M[cur_m]
        cur_m += 1
    elif cur_m == len(M):
        ans *= P[cur_p]
        cur_p += 1
    else:
        if P[cur_p] < abs(M[cur_m]):
            ans *= M[cur_m]
            cur_m += 1
        else:
            ans *= P[cur_p]
            cur_p += 1
    ans %= MOD

if cur_m % 2 == 0:
    print(ans)
else:
    if cur_p == len(P):
        ans *= M[cur_m]
        ans *= pow(P[cur_p - 1], MOD - 2, MOD)
        ans %= MOD
    elif cur_m == len(M):
        ans *= P[cur_p]
        ans *= pow(P[cur_m - 1], MOD - 2, MOD)
        ans %= MOD
    else:
        m1 = M[cur_m - 1]
        p1 = P[cur_p]
        m2 = M[cur_m]
        p2 = P[cur_p - 1]
        if p1 / m1 > m2 / p2:
            ans *= p1
            ans *= pow(m1, MOD - 2, MOD)
            ans %= MOD
        else:
            ans *= m2
            ans *= pow(p2, MOD - 2, MOD)
            ans %= MOD
    print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ap=[]
a0=[]
am=[]
for i in range(n):
    if a[i]>0:
        ap.append(a[i])
    elif a[i]==0:
        a0.append(a[i])
    else:
        am.append(a[i])
ap.sort(reverse=True)
am.sort()
ap2=[]
for i in range(len(ap)//2):
    ap2.append([ap[i*2]*ap[i*2+1],i+1])
am2=[]
for i in range(len(am)//2):
    am2.append([am[i*2]*am[i*2+1],0])
aa3=[]
pc=0
mc=0
while pc<len(ap2) and mc<len(am2):
    if ap2[pc][0]<=am2[mc][0]:
        aa3.append(am2[mc])
        mc+=1
    elif ap2[pc][0]>am2[mc][0]:
        aa3.append(ap2[pc])
        pc+=1
while pc<len(ap2):
    aa3.append(ap2[pc])
    pc+=1
while mc<len(am2):
    aa3.append(am2[mc])
    mc+=1
f=0
ans=1
for i in range(len(aa3)):
    if k>=2:
        ans*=aa3[i][0]
        ans%=(10**9+7)
        k-=2
        if aa3[i][1]!=0:
            f=aa3[1]
    elif k==1:
        if f*2<len(ap):
            ans*=ap[f*2]
            ans%=10**9+7
            k-=1
        else:
            break
    else:
        break
if k==0:
    print(ans%(10**9+7))
else:
    if len(ap)%2==0:
        if len(a0)>0:
            print(0)
        else:
            print((ans*am[len(am)-1])%(10**9+7))
    else:
        ans*=ap[f*2]
        ans%=10**9+7
        k-=1
        if k>0:
            if len(a0)>0:
                print(0)
            else:
                print((ans*am[len(am)-1])%(10**9+7))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
解説PDFを読んでから書き直した。
"""
def main():
    N, K = map(int, input().split())
    A_lsit = list(map(int, input().split()))
    A_lsit_plus = sorted([A for A in A_lsit if A >= 1], reverse=True)
    A_lsit_minus = sorted([-A for A in A_lsit if A <= 0], reverse=True)
    #print(A_lsit_plus)
    #print(A_lsit_minus)
    P = pow(10, 9) + 7

    if len(A_lsit_minus) == N and K%2 == 1:
        product = 1
        for A in A_lsit_minus[:(N-K)-1:-1]:
            product *= A
            if product >= P:
                product = product % P
        print(P-product)
        return
    max_product = 0
    for i in range(K//2 +1):
        if i*2<= len(A_lsit_minus) and K-i*2 <= len(A_lsit_plus):
            product = 1
            for j in range(i*2):
                product *= A_lsit_minus[j]
                if product >= P:
                    product = product % P
            for j in range(K-i*2):
                product *= A_lsit_plus[j]
                if product >= P:
                    product = product % P
        max_product = max(max_product, product)
    print(max_product)
    return

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
from heapq import heappop, heapify, heappush
mod = 10**9 + 7
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
plus = []
minus = []
zero = []
ans = []
for a in A:
    if a > 0:
        plus.append(-a)
    elif a == 0:
        zero.append(a)
    else:
        minus.append(a)
heapify(plus)
heapify(minus)
cnt = 0
last_minus = 0
last_plus = 0
if len(plus) + len(minus) < K:
    print(0)
    sys.exit()

if len(plus) == 0:
    if K%2 == 1:
        print(0)
        sys.exit()
    else:
        num = 1
        minus.sort()
        for x in minus[:K]:
            if x < 0:
                x = -x
            num *= x
            num %= mod
        print(num%mod)
        sys.exit()

if len(minus) == 0:
    num = 1
    plus.sort(reverse=True)
    for x in plus[:K]:
        if x < 0:
            x = -x
        num *= x
        num %= mod
    print(num%mod)
    sys.exit()

flag = 0

for i in range(K):
    if len(plus) > 0 and len(minus) > 0:
        a = heappop(plus)
        b = heappop(minus)
    elif len(plus) == 0:
        flag = 1
        break
    else:
        flag = 2
        break
    if a >= b:
        ans.append(b)
        heappush(plus, a)
        cnt += 1
        last_minus = b
    else:
        ans.append(a)
        heappush(minus, b)
        last_plus = a

if flag == 2:
    for i in range(K - len(ans)):
        a = heappop(plus)
        last_plus = a
        ans.append(a)

if flag == 1:
    for i in range(K - len(ans)):
        a = heappop(minus)
        last_minus = a
        cnt += 1
        ans.append(a)

if cnt%2 == 0:
    num = 1
    for a in ans:
        if a < 0:
            a = -a
        num = (num * a%mod)%mod
    print(num%mod)
    sys.exit()
else:
    num = 1
    ls = []
    for a in ans:
        if a < 0:
            ls.append(-a)
        else:
            ls.append(a)
    if len(plus) == 0:
        c = heappop(minus)
        if c < 0:
            c = -c
        if last_plus < 0:
            last_plus = -last_plus
        ls.remove(last_plus)
        for a in ls:
            if a < 0:
                a = -a
            num = (num * a%mod)%mod
        num = (num * c%mod)%mod
        print(num%mod)
    elif len(minus) == 0:
        c = heappop(plus)
        if c < 0:
            c = -c
        if last_minus < 0:
            last_minus = -last_minus
        ls.remove(last_minus)
        for a in ls:
            if a < 0:
                a = -a
            num = (num * a%mod)%mod
        num = (num * c%mod)%mod
        print(num%mod)
    else:
        a = heappop(plus)
        b = heappop(minus)
        if a < 0:
            a = -a
        if b < 0:
            b = -b
        if last_minus < 0:
            last_minus = -last_minus
        if last_plus < 0:
            last_plus = -last_plus

        if a *last_plus >= b*last_minus:
            ls.remove(last_minus)
            for c in ls:
                num = (num * c%mod)%mod
            num = (num * a%mod)%mod
            print(num%mod)
        else:
            ls.remove(last_plus)
            for c in ls:
                num = (num * c%mod)%mod
            num = (num * b%mod)%mod
            print(num%mod)

Submission status: Runtime Error

Solution code:
"""
    Satwik_Tiwari ;) .
    4th july , 2020  - Saturday
"""

#===============================================================================================
#importing some useful libraries.
from __future__ import division, print_function

from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase


import bisect
from heapq import *
from math import *
from collections import deque
from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
from itertools import combinations as comb # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
from itertools import permutations as permutate
from bisect import bisect_left as bl
#If the element is already present in the list,
# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect
#If the element is already present in the list,
# the right most position where element has to be inserted is returned

#==============================================================================================

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")

#===============================================================================================
#some shortcuts

mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") #for fast input
def out(var): sys.stdout.write(str(var))  #for fast output, always take string
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())
# def graph(vertex): return [[] for i in range(0,vertex+1)]
def zerolist(n): return [0]*n
def nextline(): out("\n")  #as stdout.write always print sring.
def testcase(t):
    for p in range(t):
        solve()
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(a,b):
    ans = 1
    while(b>0):
        if(b%2==1):
            ans*=a
        a*=a
        b//=2
    return ans
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) : # Check Prime Number or not
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True

#===============================================================================================
# code here ;))
def bs(a,l,h,x):
    while(l<h):
        # print(l,h)
        mid = (l+h)//2
        if(a[mid] == x):
            return mid
        if(a[mid] < x):
            l = mid+1
        else:
            h = mid
    return l

def sieve(a): #O(n loglogn) nearly linear
    #all odd mark 1
    for i in range(3,((10**6)+1),2):
        a[i] = 1
    #marking multiples of i form i*i 0. they are nt prime
    for i in range(3,((10**6)+1),2):
        for j in range(i*i,((10**6)+1),i):
            a[j] = 0
    a[2] = 1 #special left case
    return (a)


def bfs(g,st):
    visited = [-1]*(len(g))
    visited[st] = 0
    queue = []
    queue.append(st)
    new = []
    while(len(queue) != 0):
        s = queue.pop()
        new.append(s)
        for i in g[s]:
            if(visited[i] == -1):
                visited[i] = visited[s]+1
                queue.append(i)
    return visited


def dfsusingstack(v,st):
    d = deque([])
    visited = [0]*(len(v))
    d.append(st)
    new = []
    visited[st] = 1
    while(len(d) != 0):
        curr = d.pop()
        new.append(curr)
        for i in v[curr]:
            if(visited[i] == 0):
                visited[i] = 1
                d.append(i)
    return new


def solve():
    n,k =sep()
    a = lis()
    pos= []
    neg = []
    for i in range(n):
        if(a[i]>=0):
            pos.append(a[i])
        else:
            neg.append(a[i])
    pos = sorted(pos)[::-1]
    neg = sorted(neg)[::-1]
    cnt = k
    st1 = 0
    st2 = 0
    ans = 1
    while(cnt>0):
        if(cnt>1):
            if(st1>=len(pos)-1):
                ans = (ans*((neg[st2]*neg[st2+1])%mod))%mod
                st2+=2
                cnt-=2
                continue
            if(st2>=len(neg)-1):
                ans = (ans*((pos[st1]*pos[st1+1])%mod))%mod
                st1+=2
                cnt-=2
                continue

            if(pos[st1]*pos[st1+1] > neg[st2]*neg[st2+1]):
                ans = (ans*((pos[st1]*pos[st1+1])%mod))%mod
                st1+=2
                cnt-=2
            else:
                ans = (ans*((neg[st2]*neg[st2+1])%mod))%mod
                st2+=2
                cnt-=2
        else:
            if(st1>len(pos)-1):
                ans = (ans*neg[st2])%mod
                st2+=1
                cnt-=1
                continue
            ans = (ans*pos[st1])%mod
            st1+=1
            cnt-=1
    print(ans%mod)





testcase(1)
# testcase(int(inp()))

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush
mod = 10**9+7
n, k = map(int, input().split())
a = [int(x) for x in input().split()]


def sgn(x):
    if x > 0:
        return 0
    elif x < 0:
        return 1
    else:
        return 2


pl = []
mn = []
zr = []

for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mn.append(-x)
    else:
        zr.append(x)

pl = sorted(pl, reverse=True)
mn = sorted(mn, reverse=True)


b = [(abs(a[i]), sgn(a[i])) for i in range(n)]
b = sorted(b, reverse=True)

c = [0, 0, 0]
for i in range(k):
    c[b[i][1]] += 1
    if c[2] > 1:
        print(0)
        exit()


def solve(c):
    ans = 1
    for i in range(c[0]):
        ans *= pl[i]
        ans %= mod
    for i in range(c[1]):
        ans *= mn[i]
        ans %= mod
    return ans


if c[1] % 2 == 0:
    print(solve(c))
elif c[0] < len(pl):
    c[0] += 1
    c[1] -= 1
    print(solve(c))
elif 0 < c[0] and c[0] == len(pl) and c[1] < len(mn):
    c[0] -= 1
    c[1] += 1
    print(solve())
elif 0 == c[0] and c[1] < len(mn):
    if len(zr) > 0:
        print(0)
        exit()
    else:
        tmp = 1
        for i in range(k):
            tmp *= mn[-i-1]
            tmp %= mod
        print((-tmp) % mod)

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,K=map(int,input().split())

A=list(map(int,input().split()))
mod=10**9+7
Am=[-i for i in A if i<0]
Ap=[i for i in A if i>=0]

Am.sort()
Ap.sort()
Am=deque(Am)
Ap=deque(Ap)



if N==K:
    c=1
    for a in A:
        c*=a
        c%=mod

elif len(Ap)==0 and K%2:
    c=1
    while K :
        c*=Am.popleft()

        K-=1

        c%=mod
    c=-c
    c%=mod
    #print("unko")

else:
    #print(unko)
    c=1
    h=0
    a="unko"
    b="unko"
    while K and (Am or Ap) :
        if Am and Ap:
            if Am[-1]>Ap[-1]:

                a=Am.pop()
                c*=a
                h+=1
            else:

                b=Ap.pop()
                c*=b

        elif Am:
            a=Am.pop()
            c*=a
            h+=1
        elif Ap:
            b=Ap.pop()
            c*=b
        K-=1
        c%=mod

    if h%2:
        if Am and Ap and a!="unko" and b!="unko":
            if Am[-1]*a>Ap[-1]*b:
                a=Am.pop()
                c*=a
                c*=pow(b,mod-2,mod)
            else:
                b=Ap.pop()
                c*=b
                c*=pow(a,mod-2,mod)
        elif b=="unko":
            a=Am.pop()
            c*=a
            c*=pow(b,mod-2,mod)
        else:
            b=Ap.pop()
            c*=b
            c*=pow(a,mod-2,mod)


print(c%mod)