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:
import sys
input = sys.stdin.readline
from itertools import accumulate
from functools import reduce
from operator import mul
from bisect import bisect_left


def read():
    N, K = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, K, A


def sign(x):
    if x == 0:
        return 0
    if x < 0:
        return -1
    return 1


class ModInt(int):
    
    MOD = 10**9+7

    def __new__(cls, x, *args, **kwargs):
        return super().__new__(cls, x % ModInt.MOD)

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

    def __radd__(self, other):
        return ModInt(super().__radd__(other) % ModInt.MOD)

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

    def __rmul__(self, other):
        return ModInt(super().__rmul__(other) % ModInt.MOD)

    def __pow__(self, other, *args):
        return ModInt(super().__pow__(other, ModInt.MOD))

    def __rpow__(self, other, *args):
        raise NotImplementedError()

    def __truediv__(self, other):
        inv = ModInt(other).inverse()
        return ModInt(super().__mul__(inv) % ModInt.MOD)

    def __floordiv__(self, other):
        return self.__truediv__(other)

    def __rtruediv__(self, other):
        return ModInt(self.inverse().__mul__(other))

    def __rfloordiv__(self, other):
        return self.__rtruediv__(other)

    def _extgcd(self, a, b):
        assert not isinstance(a, ModInt) and not isinstance(b, ModInt)
        if a < b:
            m, y, x = self._extgcd(b, a)
            return (m, x, y)
        if b == 0:
            x = 1
            y = 0
            return (a, x, y)
        m, y, x = self._extgcd(b, a % b)
        y = y - a // b * x
        return (m, x, y)

    def inverse(self):
        a = int(self)
        m = int(ModInt.MOD)
        n, x, y = self._extgcd(a, m)
        if n != 1:
            raise ValueError("{} and {} are not mutually prime.".format(a, m))
        return ModInt(x)


def solve(N, K, A, p=10**9+7):
    A.sort(key=lambda x: abs(x))
    n_zero = 0
    n_minus = 0
    for a in A:
        if a == 0:
            n_zero += 1
        elif a < 0:
            n_minus += 1
    n_plus = N - n_zero - n_minus

    # 全て0以下のとき
    if n_plus == 0:
        # マイナスを偶数個選べる -> それが最大値
        if n_minus >= K and K % 2 == 0:
            base = 1
            for i in range(K):
                base *= A[N-i]
                base %= p
            return base
        elif n_zero > 0:
            return 0
        else:
            base = 1
            for i in range(K):
                base *= A[i]
                base %= p
            return base % p
    # プラスが1つ以上あるとき
    # 0を選ばざるを得ないなら0
    if n_plus + n_minus < K:
        return 0
    # 0を選ばなくて良いとき: A[n_zero:] から選ぶ
    B = A[n_zero:][::-1]
    sn = 1
    base = 1
    r0 = 0
    r1 = 0
    for i in range(K):
        a = B[i]
        if a < 0:
            r0 = i
            r1 = r0
        sn *= sign(a)
        base *= abs(a)
        base %= p
    if sn == 1:
        return base % p
    
    sn = 1
    base = 1
    for i in range(r1+1):
        a = B[i]
        sn *= sign(a)
        base *= abs(a)
        base %= p
    n = K - r1
    i = r1 + 1
    while n > 0:
        if B[i] > 0:
            base *= a
            base %= p
        n -= 1
    return base % p


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Runtime Error

Solution code:
import heapq

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

MOD=10**9+7

ans=1
if L[-1]<=0:#全部負
    if K%2==1:
        #小さい方からKこ
        for l in L[-K:]:
            ans*=l
            ans%=MOD
    else:
        #大きい方からKこ
        for l in L[:K]:
            ans*=l
            ans%=MOD
elif L[0]>=0:#全部生
    for l in L[-K:]:
        ans*=l
        ans%=MOD
