Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

We will choose exactly K of these elements. Find the maximum possible product of the chosen elements.

Then, print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Constraints

1 \leq K \leq N \leq 2\times 10^5

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

Print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

The possible products of the two chosen elements are 2, -3, -4, -6, -8, and 12, so the maximum product is 12.

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

The possible products of the three chosen elements are -24, -12, -8, and -6, so the maximum product is -6.

We print this value modulo (10^9+7), that is, 1000000001.

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

The possible products of the one chosen element are -1 and 1000000000, so the maximum product is 1000000000.

Sample Input 4

10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1

Sample Output 4

999983200

Be sure to print the product modulo (10^9+7).



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Accepted

Solution code:
# template by 3xC and starkizard.
# contributors: 

#####################################################################################
from __future__ import division, print_function 

import sys
import os
from collections import Counter, deque, defaultdict
import itertools
import math
import io


"""Uncomment modules according to your need"""


# from bisect import bisect_left, bisect_right, insort
# from heapq import heappop, heapify, heappush
# from random import randint as rn
# from Queue import Queue as Q
# from copy import deepcopy
# from decimal import *
# import re
# import operator

#####################################################################################
# this enables you to write python3 code with PyPy2 (Python 2)
if sys.version_info[0] < 3:
    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip

#####################################################################################

"""value of mod"""
MOD = 998244353
mod = 10**9 + 7

"""Uncomment next 4 lines if doing huge recursion"""
# import threading
# threading.stack_size(1<<27)
# sys.setrecursionlimit(10000)

def prepare_factorial(mod=mod):
    """ returns two lists, factorial and inverse factorial modulo argument by default 10**9 +7 """
    # Comment code out when you don't need inverse factorial or vice versa
    fact = [1]
    for i in range(1, 200005):
        fact.append((fact[-1] * i) % mod)

    ifact = [0] * 200005
    ifact[200004] = pow(fact[200004], mod - 2, mod)
    for i in range(200004, 0, -1):
        ifact[i - 1] = (i * ifact[i]) % mod

    return fact, ifact

def modinv(n, p):
    """ returns N inverse modulo p """
    return pow(n, p - 2, p)

def ncr(n, r,  fact, ifact,MOD=mod):
    """ takes 4 arguments: n , r and factorial and inverse factorial lists"""
    t = (fact[n] * (ifact[r]*ifact[n-r]) % MOD)% MOD
    return t


def get_n(Sum):    
    """this function returns the maximum n for which Summation(n) <= Sum"""
    ans = (-1 + sqrt(1 + 8*Sum))//2
    return ans

def sieve(n):
    """ returns a list of prime numbers till n """
    if n < 2: return list()
    prime = [True for _ in range(n + 1)]
    p = 3
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 2
    r = [2]
    for p in range(3, n + 1, 2):
        if prime[p]:
            r.append(p)
    return r



