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: Wrong Answer

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>0):
            product=(product*a[pointer])%mod
            pointer-=1
            count+=1
            if count==k:
                break
        print(int(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(int(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: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from functools import total_ordering

MOD = 1000000007  # type: int


def solve(N: int, K: int, A: "List[int]"):
    B = [Num(A[i]) for i in range(N)]
    B.sort(reverse=True)
    sign = 1
    ret = 1
    for i in range(K):
        sign *= B[i].getSign()
        ret *= B[i].getNum() % MOD
        ret %= MOD
    if sign > 0:
        print(ret)
        return
    elif sign < 0:
        minP = -1
        minP_i = 0
        minM = 1
        minM_i = 0
        for i in range(K - 1, -1, -1):
            if B[i].getSign() > 0:
                minP = B[i].getNum()
                minP_i = i
                break
        else:
            minP = 10 ** 10
        for i in range(K - 1, -1, -1):
            if B[i].getSign() < 0:
                minM = B[i].getNum()
                minM_i = i
                break
        else:
            minM = 10 ** 10
        maxP = -1
        maxP_i = 0
        maxM = 1
        maxM_i = 0
        for i in range(K, N):
            if B[i].getSign() > 0:
                maxP = B[i].getNum()
                maxP_i = i
                break
        else:
            maxP = 0
        for i in range(K, N):
            if B[i].getSign() < 0:
                maxM = B[i].getNum()
                maxM_i = i
                break
        else:
            maxM = 0
        x = abs(maxM) / abs(minP)   
        y = abs(maxP) / abs(minM)
        ret_new = 1
        if x > y:
            for i in range(K):
                if i != minP_i:
                    ret_new *= B[i].getNum() % MOD
                    ret_new %= MOD
            ret_new *= B[maxM_i].getNum() % MOD
            ret_new %= MOD
        else:
            for i in range(K):
                if i != minM_i:
                    ret_new *= B[i].getNum() % MOD
                    ret_new %= MOD
            ret_new *= B[maxP_i].getNum() % MOD
            ret_new %= MOD
        print(ret_new)
    else:
        print(0)
        return


@total_ordering
class Num:
    def __init__(self, num):
        self.num = num
        self.sign = (num > 0) - (num < 0)
    
    def __eq__(self, value):
        return abs(self.num) == abs(value.num)
    
    def __lt__(self, value):
        return abs(self.num) < abs(value.num)

    def getNum(self):
        return self.num

    def getSign(self):
        return self.sign

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort(reverse=True, key=lambda x:abs(x))
cnt = 0
im = 0
ip = 0
cp = 0
mod = 10 ** 9 + 7

for i, ai in enumerate(a):
    if i < k:
        if ai < 0:
            im = i
            cnt += 1
        if ai > 0:
            ip = i
    if ai > 0:
        cp += 1

ans = 1
f = 0

# print(a)
if cnt % 2:
    if cp == 0:
        a.sort(reverse=True)
        for i, ai in enumerate(a):
            if i == k:
                break
            ans *= ai
            ans %= mod
        print(ans)
    else:
        for i, ai in enumerate(a):
            if i == im:
                f = 1
                continue
            if f == 1:
                if ai > 0:
                    ans *= abs(ai)
                    ans %= mod
                    f = 2
                    break
                else:
                    continue
            ans *= abs(ai)
            ans %= mod
        if f == 2:
            print(ans)
        else:
            ans = 1
            cnt = 0
            f = 0
            for i, ai in enumerate(a):
                if cnt == k:
                    break
                if i == ip:
                    f = 1
                    continue
                if f == 1 and ai > 0:
                    continue
                ans *= abs(ai)
                ans %= mod
                # print(i, ai)
                cnt += 1
            print(ans)

else:
    for i, ai in enumerate(a):
        if i == k:
            break
        ans *= abs(ai)
        ans %= mod
    print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))

A = sorted(A, reverse=True)

i = 0
while A[i] >= 0:
    i += 1
    if i >= len(A):
        break

plus = A[:i]
minus = sorted(A[i:], reverse=True)


if len(plus) > 0:
    next_i = 0
    for m in minus:
        if plus[0] < abs(m):
            plus.insert(0, m)
            continue
        for i in range(next_i, len(plus)-1):
            if plus[i] > abs(m) > plus[i+1]:
                plus.insert(i+1, m)
                next_i  = i+1
                continue
        plus.insert(-1, m)
else:
    plus = sorted(minus)

a = 1
b = 1

for num in plus[:K]:
    a *= num

for num in A[:K]:
    b *= num

if a > b:
    print(a % (10**9 + 7))
else:
    print(b % (10**9 + 7))

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7

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

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

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

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


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

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


i, j = 0, 0

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

if k % 2 == 1:
    ans = (ans*p[j]) % MOD
if ans == MOD:
    ans = 0
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
mod = 10**9+7
P = []
M = []
zero = []
for a in A:
    if a>0:
        P.append(a)
    elif a<0:
        M.append(a)
    else:
        zero.append(a)
if N==K and zero: print(0);exit()

P.sort(reverse=True)
M.sort(reverse=True)
if K==1:
    A.sort()
    print(A[-1]);exit()
if len(P)>=K:
    ans = 1
    P = P[:K]
    P.sort()
    for i in range(K):
        ans *=P[i]
        ans %=mod
    while P:
        while len(M)>=2:
            a1 = M.pop()
            a2 = M.pop()
            b1 = P.pop()
            b2 = P.pop()
            if a1*a2 > b1*b2:
                ans = ans/b1
                ans = ans/b2
                ans *=a1*a2
                ans %=mod
            else:
                break
        break
else:
    ans = 1
    P.sort()
    for i in range(len(P)):
        ans *=P[i]
        ans %=mod
    K -=len(P)
    if K>len(M):print(0);exit()
    else:
        if K%2!=0:
            if zero:print(0);exit()
            else:
                M.sort(reverse=True)
                for i in range(K):
                    ans *=M[i]
                    ans %=mod
        else:
            for i in range(K):
                ans *=M[i]
                ans %=mod
print(int(ans%mod))

Submission status: Wrong Answer

Solution code:
N, K, *A = map(int, open(0).read().split())
MOD = 10 ** 9 + 7

if sum(v == 0 for v in A) > N - K:
    print(0)
    exit()


if all(v <= 0 for v in A):
    x = sorted([v for v in A if v < 0])
    ans = 1
    if K % 2 == 0:
        for i in range(K):
            ans = ans * x[i] % MOD
    else:
        n = len(x)
        for i in range(n - K, n):
            ans = ans * x[i] % MOD

    print(ans)
    exit()


x = sorted([(abs(v), v // abs(v)) for v in A if v != 0])
plus = []
minus = []
for i in range(K):
    v, s = x.pop()
    if s == 1:
        plus.append(v)
    else:
        minus.append(v)


if len(minus) % 2 != 0:
    p_cand = MOD
    m_cand = MOD
    while x:
        v, s = x.pop()
        if s == 1 and p_cand == MOD:
            p_cand = v
        elif s == -1 and m_cand == MOD:
            m_cand = v
    
    if p_cand == MOD and m_cand != MOD and plus:
        plus.pop()
        minus.append(m_cand)
    elif m_cand == MOD and p_cand != MOD and minus:
        minus.pop()
        plus.append(p_cand)
    elif p_cand != MOD and m_cand != MOD and plus and minus:
        p_val = plus.pop() * p_cand
        m_val = minus.pop() * m_cand
        
        if p_val > m_val:
            plus.append(p_val)
        else:
            minus.append(m_val)
            
ans = 1
for v in plus:
    ans = ans * v % MOD
for v in minus:
    ans = ans * (-v) % MOD
print(ans)

Submission status: Wrong Answer

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 len(P)+len(N)<k:
  print(0)
  exit()

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

if len(P)+len(N)==k:
  if len(N)%2==0:
    print(P2[-1]*N2[-1]%mod)
    exit()
  else:
    print(0)
    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=0
    if xn+1<len(N):
      xb=N[xn]*N[xn+1]
    else:
      xb=0
    if xa<xb:
      xn+=2
      ans*=xb
      ans%=mod
    else:
      xp+=2
      ans*=xa
      ans%=mod
  print(ans)

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=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
  if ctP*2+1<=len(P):
    ans*=P[ctP*2]
    ans%=mod
    print(ans)
  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
    print(-ans%mod)

Submission status: Wrong Answer

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

pos = []
neg  = []
pool = []
zeros = 0
for i in range(n):
    if a[i]>0:
        pos.append(a[i])
    if a[i]<0:
        neg.append(a[i])
    if a[i]==0:
        zeros+=1
pos.sort()
neg.sort(reverse=True)
ans = []
if len(pos)==0:
    if len(neg)<k or (zeros>0 and k%2):
        ans = [0]
    else:
        for i in range(k):
            ans.append(neg[i])
    k = 0
else:
    if k%2== 1:
        if len(pos)>0:
            ans.append(pos[-1])
            pos.pop()
            k-=1
    while(k):
        if len(pos)<2 and len(neg)<2:
            if zeros>0:
                ans = [0]
                k = 0
            else:
                ans.append(pos[0])
                ans.append(neg[0])
                k -= 2
            break
        elif len(pos)<2:
            ans.append(neg[-1])
            ans.append(neg[-2])
            neg.pop()
            neg.pop()
        elif len(neg)<2:
            ans.append(pos[-1])
            ans.append(pos[-2])
            pos.pop()
            pos.pop()
        else:
            if neg[-1]*neg[-2] > pos[-1]*pos[-2]:
                ans.append(neg[-1])
                ans.append(neg[-2])
                neg.pop()
                neg.pop()   
            else:
                ans.append(pos[-1])
                ans.append(pos[-2])
                pos.pop()
                pos.pop()
        k -= 2



res = 1
for i in range(len(ans)):
    res *= ans[i]
    res %= MOD

print(res)

Submission status: Wrong Answer

Solution code:
from functools import reduce
from operator import mul

mod = 1000000007

n, k = input().split()
a = input().split()

a = [int(x) for x in a]
n, k = int(n), int(k)

ans = []
for i in range(0, n-k+1):
    answer = reduce(mul, a[i:i+k], 1)
    ans.append(answer)
_max = max(ans)
# print(_max)


if _max < 0:
    print(mod + _max)
else:
    print(_max % mod)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = []
a.sort()
tmp = 1
for i in range(k):
    tmp *= a[i]
ans.append(tmp)
tmp = 1
a.sort(reverse = True)
for i in range(k):
    tmp *= a[i]
ans.append(tmp)

print((max(ans))%(10**9+7))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
mod = 10**9 + 7
plus = []
minus = []
zlen = 0
for i in map(int, input().split()):
    if i > 0:
        plus.append(i)
    elif i < 0:
        minus.append(i)
    else:
        zlen += 1
plen = len(plus)
mlen = len(minus)
if K > plen + mlen:
    print(0)
    import sys
    sys.exit()
plus.sort(reverse=True)
minus.sort()
pp = [1]
mp = [1]
for p in plus:
    pp.append((pp[-1]*p)%mod)
for m in minus:
    mp.append((mp[-1]*(-m))%mod)
ppm = [1]
mpm = [1]
for p in plus[::-1]:
    ppm.append((ppm[-1]*p)%mod)
for m in minus[::-1]:
    mpm.append((mpm[-1]*(-m))%mod)
ans = -float("inf")
# kこマイナスから選ぶ
for k in range(K+1):
    if mlen < k:
        continue
    if plen < K-k:
        continue
    # 最大を目指す
    if k % 2 == 0:
        tmp = mp[k] * pp[K-k]
        ans = max(ans, tmp)
    # 絶対値最小を目指す
    else:
        tmp = -(mpm[k] * ppm[K-k])
        ans = max(ans, tmp)
if ans < 0 and zlen > 0:
    print(0)
    import sys
    sys.exit()
print(ans%mod)

Submission status: Wrong Answer

Solution code:
import heapq

mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
cnt_plus=0
cnt_zero=0
cnt_minus=0
arr_plus=[]
arr_minus=[]
for i in range(n):
  if arr[i]>0:
    cnt_plus+=1
    arr_plus.append(arr[i])
  elif arr[i]<0:
    cnt_minus+=1
    arr_minus.append(-arr[i])
  else:
    cnt_zero+=1
if cnt_plus+cnt_minus<k:
  print(0)
else:
  if (k%2==1 and cnt_plus==0) or (cnt_plus+2*(cnt_minus//2)<k):
    q=[]
    for i in range(n):
      if arr[i]>0:
        heapq.heappush(q,(arr[i],1))
      if arr[i]<0:
        heapq.heappush(q,(-arr[i],-1))
    pick=[]
    for i in range(k):
      tmp,flag=heapq.heappop(q)
      if flag==1:
        pick.append(tmp)
      else:
        pick.append(-tmp)
    ans=1
    for i in range(k):
      ans*=pick[i]
      ans%=mod
    print(ans)
  else:
    q=[]
    for i in range(n):
      if arr[i]>0:
        heapq.heappush(q,(-arr[i],1))
      if arr[i]<0:
        heapq.heappush(q,(arr[i],-1))
    pick=[]
    prev=0
    cnt=0
    for _ in range(k):
      tmp,flag=heapq.heappop(q)
      tmp*=-1
      if flag==1:
        pick.append(tmp)
      else:
        if cnt==0:
          prev=tmp
          cnt+=1
        else:
          cnt=0
          pick.append(prev)
          pick.append(tmp)
          prev=0
    if cnt==0:
      ans=1
      for i in range(k):
        ans*=pick[i]
        ans%=mod
      print(ans)
    else:
      cand_plus=0
      cand_minus=0
      while len(q)!=0:
        tmp,flag=heapq.heappop(q)
        tmp*=-1
        if flag==1 and cand_plus==0:
          cand_plus=tmp
        if flag==-1 and cand_minus==0:
          cand_minus=tmp
        if cand_plus!=0 and cand_minus!=0:
          break
      if pick[-1]*cand_plus>=prev*cand_minus:
        pick.append(cand_plus)
      else:
        pick=pick[:-1]
        pick.append(prev)
        pick.append(cand_minus)      
      ans=1
      for i in range(k):
        ans*=pick[i]
        ans%=mod
      print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
li_a = list(map(int, input().split()))
mod = 10**9+7
li = []
lll = 0
for i in li_a:
    if i < 0:
        li.append((abs(i), -1))
        lll += 1
    else:
        li.append((i, 1))
li.sort()
if lll == n:
    ans = 1
    for i in range(k):
        ans *= -li[i][0]
        ans %= mod
    print(ans)
    exit()
ans = 1
guki = 1
for i in range(n-1, n-k-1, -1):
    ans *= li[i][0]
    ans %= mod
    guki *= li[i][1]
if guki > 0:
    print(ans)
else:
    P, M, p, m = 10**6, 1000000, 1000000, 1000000
    P1, M1, p1, m1 = True, True, True, True
    for i in range(n-k, n-1):
        if li[i][1] > 0:
            Plus = li[i][0]
            P = i
            P1 = False
            break
    for i in range(n-k, n-1):
        if li[i][1] < 0:
            Mini = li[i][0]
            M = i
            M1 = False
            break
    for i in range(n-k, -1, -1):
        if li[i][1] > 0:
            plus = li[i][0]
            p = i
            p1 = False
            break
    for i in range(n-k, -1, -1):
        if li[i][1] < 0:
            mini = li[i][0]
            m = i
            m1 = False
            break
    ans1 = 1
    ans2 = 1
    if (not P1) and (not m1):
        for i in range(n-1, n-k-1, -1):
            if i == P:
                continue
            ans1 *= li[i][0]
            ans1 %= mod
        ans1 *= li[m][0]
        ans1 %= mod
    if (not p1) and (not M1):
        for i in range(n-1, n-k-1, -1):
            if i == M:
                continue
            ans1 *= li[i][0]
            ans1 %= mod
        ans2 *= li[p][0]
        ans2 %= mod
    if p1 or P1 or M1 or m1:
        print(max(ans1, ans2))
    else:
        ans = 1
        for i in range(k):
            ans *= -li[i][0]
            ans %= mod
        print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main():

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

    mod = pow(10, 9) + 7

    pos = []
    neg = []
    zero = 0
    for v in A:
        if v > 0: pos.append(v)
        elif v < 0: neg.append(v)
        else: zero += 1

    # zero is needed
    if len(pos) + len(neg) < K:
        return 0

    pos.sort(reverse = True)
    neg.sort()

    cnt_p, cnt_n = 0, 0
    h = []
    for v in pos:
        h.append([v, 1])
    for v in neg:
        h.append([-v, -1])

    h.sort(reverse = True)
    v = 1
    for k in range(K):
        if h[k][1] > 0:
            cnt_p += 1
        else:
            cnt_n += 1

    if cnt_n % 2 == 0: # when positive
        v = 1
        for i in range(cnt_p):
            v *= pos[i]
            v %= mod
        for j in range(cnt_n):
            v *= neg[j]
            v %= mod
        return v
    else: # when negative
        if cnt_p < len(pos) and cnt_n < len(neg): # both are not full
            # if abs(neg[cnt_n]) / pos[cnt_p-1] < pos[cnt_p] / abs(neg[cnt_n-1]):
            if pos[cnt_p] * pos[cnt_p-1] > abs(neg[cnt_n]) * abs(neg[cnt_n-1]):
                cnt_p += 1
                cnt_n -= 1
            else:
                cnt_p -= 1
                cnt_n += 1
            v = 1
            for i in range(cnt_p):
                v *= pos[i]
                v %= mod
            for j in range(cnt_n):
                v *= neg[j]
                v %= mod
            return v
        elif cnt_p < len(pos) and cnt_n > 0:
            cnt_p += 1
            cnt_n -= 1
            v = 1
            for i in range(cnt_p):
                v *= pos[i]
                v %= mod
            for j in range(cnt_n):
                v *= neg[j]
                v %= mod
            return v
        elif cnt_n < len(neg) and cnt_p > 0:
            cnt_p -= 1
            cnt_n += 1
            for i in range(cnt_p):
                v *= pos[i]
                v %= mod
            for j in range(cnt_n):
                v *= neg[j]
                v %= mod
            return v
        else:
            if zero > 0:
                return 0
            else:
                h.sort()
                v = 1
                for i in range(K):
                    v *= h[i][0] * h[i][1]
                    v %= mod
                return v



if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
import sys
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def Main():
    n,k = IL()
    a = list(IL())
    a.sort()
    mod = int(1e9+7)
    ans = 1
    if k%2:
        for i in range(n-1,n-k-1,-1):
            ans = ans*min(a[i],a[i]%mod)
            ans = min(ans,ans%mod)
    else:
        l = r = 1
        for i in range(0,k):
            l = l*min(a[i],a[i]%mod)
            r = r*min(a[n-i-1],a[n-i-1]%mod)
            l = min(l,l%mod)
            r = min(r,r%mod)
            if abs(l)<abs(r):
                ans = r
            else:
                ans = l
    ans = ans%mod
    print(ans%mod)
    return

if __name__=='__main__':
    Main()

Submission status: Wrong Answer

Solution code:
N, K = list(map(int,input().split()))
A = list(map(int,input().split()))
A = sorted(A, reverse = True, key = lambda x:abs(x))

ans = 1
for i in range(K):
  ans *= A[i]
print(ans%(10**9+7))