else:#生徒ふが入り混じり
    cand=[]
    poss=[]
    negs=[]
    replace=[]
    if K%2==1:#奇数個
        K-=1
        cand.append(L[-1])
        for l in L[:-1]:
            if l>0:
                heapq.heappush(poss,-l)
            else:
                heapq.heappush(negs,l)

    added = len(cand)
    while len(added)<K:
        if len(poss)>=2 and len(negs)>=2:
            pa = -heapq.heappop(poss)
            pb = -heapq.heappop(poss)

            na = heapq.heappop(negs)
            nb = heapq.heappop(negs)
            if pa*pb>na*nb:
                cand.append(pa*pb)
                added+=2
            else:
                cand.append(na*nb)
                added+=2
        elif len(poss)>=2:
            pa = -heapq.heappop(poss)
            pb = -heapq.heappop(poss)
            cand.append(pa*pb)
            added+=2
        if len(negs)>=2:
            na = heapq.heappop(negs)
            nb = heapq.heappop(negs)
            cand.append(na*nb)
            added+=2
        for c in cand:
            ans*=c
            ans%=MOD
print(ans%MOD)

Submission status: Runtime Error

Solution code:
import numpy as np
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:
        negative_min_big = max([num for num in a_list[:k] if np.sign(num)==-1])
        positive_min_big = min([num for num in a_list[:k] if np.sign(num)!=-1])
        negative_max_small = min([num for num in a_list[k:] if np.sign(num)==-1])
        positive_max_small = max([num for num in a_list[k:] if np.sign(num)!=-1])
        if positive_max_small/negative_min_big < negative_max_small/positive_min_big:
            remove = negative_min_big
            add = positive_max_small
        else:
            remove = positive_min_big
            add = negative_max_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:
#!/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):
    ms = []
    ps = []
    zs = []
    for d in data:
        if d > 0:
            ps.append(ModInt(d))
        elif d < 0:
            ms.append(ModInt(d))
        else:
            zs.append(d)
    return list(reversed(sorted(ps))), sorted(ms), zs

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

def solve(data, k):
    ps, ms, zs = mysplit(data)
    #print('ps') # debug
    #print(ps) # debug
    #print('ms') # debug
    #print(ms) # debug
    if len(ps) == 0:
        # small abs
        if len(zs) > 0:
            return 0
        return solve2(ms, k)
    if len(ps) + len(ms) < k:
        return 0
    ans = ModInt(1)
    pk = 0
    mk = 0
    while k > 0:
        if pk + 1 >= len(ps):
            if k % 2 == 0:
                ans *= ms[mk] * ms[mk+1]
                mk += 2
                k -= 2
                continue
            else:
                ans *= ps[pk]
                pk += 1
                k -= 1
                continue
        if mk + 1 < len(ms):
            if ps[pk] * ps[pk + 1] < ms[mk] * ms[mk+1]:
                ans *= ms[mk] * ms[mk+1]
                mk += 2
                k -= 2
                continue
        ans *= ps[pk]
        pk += 1
        k -= 1
        continue
    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 sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

n, k = MI()
mylist = LI()
temp1 = sorted(mylist)
temp2 = sorted(mylist, reverse = True)
mod = 1.0e9 + 7
start = 1
for i in range(k):
    start *= temp1[i]

for i in range(min(n-k,k)):
    s1 = temp1[k-1-i]
    r1 = temp2[i]
    if r1 >= 1:
        break
    if s1 == 0:
        pass
    elif start < start * r1 / s1:
        start =  start * r1 / s1
        
print(int(start % mod))

Submission status: Runtime Error

Solution code:
import numpy as np
n,k = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=True,key=lambda x: abs(x))

def main(n,k,a):
    a = np.array(a)
    if (a<0).all() and k%2==1 : return np.prod(a[-1*k:])
    prod = 1
    for i in range(k-2):
        prod = (prod*a[i])%1000000007

    if prod<0:
        p_flag,n_flag = False,False
        p_done,n_done = False,False
        p,n = 0,0
        for i in range(k-2,len(a)):
            if a[i] > 0 :
                if not p_flag:
                    p = a[i]
                    p_flag =True
                if n_flag and not n_done:
                    n *= a[i]
                    n_done = True
            if a[i] < 0:
                if not n_flag:
                    n = a[i]
                    n_flag =True
                if p_flag and not p_done:
                    p *= a[i]
                    p_done = True
    if prod>0:
        p_flag,n_flag = False,False
        p_done,n_done = False,False
        p,n = 0,0
        for i in range(k-2,len(a)):
            if a[i] > 0 :
                if not p_flag:
                    p = a[i]
                    p_flag =True
                else:
                    p *= a[i]
                    p_done = True
            if a[i] < 0:
                if not n_flag:
                    n = a[i]
                    n_flag =True
                else:
                    n *= a[i]
                    n_done = True
    #print(prod*n,prod*p)
    return max(prod*n,prod*p)