def divs(n, start=1):
    """ returns a list of all divisors till n """
    divisors = []
    #rdivisors=[]
    for i in range(start, int(math.sqrt(n) + 1)):
        if n % i == 0:
            if n / i == i:
                divisors.append(i)
            else:
                divisors.extend([i, n // i])
    return divisors



def divn(n, primes):
    """ returns the number of divisors, two arguments n and the sieve till n """
    divs_number = 1
    for i in primes:
        if n == 1:
            return divs_number
        t = 1
        while n % i == 0:
            t += 1
            n //= i
        divs_number *= t
    return divs_number


def lrfind(d, x, default=-1):
    """ Takes 2 arguments an iterable and an element. returns a tuple (firstoccurence,lastoccurence) -1 if not found """
    left = right = -1
    for i in range(len(d)):
        if d[i] == x:
            if left == -1: left = i
            right = i
    if left == -1:
        return default, default
    else:
        return left, right

def gcd(x, y): # math.gcd is slower
    """ returns greatest common divisor of x and y """
    while y:
        x, y = y, x % y
    return x

def check_sorted(a):
    ''' returns True/False '''
    for i in range(len(a)-1):
        if a[i]>a[i+1]:
            return False
    return True

def print_arr2d(a):
    for i in a:
        prr(i)
    
def ceil(n, k=1): return n // k + (n % k != 0) #returns math.ceil but protecting against floating inconsistencies
def input(): return sys.stdin.readline().strip()
def ii(): return int(input()) #inputs integer
def mi(): return map(int, input().split()) # inputting space seperated variables for example x,y,z
def li(): return list(map(int, input().split())) #inputting a space seperated list of integers
def lw(): return input().split() #inputting a space seperated list of strings
def lcm(a, b): return abs(a * b) // gcd(a, b) #returns LCM of two arguments
def prr(a, sep=' ', end='\n'): print(sep.join(map(str, a)), end=end) #For printing an iterable with seperator sep as optional second argument (default : " "), ending character (default: "\n") as optional third
def dd(): return defaultdict(int) #returns a dictionary with values defaulted to 0
def ddl(): return defaultdict(list) #returns a dictionary with values defaulted to []
def write(s): return sys.stdout.write(s)












###################################################################
# code goes here
def main(): 
    n,k=mi()
    a=li()
    a.sort()
    product=1
    if(a[-1]==0 and k&1):
        print(0)
        return
    if(a[-1]<0 and (k&1)):
        pointer=n-1
        count=0
        while(pointer>-1):
            product=(product*a[pointer])%mod
            pointer-=1
            count+=1
            if count==k:
                break
        print(product%mod)
        return
    lpointer=0
    rpointer=n-1
    if(k&1):
        product*=a[-1]
        rpointer-=1
        k-=1
    pairs=k//2
    for i in range(pairs):
        lproduct=a[lpointer]*a[lpointer+1]
        rproduct=a[rpointer]*a[rpointer-1]
        if(lproduct>rproduct):
            product=(product*lproduct)%mod
            lpointer+=2
        else:
            product=(product*rproduct)%mod
            rpointer-=2
    print(product%mod)
        


                

                    




        
    
        
        
    


            


            
                
            

            



                






        
        


    
    
                

    

""" -------- Python 2 and 3 footer by Pajenegod and c1729 ---------"""

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192

class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO, self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill();
            self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

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


class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            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')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')
# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

""" main function"""

if __name__ == '__main__':
    main()
    #threading.Thread(target=main).start()

Submission status: Accepted

Solution code:
def mergesort(l):
    n = len(l)
    if(n == 0):
        return 0
    elif(n == 1):
        return l
    elif(n <= 2):
        if(l[0] > l[1]):
            return [l[1],l[0]]
        else:
            return l
    else:
        tmp1 = mergesort(l[:n//2])
        tmp2 = mergesort(l[n//2:])
        x = n//2
        y = n-x
        l = []
        for i in range(n):
            if(tmp1[-x] < tmp2[-y]):
                l.append(tmp1[-x])
                x -= 1
            else:
                l.append(tmp2[-y])
                y -= 1
            if(x*y == 0):
                if(x == 0):
                    l += tmp2[-y:]
                else:
                    l += tmp1[-x:]
                break
        return l
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = []
c = []
s,t,u = 0,0,0
for i in range(n):
    if(a[i] < 0):
        t += 1
        c.append(a[i])
    else:
        s += 1
        b.append(a[i])
b = mergesort(b)
c = mergesort(c)
p = 1
if(s == 0 and k%2 == 1):
    for i in range(1,k+1):
        p *= c[-i]
        p %= 1000000007
else:
    if(n == k):
        for i in range(n):
            p *= a[i]
            p %= 1000000007
    else:
        if(k%2 == 1):
            s-=1
            p = b[s]
            k -= 1
        while(k>0):
            if(s >= 2 and t >= u+2):
                if(b[s-1]*b[s-2] > c[u]*c[u+1]):
                    p *= b[s-1]*b[s-2]
                    p %= 1000000007
                    s -= 2
                else:
                    p *= c[u]*c[u+1]
                    p %= 1000000007
                    u += 2
            elif(s <= 1):
                p *= c[u]*c[u+1]
                p %= 1000000007
                u += 2
            else:
                p *= b[s-1]*b[s-2]
                p %= 1000000007
                s -= 2
            k -= 2
print(p)

Submission status: Accepted

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) and p < len(P):
        Ans.append(P[p])
        if len(Ans) == K:
            break
        if p + 1 < len(P):
            Ans.append(P[p + 1])
            p += 2
        else:
            p += 1
        
    elif p+1 >= len(P) and m < len(M):
        Ans.append(M[m])
        if len(Ans) == K:
            break
        Ans.append(M[m + 1])
        m += 2
    elif m >= len(M) and p < len(P):
        Ans.append(P[p])
        p += 1
    elif p >= len(P) and m < len(M):
        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: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    import bisect

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

    neg = bisect.bisect_left(a, 0)
    zer = bisect.bisect_right(a, 0) - neg
    pos = n - (neg + zer)

    a_neg = a[:neg]
    a_pos = a[-pos:] if pos > 0 else []
    a_pos.sort(reverse=True)

    ans = 0
    flag = False
    
    if k == n:
        ans = 1
        for x in a:
            ans *= x
            ans %= MOD
        print(ans)
        sys.exit()

    if k % 2 == 0:
        a2 = []
        for i in range(0, pos - 1, 2):
            a2.append(a_pos[i] * a_pos[i + 1])
        for i in range(0, neg - 1, 2):
            a2.append(a_neg[i] * a_neg[i + 1])
        a2.sort(reverse=True)
        if len(a2) * 2 >= k:
            flag = True
            ans = 1
            for i in range(k // 2):
                ans *= a2[i]
                ans %= MOD
    else:
        a2 = []
        for i in range(1, pos - 1, 2):
            a2.append(a_pos[i] * a_pos[i + 1])
        for i in range(0, neg - 1, 2):
            a2.append(a_neg[i] * a_neg[i + 1])
        a2.sort(reverse=True)
        if pos > 0 and len(a2) * 2 + 1 >= k:
            flag = True
            ans = a_pos[0]
            for i in range(k // 2):
                ans *= a2[i]
                ans %= MOD

    if not flag:
        if zer > 0:
            ans = 0
        elif k % 2 == 0:
            b2 = []
            a_pos.sort()
            a_neg.sort(reverse=True)

            for i in range(1, neg - 1, 2):
                b2.append(a_neg[i] * a_neg[i + 1])
            for i in range(1, pos - 1, 2):
                b2.append(a_pos[i] * a_pos[i + 1])
            b2.sort()
            if len(b2) * 2 + 2 >= k:
                ans = a_pos[0] * a_neg[0]
                for i in range(k // 2):
                    ans *= b2[i]
                    ans %= MOD
        else:
            b2 = []
            a_pos.sort()
            a_neg.sort(reverse=True)
            for i in range(1, neg - 1, 2):
                b2.append(a_neg[i] * a_neg[i + 1])
            for i in range(0, pos - 1, 2):
                b2.append(a_pos[i] * a_pos[i + 1])
            b2.sort()
            if neg > 0 and len(b2) * 2 + 1 >= k:
                ans = a_neg[0]
                for i in range(k // 2):
                    ans *= b2[i]
                    ans %= MOD

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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:
    ww = negative[0]
    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:
    w = positive[0]
    positive = positive[1:]
while positive:
    check.append(positive.pop() * positive.pop())
check.sort()


for i in range(k//2):
    if check:
        ans *= check.pop()
    else:
        print(ans*w*ww%mod)
        exit()
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
p=[]
m=[]
z=0
a.sort(reverse=True)
for i in range(n):
    if a[i]>0:
        p.append(a[i])
    elif a[i]==0:
        z+=1
    else:
        m.append(a[i])
nump=len(p)
numm=len(m)
ans=1
if nump+numm<k:
    print(0)
elif numm<2 and nump>=k:
    for i in range(k):
        ans*=p[i]
        ans%=10**9+7
    print(ans)
elif 2*(numm//2)+nump<k: #2
    if z!=0:
        print(0)
    else:
        for i in range(n):
            a[i]=abs(a[i])
        a.sort()
        ans=-1
        for i in range(k):
            ans*=a[i]
            ans%=10**9+7
        print(ans)
elif  nump==0: #8?
    if z!=0 and k%2==1:
        print(0)
    elif z!=0 and numm<k:
        print(0)
    else:
        if k%2==0:
            m.sort()
            for i in range(k):
                ans*=m[i]
                ans%=10**9+7
        else:
            m.sort(reverse=True)
            for i in range(k):
                ans*=m[i]
                ans%=10**9+7
        print(ans)
else:
    if k%2==1:
        ans*=p[0]
        p=p[1:]
    m.sort()
    p.sort(reverse=True)
    nump=len(p)//2
    numm=numm//2
    nump1=0
    nump2=0
    numm1=0
    numm2=0
    for i in range(k//2):
        if nump2==nump:
            nump1=-1
        else:
            nump1=p[nump2*2]*p[nump2*2+1]
        if numm2==numm:
            numm1=-1
        else:
            numm1=m[numm2*2]*m[numm2*2+1]
        if numm1>=nump1:
            num=numm1
            numm2+=1
        else:
            num=nump1
            nump2+=1
        ans*=num
        ans%=10**9+7
    print(ans)

Submission status: Accepted

Solution code:
mod = 1000000007

def sgn(v):
    return (v > 0) - (v < 0)

def solve():
    v.sort(key=abs, reverse=True)
    res = 1
    flag = 1
    for i in range(k):
        res *= v[i]
        res %= mod
        flag *= sgn(v[i])
    if flag >= 0:
        return res
    if max(v) <= 0:
        res = 1
        for i in range(-k, 0, 1):
            res *= v[i]
            res %= mod
        return res

    def get(comp):
        i = k - 1
        while i >= 0 and comp(v[i]):
          i -= 1
        j = k
        while j < n and not comp(v[j]):
          j += 1
        if j == n: j = i
        return i, j
      
    i, j = get(lambda w: w >= 0)
    i2, j2 = get(lambda w: w <= 0)
    if i2 >= 0 and v[j] * v[i2] < v[i] * v[j2]:
        i = i2
        j = j2

    res = v[j]
    for a in range(k):
        if a != i:
            res *= v[a]
            res %= mod
    return res

n, k = map(int, input().split(" "))
v = list(map(int, input().split(" ")))
print (solve())

Submission status: Accepted

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

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, K, XS):
    "void()"

    posi = [x for x in XS if x >= 0]
    nega = [x for x in XS if x < 0]

    nega.sort(reverse=True)
    posi.sort()

    if K == N:
        # no choice
        ret = 1
        for i in range(N):
            ret *= XS[i]
            ret %= MOD
        return ret

    if not posi and K % 2:
        # negative answer
        # find smallest abs
        ret = 1
        for i in range(K):
            ret *= nega[i]
            ret %= MOD
        return ret

    ret = 1
    while K:
        # debug(": K, nega, posi", K, nega, posi)
        if K >= 2:
            if len(posi) >= 2:
                v = posi[-1] * posi[-2]
                if len(nega) >= 2:
                    w = nega[-1] * nega[-2]
                else:
                    w = -INF
                if v > w:
                    posi.pop()
                    posi.pop()
                    ret *= v
                    ret %= MOD
                else:
                    nega.pop()
                    nega.pop()
                    ret *= w
                    ret %= MOD

            else:
                w = nega[-1] * nega[-2]
                nega.pop()
                nega.pop()
                ret *= w
                ret %= MOD

            K -= 2
        else:
            if posi:
                ret *= posi[-1]
                ret %= MOD
            else:
                ret *= nega[0]
                ret %= MOD
            K -= 1
    return ret


def main():
    N, K = map(int, input().split())
    XS = list(map(int, input().split()))
    print(solve(N, K, XS))


T1 = """
4 2
1 2 -3 -4
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    12
    """


T2 = """
4 3
-1 -2 -3 -4
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    1000000001
    """


T3 = """
2 1
-1 1000000000
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    1000000000
    """


T4 = """
10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    999983200
    """


def _test():
    import doctest
    doctest.testmod()


T5 = """
3 2
1 1 -1
"""


def test_T5():
    """
    >>> as_input(T5)
    >>> main()
    1
    """


T6 = """
3 2
1 -1 -1
"""


def test_T6():
    """
    >>> as_input(T6)
    >>> main()
    1
    """


T7 = """
3 2
2 -1 -1
"""


def test_T7():
    """
    >>> as_input(T7)
    >>> main()
    1
    """


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
P=[]
Z=[]
N=[]
for i in range(n):
  if a[i]>0:
    P.append(a[i])
  elif a[i]==0:
    Z.append(a[i])
  else:
    N.append(-a[i])
P.sort()
P3=[1]
for i in range(len(P)):
  P3.append(P3[-1]*P[i]%mod)
P.reverse()
P2=[1]
for i in range(len(P)):
  P2.append(P2[-1]*P[i]%mod)
N.sort()
N3=[1]
for i in range(len(N)):
  N3.append(N3[-1]*N[i]%mod)
N.reverse()
N2=[1]
for i in range(len(N)):
  N2.append(N2[-1]*N[i]%mod)

if n==k:
  ans=1
  for i in range(n):
    ans*=a[i]
    ans%=mod
  print(ans%mod)
  exit()

if k==1:
  print(max(a)%mod)
  exit()

if len(P)+len(N)<k:
  print(0)
  exit()

if len(N)==0:
  print(P2[k]%mod)
  exit()

if len(P)+len(N)==k:
  if len(N)%2==0:
    print(P2[-1]*N2[-1]%mod)
    exit()
  else:
    if len(Z)!=0:
      print(0)
    else:
      print(-P2[-1]*N2[-1]%mod)
    exit()

if k%2==0:
  ans=1
  xp=0
  xn=0
  for i in range(k//2):
    if xp+1<len(P):
      xa=P[xp]*P[xp+1]
    else:
      xa=1
    if xn+1<len(N):
      xb=N[xn]*N[xn+1]
    else:
      xb=1
    if xa<=xb:
      xn+=2
      ans*=xb
      ans%=mod
    else:
      xp+=2
      ans*=xa
      ans%=mod
  print(ans%mod)

else:
  ans=1
  xp=0
  xn=0
  ctP=0
  ctN=0
  for i in range(k//2):
    if xp+1<len(P):
      xa=P[xp]*P[xp+1]
    else:
      xa=1
    if xn+1<len(N):
      xb=N[xn]*N[xn+1]
    else:
      xb=1
    if xa<=xb:
      xn+=2
      ans*=xb
      ans%=mod
      ctN+=1
    else:
      xp+=2
      ans*=xa
      ans%=mod
      ctP+=1
  if ctP*2+1<=len(P):
    ans*=P[ctP*2]
    ans%=mod
    print(ans%mod)
  else:
    N.reverse()
    P.reverse()
    ans=1
    xp=0
    xn=0
    ctP=0
    ctN=0
    for i in range(k//2):
      if xp+1<len(P):
        xa=P[xp]*P[xp+1]
      else:
        xa=0
      if xn+1<len(N):
        xb=N[xn]*N[xn+1]
      else:
        xb=0
      if xa<=xb:
        xn+=2
        ans*=xb
        ans%=mod
        ctN+=1
      else:
        xp+=2
        ans*=xa
        ans%=mod
        ctP+=1
    ans*=N[ctN*2]
    ans%=mod
    if len(Z)!=0:
      print(0)
    else:
      print(-ans%mod)

Submission status: Accepted

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

Solution code:
MOD = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
am = []
ap = []
for ai in a:
    if ai > 0:
        ap.append(ai)
    elif ai < 0:
        am.append(-ai)
am.sort(reverse=True)
ap.sort(reverse=True)

nm = len(am)
np = len(ap)
nz = n - np - nm
# print(am)
# print(ap)

if np + nm < k:
    ans = 0
elif np == 0:
    if k % 2 == 1:
        if nz > 0:
            ans = 0
        else:
            am.sort()
            ans = -1 + MOD
            for i in range(k):
                ans *= am[i]
                ans %= MOD
    else:
        ans = 1
        for i in range(k):
            ans *= am[i]
            ans %= MOD
elif np < k:
    if (k - np) % 2 == 1:
        idx1 = np - 1
        idx2 = k - np + 1
        if k - np + 1 > nm:
            if nz > 0:
                ans = 0
            else:
                if nm % 2 == 1:
                    ans = -1 + MOD
                else:
                    ans = 1
                for i in range(np):
                    ans *= ap[i]
                    ans %= MOD
                for i in range(nm):
                    ans *= am[i]
                    ans %= MOD
        else:
            while idx1 >= 2 and idx2 + 1 < nm and \
                ap[idx1 - 1] * ap[idx1 - 2] < am[idx2] * am[idx2 + 1]:
                idx1 -= 2
                idx2 += 2
            ans = 1
            for i in range(idx1):
                ans *= ap[i]
                ans %= MOD
            for i in range(idx2):
                ans *= am[i]
                ans %= MOD
    else:
        idx1 = np
        idx2 = k - np
        while idx1 >= 2 and idx2 + 1 < nm and \
            ap[idx1 - 1] * ap[idx1 - 2] < am[idx2] * am[idx2 + 1]:
            idx1 -= 2
            idx2 += 2
        ans = 1
        for i in range(idx1):
            ans *= ap[i]
            ans %= MOD
        for i in range(idx2):
            ans *= am[i]
            ans %= MOD
else:
    idx1 = k
    idx2 = 0
    while idx1 >= 2 and idx2 + 1 < nm and \
        ap[idx1 - 1] * ap[idx1 - 2] < am[idx2] * am[idx2 + 1]:
        idx1 -= 2
        idx2 += 2
    ans = 1
    for i in range(idx1):
        ans *= ap[i]
        ans %= MOD
    for i in range(idx2):
        ans *= am[i]
        ans %= MOD

print(ans)