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(product)
        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)
        


                

                    




        
    
        
        
    


            


            
                
            

            



                






        
        


    
    
                

    

""" -------- 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:
N,K = map(int,input().split())
list = list(map(int,input().split()))

#if K % 2 != 0:
    #list.sort(reverse=True)
    #for i in range(1,K):
    #    n = list[0]*list[i]
    #print(n % ((10^9)+7))
#else:
m = 1
o = 1
list.sort(reverse=True)
#print(list)
for i in range(K):
    m=m*list[i]
#print(m)
list.sort()
#print(list)
for i in range(K):
    o=o*list[i]
#print(o)
if m > o:
    print(m%((10^9)+7))
    #print("a")
else:
    print(o%((10^9)+7))
    #print("b")

Submission status: Wrong Answer

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

if n == k:
    prod = 1
    for b in a:
        prod *= b
        prod %= mod
    print(prod)
    exit()

# negative prod
if k & 1 and a[-1] < 0:
    prod = 1
    for i in range(k):
        prod *= a[-1 - i]
        prod %= mod
    print(prod)
    exit()

A = []
for b in a:
    if b < 0:
        A.append((-b, True))
    else:
        A.append((b, False))
A = sorted(A)[::-1]

ans = 1
is_neg = False
last_neg = 1
last_nneg = -1

for i in range(k + 1):
    (b, neg) = A[i]
    ans *= b
    ans %= mod
    is_neg ^= neg
    if i == k - 1:
        if not is_neg:
            print(ans)
            exit()
    if i <= k - 1:
        if neg:
            last_neg = b
        else:
            last_nneg = b
    if i == k:
        if is_neg:
            ans *= pow(last_neg, mod - 2, mod)
        else:
            ans *= pow(last_nneg, mod - 2, mod)
        ans %= mod
        print(ans)
        exit()

Submission status: Wrong Answer

Solution code:
N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
MOD = 10**9 + 7
def calc(X):
  ans = 1
  for x in X:
    ans *= x
    ans %= MOD
  return ans

def solve(A):
  if N == K:
    return calc(A)
  if max(A) < 0 and K % 2:
    return calc(sorted(A, reverse=True)[:K])
  
  sA = sorted(((abs(a), -1 if a < 0 else 1) for a in A), reverse=True)
  #print(sA)
  cn = 0
  for i in range(K):
    if sA[i][1] < 0:
      cn += 1
  if cn % 2 == 0:
    return calc([s[0] for s in sA[:K]])
  pA = sorted([abs(a) for a in A if a >= 0], reverse=True)
  nA = sorted([abs(a) for a in A if a < 0], reverse=True)
  #print(pA, nA)
  candidates = []
  if len(nA) >= cn + 1 and len(pA) >= K - cn - 1:
    #print(cn, cn+1)
    candidates.append(calc(pA[:K-cn-1] + nA[:cn+1]))
  if len(nA) >= cn - 1 and len(pA) >= K - cn + 1:
    #print(cn, cn-1)
    candidates.append(calc(pA[:K-cn+1] + nA[:cn-1]))
  
  return(max(candidates))

print(solve(A))

Submission status: Wrong Answer

Solution code:
import itertools
from operator import mul
from functools import reduce


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

a = 0

for pair in itertools.combinations(A, K):
    aa = reduce(mul,pair)
    if a <= aa:
        a == aa
print(aa)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

mod = 10**9+7
N, K = map(int, input().split())
A = list(map(int, input().split()))

Mi = []
for a in A:
    if a != 0:
        Mi.append((abs(a), a//abs(a)))

Mi.sort(reverse=True)

if len(Mi) < K:
    ans = 0
else:
    ans = 1
    seg = 1
    lastinv = -1
    lastpu = -1
    for i in range(K):
        a, iv = Mi[i]
        seg *= iv
        if iv == -1:
            lastinv = a
        else:
            lastpu = a
        ans = ans * a % mod

    if seg == -1:
        fpu = -1
        fmi = -1
        ind = K
        while ind < len(Mi):
            a, iv = Mi[ind]
            ind += 1
            if iv == -1:
                if fmi == -1:
                    fmi = a
                continue
            if fpu == -1:
                fpu = a
        
        if lastpu == -1:
            if fpu != -1:
                ans = ans * fpu * pow(lastinv, mod-2, mod) % mod
            elif 0 in A:
                ans = 0
            else:
                ans = -1
                for i in range(K):
                    ans = ans * Mi[-i-1][0] % mod
        elif fpu == -1 or fmi == -1:
            if fpu == -1 and fmi == -1:
                if 0 in A:
                    ans = 0
                else:
                    ans = -ans
            elif fpu == -1:
                ans = ans * fmi * pow(lastpu, mod-2, mod) % mod
            else:
                ans = ans * fpu * pow(lastinv, mod-2, mod) % mod
        elif lastpu * fpu > lastinv * fmi:
            ans = ans * fpu * pow(lastinv, mod-2, mod) % mod
        else:
            ans = ans * fmi * pow(lastpu, mod-2, mod) % mod
    
    print(ans % mod)

Submission status: Wrong Answer

Solution code:
mod = 10**9+7

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

A.sort(reverse=True)

ans = 1
left = 0
right = len(A)-1

if A[0] < 0:
    for i in range(K):
        ans = (ans * A[i]) % mod
else:
    while K > 0:
        if K == 1:
            ans = (ans * A[left]) % mod
            left += 1
            break
        else:
            r = A[right] * A[right-1]
            l = A[left] * A[left + 1]
            if l > r:
                ans = (ans * l) % mod
                left += 2
            else:
                ans = (ans * r) % mod
                right -= 2
            K -= 2

if ans < 0:
    ans = ans + mod

print(ans)

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

def main():
    INF = 999999999999999999999999
    MOD = 10**9+7

    n,k,*A = get_all_int()
    A = list(A)

    # 答えが負である条件
    # ・Aが全て負で、Kが奇数
    # ・Aの負数が奇数個かつ0が存在せず、K=N

    # 答えが0である条件
    # ・N-(Aの0の個数) < K

    positives = 0
    zeros = 0
    negatives = 0

    for a in A:
        if a > 0:
            positives += 1
        elif a == 0:
            zeros += 1
        else:
            negatives += 1
    
    if (n-zeros) < k:
        # 答えが0
        print(0)
        exit()
    
    elif (k==n and negatives%2==1  or  n==negatives and k%2==1):
        # 答えが負
        # 絶対値小さい順にK個掛ける
        A.sort(key=lambda a: abs(a))
        # log(A)
        ans = 1
        for i in range(k):
            ans =  (ans * A[i]) % MOD
        print(ans)
        exit()

    else:
        # 答えが正
        # 絶対値大きい順にK個掛ける
        A.sort(reverse=True, key=lambda a: abs(a))
        # log(A)
        ans = 1
        n_count = 0
        last_n = 0
        last_p = 0
        for i in range(k):
            a = A[i]
            ans =  (ans * a) % MOD
            if a < 0:
                n_count += 1
                last_n = a
            elif a > 0:
                last_p = a
                # log(i, last_n)

        # log(ans, n_count, last_n)
        
        # 負数を奇数個選んでいる場合は調整する
        if n_count%2 == 1:
            for i in range(k,n):
                a = A[i]
                if a > 0 and last_n!=0:
                    ans = ans*inv(last_n, MOD) * a
                    break
                if a < 0 and last_p!=0:
                    ans = ans*inv(last_p, MOD) * a
                    break
        print(ans%MOD)
        exit()

main()

Submission status: Wrong Answer

Solution code:
# Author: S Mahesh Raju
# Username: maheshraju2020
# Date: 05/07/2020

from sys import stdin,stdout
from math import gcd, ceil, sqrt
from collections import Counter
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
mod = 1000000007

n, k = iia()
arr = sorted(iia(), key=lambda x: abs(x), reverse=True)
res = []
first = last = None
neg = 0
for i in range(k):
    if arr[i] < 0 and first == None:
        first = last = i
        neg += 1
    elif arr[i] < 0:
        last = i
        neg += 1

m = None
for i in range(k, len(arr)):
    if m == None:
        m = arr[i]
    else:
        m = max(m, arr[i])

if neg % 2 != 0 and m != None:
    arr[first] = m

res = arr[0]
for i in range(1, k):
    res *= arr[i]
    res %= mod
print(res % mod)

Submission status: Wrong Answer

Solution code:
def resolve():
    def addans(i, ans):
        return ans * i % mod
    import sys
    import bisect
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, k = map(int, input().split())
    a = sorted(list(map(int, input().split())))
    l = bisect.bisect_left(a, 0)
    r = bisect.bisect_right(a, 0)
    if n - k < r - l:
        print(0)
        return
    if r == n:
        ans = 1
        for i in range(k):
            ans = addans(a[-i - 1], ans)
        print(ans)
        return
    ans = 1
    minus = [0] * 3 + a[:l]
    plus = [0] * 3 + a[r:]
    if k % 2 == 1:
        ans = plus.pop()
        k -= 1
    m = minus.pop() * minus.pop()
    p = plus.pop() * plus.pop()
    for _ in range(k // 2):
        if p >= m:
            ans = addans(p, ans)
            p = plus.pop() * plus.pop()
        else:
            ans = addans(m, ans)
            m = minus.pop() * minus.pop()
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

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

A.sort()

mod = int(1e9+7)
AM = []
AP = []
AZC = 0
for a in A:
  if a < 0:
    AM.append(a)
  elif a == 0:
    AZC += 1
  else:
    AP.append(a)

#print(AM)
#print(AP)
#print(AZC)
# zero選ばないとだめならゼロ
if N-K < AZC:
  print(0)
  exit(0)

# minusしか選べないケースってあるの？
# AMしかなくて、Kがodd
# zeroが一つでもあればZERO
if len(AP) == 0 and K%2 == 1:
  if AZC > 0:
    print(0)
  else:
    wk = 1
    for i in range(K):
      wk *= AM[-1-i]
      wk %= mod
    print(wk)
  exit(0)  
   
# plusを狙える
# K odd -> plus max 1
# K even -> ２個いちで選んで行ってMAXを
wk = 1
if K%2 == 1:
  wk *= AP.pop(-1)
  wk %= mod
  
K = K // 2
mi, pi = 0, 0
AP = AP[::-1]
while K>0:
  mwk = AM[mi] * AM[mi + 1] if mi + 1 < len(AM) else 0
  pwk = AP[pi] * AP[pi + 1] if pi + 1 < len(AP) else 0
  if mwk <= pwk:
    wk *= pwk
    pi += 2
  else:
    wk *= mwk
    mi += 2
  #print(wk)
  wk %= mod
  K -= 1
print(wk)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
n, k = map(int, input().split())
a_i = list(map(int, input().split()))
list.sort(a_i)
ans = 1
if k % 2 == 0:
    left = 0
    right = n - 1
else:
    left = 0
    right = n - 2
    ans *= a_i[n - 1]
for x in range(k // 2):
    if ans * a_i[left] * a_i[left + 1] < ans * a_i[right] * a_i[right - 1]:
        ans *= a_i[right] * a_i[right - 1]
        right -= 2
    else:
        ans *= a_i[left] * a_i[left + 1]
        left += 2
    if ans < 0 or ans >= mod: ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
from math import log10
n, k = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10**9+7
a.sort()

cnt_neg = 0
cnt_pos = 0
for i in a:
   if i <= 0:
      cnt_neg += 1
   else:
      cnt_pos += 1
is_minus = False
k_tmp = k
while k_tmp > 0:
   if k_tmp >= 2:
      if cnt_neg >= 2:
         cnt_neg -= 2
      elif cnt_pos >= 2:
         cnt_pos -= 2
      else:
         is_minus = True
         break
      k_tmp -= 2
   else:
      if cnt_pos > 0:
         cnt_pos -= 1
         k_tmp -= 1
      else:
         is_minus = True
         break

k_1 = k
ans1 = 1
l = 0
r = n - 1
while k_1 >= 2:
   if a[l] * a[l+1] > a[r-1] * a[r]:
      ans1 *= a[l] * a[l+1]
      l += 2
   else:
      ans1 *= a[r-1] * a[r]
      r -= 2
   k_1 -= 2
   ans1 %= MOD
if k_1 == 1:
   ans1 *= a[-1]

a.sort(key=abs)
ans2 = 1
for i in a[:k]:
   ans2 *= i
   ans2 %= MOD

if is_minus:
   print(ans2)
else:
   print(ans1)

Submission status: Wrong Answer

Solution code:
# FROM GEEKSFORGEEKS

# Required function 
def maxProductSubarrayOfSizeK(A, n, k):
	A.sort()
	product = 1
	if (A[n - 1] == 0 and (k & 1)): 
		return 0
	if (A[n - 1] <= 0 and (k & 1)) : 
		for i in range(n - 1, n - k + 1, -1): 
			product *= A[i] 
		return product 
	i = 0
	j = n - 1
	if (k & 1): 
		product *= A[j] 
		j-= 1
		k-=1
	k >>= 1
	for itr in range( k) :
		left_product = A[i] * A[i + 1]
		right_product = A[j] * A[j - 1]
		if (left_product > right_product) : 
			product *= left_product 
			i += 2
		else : 
			product *= right_product 
			j -= 2
	return product
if __name__ == "__main__": 
	n,k=map(int,input().split())
	A=list(map(int,input().split()))
	print(maxProductSubarrayOfSizeK(A, n, k)%1000000007)

Submission status: Wrong Answer

Solution code:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
A.sort(key=lambda x: abs(x),reverse=True)
mod = 10**9+7
sign = 1
last_nega = 0
for i in range(K):
    if A[i] < 0:
        last_nega = i
    sign *= (1 if 0 < A[i] else -1)

if 0 < sign:
    ans = 1
    for i in range(K):
        ans *= abs(A[i])
        ans %= mod
    print(ans)
else:
    ans = 1
    for i in range(K):
        ans *= abs(A[i])
        ans %= mod
    ans *= pow(abs(A[last_nega]),mod-2,mod)
    ans %= mod
    for i in range(K,N):
        if 0 <= A[i]:
            ans *= A[i]
            ans %= mod
            break
    else:
        ans = 1
        for i in range(1,K+1):
            ans *= A[-i]
            ans %= mod
    print(ans%mod)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N,K = LI()
    A = LI()

    ans = 1
    if max(A) < 0 and K % 2:
        x = sorted(A,reverse=True)
        for i in range(K):
            ans = (ans * A[i]) % MOD
        print(ans)
        return


    x = sorted(A, key=lambda x: abs(x), reverse=True)
    m = 0
    for i in range(K):
        ans = (ans * abs(x[i])) % MOD
        if x[i] < 0 :m += 1

    if K == N or m % 2 == 0:
        print(ans)
        return
    if x[K] == 0:
        print(0)
        return
    else:
        for i in range(K-1,-1,-1):
            if x[i] * x[K] < 0:
                ans = (ans * pow(abs(x[i]),MOD-2,MOD) * x[K]) % MOD
                print(ans)
                return
        print(ans)
        return



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

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


A = sorted(A, reverse=True)[0:K]

o = 1
for i in A:
    s = i
    o *= s
if o > 1000000007 or o < 0:
    o %= 1000000007


print(o)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


mod = 10 ** 9 + 7

n, k = LI()
A = LI()
A = [[abs(a), a] for a in A]
ret = 1
flg = 0
fflg = 0
z_flg = 0
A.sort(reverse=True)
for i in range(n):
    if A[i][1] >= 0:
        flg = 1
    if A[i][1] == 0:
        z_flg = 1

if flg == 0 and z_flg == 0 and k % 2:
    A.reverse()


ret = 1
abs_max_minus = INF
minus_flg1 = 0
plus_flg1 = 0
minus_flg2 = 0
plus_flg2 = 0
for i in range(k):
    ret = ret * A[i][0] % mod
    if A[i][1] < 0:
        fflg ^= 1
        abs_max_minus = min(abs_max_minus, A[i][0])
        minus_flg1 = 1
    if A[i][1] > 0:
        plus_flg1 = 1


abs_max_plus_remain = 0
for j in range(k, n):
    if A[j][1] > 0:
        abs_max_plus_remain = max(abs_max_plus_remain, A[j][1])
        plus_flg2 = 1
    elif A[j][1] < 0:
        minus_flg2 = 1


if n == k:
    if fflg:
        ret = -ret
    print(ret % mod)
    exit()

if fflg:
    if (plus_flg1 and minus_flg2) or (minus_flg1 and plus_flg2):
        ret //= abs_max_minus
        ret *= abs_max_plus_remain
        fflg ^= 1

if fflg and z_flg:
    print(0)
else:
    if fflg:
        ret = -ret
    print(ret % mod)

Submission status: Wrong Answer

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

if N==K:
    ans=1
    for i in range(N):
        ans=(ans*A[i])%mod
    print(ans%mod)
else:
    neg=[]
    posi=[]
    zero=0
    for i in range(N):
        if A[i]>0:
            posi.append(A[i])
        elif A[i]<0:
            neg.append(-A[i])
        else:
            zero+=1
    if K>N-zero:
        print(0)
    elif len(neg)==N and K%2==1:
        neg.sort()
        ans=1
        for i in range(K):
            ans=(-ans*neg[i])%mod
        print(ans%mod)
    else:
        A.sort(key=lambda x:-abs(x))
        temp=A[:K]
        rest=A[K:]
        check=0
        for i in range(K):
            if temp[i]<0:
                check+=1
        if check%2==0:
            ans=1
            for i in range(K):
                ans=(ans*abs(temp[i]))%mod
            print(ans%mod)
        else:
            if check!=K and check!=0:
                rest.sort()
                temp.sort()
                #neg->posi
                val1=-1
                val2=-1
                for i in range(K-1):
                    if temp[i]<0 and temp[i+1]>0:
                        val1=temp[i]
                        val2=temp[i+1]
                        break
                (abs(val1),rest[-1])
                #posi->neg
                (abs(val2),abs(rest[0]))
                if abs(rest[-1])*abs(val2)>abs(rest[0])*abs(val1):
                    ans=1
                    for i in range(K):
                        ans=(ans*abs(temp[i]))%mod
                    ans=(ans*abs(rest[-1]))%mod
                    ans=(ans*pow(abs(val1),mod-2,mod))%mod
                    print(ans%mod)
                else:
                    ans=1
                    for i in range(K):
                        ans=(ans*abs(temp[i]))%mod
                    ans=(ans*abs(rest[0]))%mod
                    ans=(ans*pow(abs(val2),mod-2,mod))%mod
                    print(ans%mod)
            elif check==K:
                val1=abs(temp[-1])
                ans=1
                for i in range(K):
                    ans=(ans*abs(temp[i]))%mod
                ans=(ans*abs(rest[-1]))%mod
                ans=(ans*pow(abs(val1),mod-2,mod))%mod
                print(ans%mod)
            else:
                val2=abs(temp[0])
                ans=1
                for i in range(K):
                    ans=(ans*abs(temp[i]))%mod
                ans=(ans*abs(rest[0]))%mod
                ans=(ans*pow(abs(val2),mod-2,mod))%mod
                print(ans%mod)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,k,*a = map(int,read().split())

pos = []
neg = []
#both = []
zero = 0

for i in a:
    #if i!=0: both.append(i)
    
    if i==0: zero += 1
    elif i > 0: pos.append(i)
    else: neg.append(-i)

#print(pos,neg,zero)
MOD = 10**9+7

if n - zero < k: # ゼロが多すぎる
    print(0)

elif pos == []: # 全部ゼロ以下
    if k%2==0:
        neg.sort(reverse=True)
        ans = 1
        for i in range(k):
            ans *= neg[i]
            ans %= MOD
        print(ans)
    else:
        if zero:
            print(0)
        else: # 負のみ
            neg.sort()
            ans = -1
            for i in range(k):
                ans *= neg[i]
                ans %= MOD
            print(ans%MOD)
            
else: #正もいる
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    cp = len(pos)
    cn = len(neg)
    
    i = j = 0    
    for _ in range(k):
        if i == cp:
            j += 1
        elif j==cn:
            i += 1
        else:
            if pos[i] > neg[j]:
                i += 1
            else:
                j += 1
    
    #print(i,j)
    if j%2 == 0:
        ans = 1
        for x in pos[:i]:
            ans *= x
            ans %= MOD
        for x in neg[:j]:
            ans *= x
            ans %= MOD
        print(ans)
            
    else:
        can_i = i and j < cn
        can_j = j and i < cp
        
        if not can_i:
            j -= 1
            i += 1
        elif not can_j:
            j += 1
            i -= 1
        else:
            if pos[i]*pos[i-1] >= neg[j]*neg[j-1]:
                j -= 1
                i += 1
            else:
                j += 1
                i -= 1

        ans = 1                
        for x in pos[:i]:
            ans *= x
            ans %= MOD
        for x in neg[:j]:
            ans *= x
            ans %= MOD
        print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N,K=[int(i) for i in input().split(" ")]
A=[int(i) for i in input().split(" ")]

plus=[]
minus=[]
for a in A:
    if a>0:
        plus.append(a)
    elif a<0:
        minus.append(a)

if len(plus)+len(minus)<K:
    print(0)
    sys.exit(0)

if len(plus)==0:
    minus=sorted(minus,reverse=True)
    retval=1
    for i in minus[:K]:
        retval*=i
    print(retval%(10**9+7))
    sys.exit(0)


plus=sorted(plus,reverse=True)
minus=sorted(minus)

A=sorted(A,key=lambda w:abs(w),reverse=True)

retval=1
use_minus=0
for i in range(K):
    a=A[i]
    if a<0:
        use_minus+=1
    retval*=a
    retval=retval%(10**9+7)

if retval>0:
    print(retval%(10**9+7))
else:
    inv=pow(minus[use_minus-1],10**9+5,10**9+7)
    retval*=inv
    use_plus=K-use_minus
    retval=retval*plus[use_plus]
    print(retval%(10**9+7))