print(main(n,k,a)%1000000007)

Submission status: Runtime Error

Solution code:
n , k = map(int, input().split())
a = list(map(int, input().split()))
neg = []
pos = []
mod = 10**9+7
for i in range(n):
    if a[i] >= 0:
        pos.append(a[i])
    else:
        neg.append(a[i])
neg.sort()
pos.sort(reverse = True)
min_num = -1
good_num = -1
if len(pos) == 0 or n == k:
    ans = 1
    neg.sort(reverse = True)
    for i in range(k):
        ans *= neg[i]
        ans %= mod
    print(ans % mod)
else:
    #最大化するとき
    for i in range(0,k+1,2):
        #i個だけnegから取る。
        if i > len(neg) or k - i > len(pos):
            continue
        m = 0
        if i - 1 >= 0:
            m = abs(neg[i-1])
        if k-i-1 >= 0:
            m = min(m, pos[k-i-1])
        if m > min_num:
            min_num = m
            good_num = i
    ans = 1
    for i in range(good_num):
        ans *= neg[i]
        ans %= mod
    for i in range(k - good_num):
        ans *= pos[i]
        ans %= mod
    print(ans % 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==0 and len(Am)%2==0 or len(Ap)==0 and K%2:
    c=1
    while K and (Am or Ap) :
        if Am and Ap:
            if Am[0]<Ap[0]:
                c*=Am.popleft()
            else:
                c*=Ap.popleft()
        elif Am:
            c*=Am.popleft()
        elif Ap:
            c*=Ap.popleft()
        K-=1
        c=-c
        c%=mod
    #print("unko")

else:
    c=1
    h=0
    w=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==1:
        if Am and Ap and a!="unko" and b!="unko":
            if Am[-1]*pow(b,mod-2,mod)>Ap[-1]*pow(a,mod-2,mod):
                a=Am.pop()
                c*=a
                c*=pow(b,mod-2,mod)
            else:
                b=Ap.pop()
                c*=b
                c*=pow(a,mod-2,mod)
        if Am:
            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)

Submission status: Runtime Error

Solution code:
n , k = map(int, input().split())
a = list(map(int, input().split()))
neg = []
pos = []
mod = 10**9+7
for i in range(n):
    if a[i] >= 0:
        pos.append(a[i])
    else:
        neg.append(a[i])
neg.sort()
pos.sort(reverse = True)
min_num = -1
good_num = -1
if ( k % 2 == 1 and  len(pos) == 0) or n == k:
    ans = 1
    neg.sort(reverse = True)
    for i in range(k):
        ans *= neg[i]
        ans %= mod
    print(ans % mod)
else:
    #最大化するとき
    for i in range(0,k+1,2):
        #i個だけnegから取る。
        if i > len(neg) or k - i > len(pos):
            continue
        m = 0
        if i - 1 >= 0:
            m = abs(neg[i-1])
        if k-i-1 >= 0:
            m = min(m, pos[k-i-1])
        if m > min_num:
            min_num = m
            good_num = i
    ans = 1
    for i in range(good_num):
        ans *= neg[i]
        ans %= mod
    for i in range(k - good_num):
        ans *= pos[i]
        ans %= mod
    print(ans % 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==0 and len(Am)%2==0 or len(Ap)==0 and K%2:
    c=1
    while K and (Am or Ap) :
        if Am and Ap:
            if Am[0]<Ap[0]:
                c*=Am.popleft()
            else:
                c*=Ap.popleft()
        elif Am:
            c*=Am.popleft()
        elif Ap:
            c*=Ap.popleft()
        K-=1
        c=-c
        c%=mod
    #print("unko")

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

                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==1:
        if Am and Ap and a!="unko" and b!="unko":
            if Am[-1]*pow(b,mod-2,mod)>Ap[-1]*pow(a,mod-2,mod):
                a=Am.pop()
                c*=a
                c*=pow(b,mod-2,mod)
            else:
                b=Ap.pop()
                c*=b
                c*=pow(a,mod-2,mod)
        if Am:
            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)

Submission status: Runtime Error

Solution code:
import sys
n,k=map(int,input().split())
a = list(map(int,input().split()))
plus = sorted([i for i in a if i > 0],reverse=True)
minus = sorted([i for i in a if i < 0])
b = []
p = 0
m = 0
MOD = 10**9 + 7

while(True):
    if(p == len(plus)):
        for i in range(k-p-m):
            b.append(minus[i+m])
        break
    if(m == len(minus)):
        for i in range(k-p-m):
            b.append(plus[i+p])
        break
    if(plus[p] >= -minus[m]):
        b.append(plus[p])
        p += 1
    else:
        b.append(minus[m])
        m += 1
    if(p+m == k):
        if(m % 2 == 1):
            if(minus[m]*minus[m-1] > plus[p]*plus[p-1]):
                b[b.index(plus[p-1])] = minus[m]
            else:
                b[b.index(minus[m-1])] = plus[p]
        break
if(len([i for i in b if i<0]) %2 != 0):
    if(0 in a):
        print(0)
        sys.exit()
    else:
        ans = 1
        for i in a:
            if(i < 0):
                i *= -1
        a = sorted(a,reverse=True)
        for i in range(k):
            ans = ans*a[i] % MOD
        ans = -((-1 * ans) % -MOD)
        print(ans)
        sys.exit()
ans = 1
for i in b:
    ans = ans*i % MOD
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    A = sorted([int(x) for x in input().strip().split()])
    zeros = A.count(0)
    minus = len([a for a in A if a < 0])
    plus = N - zeros - minus
    max_A = max(A)
    mod = 10 ** 9 + 7
    ans = 1
    if N == K:
        ans = 1
        for k in range(K):
            ans = (ans * A[k]) % mod
        print(ans)
        return
    if max_A < 0:
        if K % 2:
            for k in range(K):
                ans = (ans * A[-1-k]) % mod
            print(ans)
            return
        else:
            for k in range(K):
                ans = (ans * A[k]) % mod
            print(ans)
            return
    elif max_A == 0:
        if A[K-1] == 0:
            print(0)
            return
        else:
            if len([a for a in A if a < 0]) % 2:
                print(0)
                return
            else:
                ind = A.index(0)
                for k in range(K):
                    ans = (ans * A[ind-k-1]) % mod
                print(ans)
                return
    else:
        if N - zeros < K:
            print(0)
            return
        if N - zeros == K:
            if len([a for a in A if a < 0]) % 2:
                print(0)
                return
            else:
                for a in A:
                    if a != 0:
                        ans = (ans * a) % mod
                print(ans)
                return
        A.sort(key=lambda x: abs(x), reverse=True)
        minus = 0
        for k in range(K):
            if A[k] < 0:
                minus += 1
                minus_last_index = k
            ans = (ans * A[k]) % mod
        if minus % 2:
            for k in range(minus_last_index):
                ans = (ans * A[k]) % mod
            k = minus_last_index + 2
            k2 = k
            while k2 < K:
                if A[k] >= 0:
                    ans = (ans * A[k]) % mod
                    k += 1
                    K2 = k
                else:
                    k += 1

        print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#関数リスト
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

n, k = MI()
mylist = LI()
temp1 = sorted(mylist)
temp2 = sorted(mylist, reverse = True)
mod = 1.0e9 + 7
start = 1
for i in range(k):
    start *= temp1[i]

for i in range(k):
    s1 = temp1[k-1-i]
    r1 = temp2[i]
    if r1 >= 1:
        break
    if s1 == 0:
        pass
    elif start < start * r1 / s1:
        start =  start * r1 / s1
        
print(int(start % mod))

Submission status: Runtime Error

Solution code:
from collections import deque
# N = int(input())
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
MOD = 10 ** 9 + 7
A_p = []
A_n = []
for a in A:
  if a >= 0:
    A_p.append(a)
  else:
    A_n.append(-a)

A_p.sort(reverse=True)
A_n.sort(reverse=True)
A_p = deque(A_p)
A_n = deque(A_n)

p_top = 0
n_top = 0
ans_p = deque([])
ans_n = deque([])
for i in range(K):
  if len(A_p) == 0:
    ans_n.append(A_n.popleft())
  elif len(A_n) == 0:
    ans_p.append(A_p.popleft())
  elif A_p[0] >= A_n[0]:
    ans_p.append(A_p.popleft())
  else:
    ans_n.append(A_n.popleft())
if len(ans_n) % 2 == 1:
  if len(ans_p) == 0 and len(A_p) > 0:
    ans_n.pop()
    ans_p.append(A_p.popleft())
  elif len(ans_n) == 0 and len(A_n) > 0:
    ans_p.pop()
    ans_n.append(A_n.popleft())
  elif len(ans_p) > 0 and len(ans_n) > 0 and ans_p[-1] >= ans_n[-1] and len(A_p) > 0:
    ans_n.pop()
    ans_p.append(A_p.popleft())
  elif len(ans_p) > 0 and len(ans_n) > 0 and ans_p[-1] < ans_n[-1] and len(A_n) > 0:
    ans_p.pop()
    ans_n.append(A_n.popleft())
ans = 1
for a in ans_p:
  ans = (a * ans) % MOD
for a in ans_n:
  ans = (a * ans) % MOD
if ans != 0 and len(ans_n) % 2 == 1:
  ans = 1
  A = [a for a in A if a < 0]
  A.sort(reverse=True)
  for i in range(K):
    ans = (ans * A[i]) % MOD
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    a.sort(key=abs, reverse=True)
    ans = 1
    t = 0
    L = 0
    R= 0
    for ai in a[:k]:
        if ai < 0:
            t ^= 1
            L = ai
        if ai > 0:
            R = ai
        ans *= ai
        ans %= mod
    if t:
        if len(a) >= k:
            A = min(a[k:])
            B = max(a[k:])
            if A >= 0:
                ans *= pow(L, mod - 2, mod)
                ans *= B
            else:
                if A * L > B * R:
                    ans *= pow(R, mod - 2, mod)
                    ans *= A
                else:
                    ans *= pow(L, mod - 2, mod)
                    ans *= B
            print(ans%mod)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

if arr[-1] == 0 and k % 2:
	print(0)
else:
	if arr[-1] < 0 and k % 2:
		p = 1
		while k:
			p = (p * arr[n - 1]) % m
			k -= 1
			n -= 1
		print(p)
	else:
		neg = []
		pos = []
		for i in arr:
			if i < 0:
				neg += [abs(i)]
			else:
				pos += [i]
		
		if arr[-1] > 0 and k % 2:
			arr2 = neg + pos[:-1]
			arr2.sort()
			p = 1
			while k > 1:
				p = (p * abs(arr2[n - 1])) % m
				k -= 1
				n -= 1
			print((p * pos[-1]) % m)
		else:
			arr2 = neg + pos
			arr2.sort()
			p = 1
			while k:
				p = (p * abs(arr2[n - 1])) % m
				k -= 1
				n -= 1
			print(p)

Submission status: Runtime Error

Solution code:
n , k = map(int, input().split())
a = list(map(int, input().split()))
neg = []
pos = []
mod = 10**9+7
for i in range(n):
    if a[i] >= 0:
        pos.append(a[i])
    else:
        neg.append(a[i])
neg.sort()
pos.sort(reverse = True)
min_num = -1
good_num = -1
if k % 2 == 1 and len(pos) == 0 and n == k:
    ans = 1
    neg.sort(reverse = True)
    for i in range(k):
        ans *= neg[i]
        ans %= mod
    print(ans % mod)
else:
    #最大化するとき
    for i in range(0,k+1,2):
        #i個だけnegから取る。
        if i > len(neg) or k - i > len(pos):
            continue
        m = 0
        if i - 1 >= 0:
            m = abs(neg[i-1])
        if k-i-1 >= 0:
            m = min(m, pos[k-i-1])
        if m > min_num:
            min_num = m
            good_num = i
    ans = 1
    for i in range(good_num):
        ans *= neg[i]
        ans %= mod
    for i in range(k - good_num):
        ans *= pos[i]
        ans %= mod
    print(ans % mod)

Submission status: Runtime Error

Solution code:
## coding: UTF-8
N, K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 10**9 + 7

B = []
for i in range(N):
    B.append([abs(A[i]), A[i], A[i]//abs(A[i])])
#print(B)
B = sorted(B, reverse = True)
#print(B)

minus_count = 0
for i in range(K):
    if(B[i][2] == -1):
        minus_count += 1


all_minus = True
for i in range(N):
    if(B[i][2] == 1):
        all_minus = False

if(minus_count % 2 == 0):
    ans = 1
    for i in range(K):
        ans *= B[i][0]
        ans %= MOD
    print(ans)
elif(all_minus):
    C = sorted(B)
    #print(C)
    ans = 1
    for i in range(K):
        ans *= C[i][1]
        ans %= MOD
    print(ans)
else:
    #last plus -> minus
    C = B[:K]
    #print(C)
    for i in range(K-1, -1,-1):
        if(C[i][2] == 1):
            last_plus = C[i]
            del C[i]
            break
    search_minus = True
    index = K
    while search_minus:
        if(B[index][2] == -1):
            search_minus = False
            first_minus = B[index]
            C.append(first_minus)
        index += 1
    #print(first_minus, last_plus, C)
    A_ans = 1
    A_kiroku = last_plus[0] / first_minus[0] #割った数（これが小さい方が積が大きいはず）
    for i in range(K):
        A_ans *= C[i][1]
        A_ans %= MOD

    C = B[:K]    
    for i in range(K-1, -1,-1):
        if(C[i][2] == -1):
            last_minus = C[i]
            del C[i]
            break
    search_plus = True
    index = K
    while search_plus:
        if(B[index][2] == 1):
            search_plus = False
            first_plus = B[index]
            C.append(first_plus)
        index += 1
    #print(first_minus, last_plus, C)
    B_ans = 1
    B_kiroku = last_minus[0] / first_plus[0]
    for i in range(K):
        B_ans *= C[i][1]
        B_ans %= MOD
    
    #print(A_ans, B_ans)
    #print(last_plus, first_minus, A_kiroku)
    #print(last_minus, first_plus, B_kiroku)
    if(A_kiroku > B_kiroku):
        print(B_ans)
    else:
        print(A_ans)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    A = sorted([int(x) for x in input().strip().split()])
    zeros = A.count(0)
    minus = len([a for a in A if a < 0])
    plus = N - zeros - minus
    max_A = max(A)
    mod = 10 ** 9 + 7
    if N == K:
        ans = 1
        for k in range(K):
            ans = (ans * A[k]) % mod
        print(ans)
        return
    if max_A < 0:
        if K % 2:
            ans = 1
            for k in range(K):
                ans = (ans * A[-1-k]) % mod
            print(ans)
            return
        else:
            ans = 1
            for k in range(K):
                ans = (ans * A[k]) % mod
            print(ans)
            return
    elif max_A == 0:
        if A[K-1] == 0:
            print(0)
            return
        else:
            if len([a for a in A if a < 0]) % 2:
                print(0)
                return
            else:
                ind = A.index(0)
                for k in range(K):
                    ans = (ans * A[ind-k-1]) % mod
                print(ans)
                return
    else:
        if N - zeros < K:
            print(0)
            return
        if N - zeros == K:
            if len([a for a in A if a < 0]) % 2:
                print(0)
                return
            else:
                ans = 1
                for a in A:
                    if a != 0:
                        ans = (ans * a) % mod
                print(ans)
                return
        ans = 1
        A.sort(key=lambda x: abs(x), reverse=True)
        minus = 0
        for k in range(K):
            if A[k] < 0:
                minus += 1
                minus_last_index = k
            ans = (ans * A[k]) % mod
        if minus % 2:
            for k in range(minus_last_index):
                ans = (ans * A[k]) % mod
            k = minus_last_index + 2
            k2 = k
            while k2 < K:
                if A[k] >= 0:
                    ans = (ans * A[k]) % mod
                    k += 1
                    K2 = k
                else:
                    k += 1

        print(ans)

if __name__ == '__main__':
    main()