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:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, K = mi()
A = li()

d = defaultdict(int)
mod = 10**9+7
K_ = K

if N == K:
    ans = 1
    for num in A:
        ans *= num
        ans %= mod
    print(ans)
    exit()

for i in range(N):
    d[A[i]] += 1
    if A[i] < 0:
        A[i] *= -1

A = sorted(A, reverse=True)
l = []

for num in A:
    if d[-num] > 0:
        l.append(1)
        d[-num] -= 1
    else:
        l.append(0)
        d[num] -= 1

#print(l)
#print(sum(l[:K]))

if not sum(l[:K])%2:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= mod
    print(ans)

else:
    flag = False
    ans = 1
    for i in range(K, N):
        if not l[i]:
            flag = True
            ans *= A[i]
            ans %= mod
            break
    
    if flag:
        for i in reversed(range(K)):
            if flag and l[i]:
                flag = 0
                continue
            ans *= A[i]
            ans %= mod
        print(ans)
    
    else:
        if K%2:
            for i in range(N-K, N):
                ans *= A[i]
                ans %= mod
            ans *= -1
            ans %= mod
            print(ans)

        else:
            for i in range(N):
                if l[i]:
                    K -= 1
                    ans *= A[i]
                    ans %= mod
                if K == 0:
                    break

            else:
    
                ans = 1
                flag = True
                for i in reversed(range(K_)):
                    if flag and l[i]:
                        flag = 0
                        continue
                    ans *= A[i]
                    ans %= mod
                ans *= A[K_]
                ans %= mod
                print(ans)
                exit()

            print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

mod = 10 ** 9 + 7

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

if N == K:
    ans = 1
    for i in range(N):
        ans *= A[i]
        ans %= mod
    print(ans)
    sys.exit()

A = np.array(A)

plus = A[A>0]
minus = A[A<0]
zero = A[A==0]

if len(zero) > N - K:
    print(0)
    sys.exit()

if len(plus) == 0:
    if K % 2 == 0:
        minus = np.sort(minus)
    else:
        minus = np.sort(minus)[::-1]
    ans = 1
    for i in range(K):
        ans *= minus[i]
        ans %= mod
    print(ans)
    sys.exit()

plus = np.sort(plus)[::-1]
minus *= -1
minus = np.sort(minus)[::-1]

if K % 2 == 1:
    ans = plus[0]
    K -= 1
    p = (len(plus)-1) // 2
    m = len(minus) // 2
    
    n_p = [plus[2*i+1] * plus[2*i+2] for i in range(p)]
    n_m = [minus[2*i] * minus[2*i+1] for i in range(m)]
else:
    ans = 1
    p = len(plus) // 2
    m = len(minus) // 2
    
    n_p = [plus[2*i] * plus[2*i+1] for i in range(p)]
    n_m = [minus[2*i] * minus[2*i+1] for i in range(m)]

K //= 2

p_index = 0
m_index = 0
for i in range(K):
    if p_index == len(n_p):
        ans *= n_m[m_index]
        ans %= mod
        m_index += 1
    elif m_index == len(n_m):
        ans *= n_p[p_index]
        ans %= mod
        p_index += 1
    else:
        if n_p[p_index] > n_m[m_index]:
            ans *= n_p[p_index]
            ans %= mod
            p_index += 1
        else:
            ans *= n_m[m_index]
            ans %= mod
            m_index += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
INF = float('inf')
MOD = 10**9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 1
is_pos = 0
for ai in A:
    if ai > 0:
        is_pos += 1
if is_pos == 0 and K % 2 == 1:
    sortA = sorted(A, key=abs)    
    for ai in sortA[:K]:
        ans = (ans * ai) % MOD
    print(ans)
    sys.exit()
        
sortA = sorted(A, reverse=True, key=abs)
# print(sortA)

pos_list = [0]
neg_list = [0]


for ai in sortA[:K]:
    if ai < 0:
        neg_list += [ai]
    elif ai > 0:
        pos_list += [ai]
    else:
        print(0)
        sys.exit()
# first_pos = 0
# first_neg = 0
first_pos = INF
first_neg = INF
for i in range(K, N):
    if ai > 0 and first_pos == INF:
        first_pos = sortA[i]
    elif ai < 0 and first_neg == INF:
        first_neg = sortA[i]
len_pos = len(pos_list)
len_neg = len(neg_list)
if len_pos == 0:
    if len_neg % 2 == 1:
        for i in range(1, len_neg):
            ans = (ans * neg_list[i]) % MOD
    else:
        ans = ans * first_pos
        for i in range(1, len_neg-1):
            ans = (ans * neg_list[i]) % MOD
    print(ans)
    sys.exit()
if len_neg % 2 == 1 or K==N:
    for i in range(1, len_pos):
        ans = (ans * pos_list[i]) % MOD
    for i in range(1, len_neg):
        ans = (ans * neg_list[i]) % MOD
    print(ans)
    sys.exit()
# print(first_neg, first_pos)
if first_neg == INF:
    ans = (ans * first_pos) % MOD
    for i in range(1, len_pos):
        ans = (ans * pos_list[i]) % MOD
    for i in range(1, len_neg-1):
        ans = (ans * neg_list[i]) % MOD
    print(ans)
    sys.exit()
if first_pos == INF:
    ans = (ans * first_neg) % MOD
    for i in range(1, len_pos-1):
        ans = (ans * pos_list[i]) % MOD
    for i in range(1, len_neg):
        ans = (ans * neg_list[i]) % MOD
    print(ans)
    sys.exit()
pos2 = abs(pos_list[-1] * first_pos)
neg2 = abs(neg_list[-1] * first_neg)
if pos2 > neg2:
    ans = (ans * first_pos) % MOD
    for i in range(1, len_pos):
        ans = (ans * pos_list[i]) % MOD
    for i in range(1, len_neg-1):
        ans = (ans * neg_list[i]) % MOD
else:
    ans = (ans * first_neg) % MOD
    for i in range(1, len_pos-1):
        ans = (ans * pos_list[i]) % MOD
    for i in range(1, len_neg):
        ans = (ans * neg_list[i]) % MOD
print(ans)

Submission status: Wrong Answer

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

#solve
def solve():
    n, k = LI()
    a = LI()
    if n == k:
        ans = a[0]
        for i in a[1:]:
            ans *= i
            ans %= mod
        print(ans)
        return
    mi = []
    ma = []
    a.sort()
    for ai in a:
        if ai <= 0:
            heappush(mi, ai)
        else:
            heappush(ma, (-ai,1))
    X = []
    if not ma:
        ans = 1
        if k & 1:
            for i in range(k):
                ans *= a[-i - 1]
                ans %= mod
        else:
            for i in range(k):
                ans *= a[i]
                ans %= mod
        print(ans)
        return
    ans = 1
    while len(mi) >= 2:
        xx1 = heappop(mi)
        xy1 = heappop(mi)
        heappush(ma, (-xx1 * xy1, 2))
    t = 0
    LL = 0
    while t < k and ma:
        tmp, xx = heappop(ma)
        tmp = -tmp 
        if xx == 1:
            LL = tmp
        if t + xx > k:
            while t < k and ma:
                tmp1, xx = heappop(ma)
                tmp1 = -tmp1
                if xx == 1:
                    if tmp1 * LL >= tmp:
                        ans *= tmp1
                        ans %= mod
                        print(ans)
                        return
                    else:
                        ans *= pow(LL, mod - 2, mod)
                        ans *= tmp
                        ans %= mod
                        print(ans)
                        return
            
        ans *= tmp
        t += xx
        ans %= mod

    print(ans)
    return


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

Submission status: Wrong Answer

Solution code:
#                          JAI SHREE RAM

import math; from collections import *
import sys; from functools import reduce

# sys.setrecursionlimit(10**6)
def get_ints(): return map(int, input().strip().split())
def get_list(): return list(get_ints())
def get_string(): return list(input().strip().split())
def printxsp(*args): return print(*args, end="")
def printsp(*args): return print(*args, end=" ")

UGLYMOD = int(1e9)+7; SEXYMOD = 998244353; MAXN = int(1e5)

# sys.stdin=open("input.txt","r");sys.stdout=open("output.txt","w")

# for _testcases_ in range(int(input())):
n, k = get_ints()
li = get_list()
pos = []
neg = []
ans = 1
zeroes = 0
for i in li:
    if i < 0: neg.append(i)
    elif i > 0: pos.append(i)
    else: zeroes += 1
lengthOfPos, lengthOfNeg = len(pos), len(neg)

if k&1 : #and (k - lengthOfPos) >= 0 and (k - lengthOfPos) & 1:
    if k > lengthOfPos:
        if zeroes:
            print("0")
        else:
            # last pr pakka negative ayega
            pos.extend([0] * zeroes)
            pos.sort(); positionOfPos = 0
            neg.sort(reverse = True); positionOfNeg = 0
            while k > 1:
                try: negpower = neg[positionOfNeg] * neg[positionOfNeg+1]
                except: negpower = float('inf')
                try: pospower = pos[positionOfPos] * pos[positionOfPos+1]
                except: pospower = float('inf')
                if pospower <= negpower:
                    positionOfPos += 2
                    ans = (ans * (pospower % UGLYMOD)) % UGLYMOD
                else:
                    ans = (ans * (negpower % UGLYMOD)) % UGLYMOD
                    positionOfNeg += 2
                k -= 2
            if k == 1:
                try: negpower = neg[positionOfNeg]
                except: negpower = float('inf')
                try: pospower = pos[positionOfPos]
                except: pospower = float('inf')
                ans = (ans * min(pospower, negpower)) % UGLYMOD
            print(ans)
            
    else:
        pos.sort(reverse = True); positionOfPos = 0
        neg.sort(); positionOfNeg = 0
        ans = 1
        while k > 1:
            try: negpower = neg[positionOfNeg] * neg[positionOfNeg+1]
            except: negpower = -float('inf')
            try: pospower = pos[positionOfPos] * pos[positionOfPos+1]
            except: pospower = -float('inf')
            if pospower >= negpower:
                positionOfPos += 2
                ans = (ans * (pospower % UGLYMOD)) % UGLYMOD
            else:
                ans = (ans * (negpower % UGLYMOD)) % UGLYMOD
                positionOfNeg += 2
            k -= 2
        if k == 1:
            ans = (ans * pos[positionOfPos]) % UGLYMOD
        print(ans)
else:
    pos.sort(reverse = True); positionOfPos = 0
    neg.sort(); positionOfNeg = 0
    ans = 1
    while k > 1:
        try: negpower = neg[positionOfNeg] * neg[positionOfNeg+1]
        except: negpower = -float('inf')
        try: pospower = pos[positionOfPos] * pos[positionOfPos+1]
        except: pospower = -float('inf')
        if pospower >= negpower:
            positionOfPos += 2
            ans = (ans * (pospower % UGLYMOD)) % UGLYMOD
        else:
            ans = (ans * (negpower % UGLYMOD)) % UGLYMOD
            positionOfNeg += 2
        k -= 2
    if k == 1:
        ans = (ans * pos[positionOfPos]) % UGLYMOD
    print(ans)







'''
>>> COMMENT THE STDIN!! CHANGE ONLINE JUDGE !!
THE LOGIC AND APPROACH IS MINE @luctivud ( UDIT GUPTA )
Link may be copy-pasted here if it's taken from other source.
DO NOT PLAGIARISE.
>>> COMMENT THE STDIN!! CHANGE ONLINE JUDGE !!
'''

Submission status: Wrong Answer

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

mainasu=[]
purasu=[]
zero=[]
for aa in a:
    if aa==0:
        zero.append(aa)
    elif aa>0:
        purasu.append(aa)
    else:
        mainasu.append(aa*(-1))

#ゼロを選ばないといけない絶対ゼロ
if len(purasu)+len(mainasu)<k:
    print(0)
    exit()
mod=10**9+7

#プラスがない
if len(purasu)==0:
    #奇数個選択しないといけない
    if k%2==1:
        if len(zero)>0:
            print(0)
            exit()
        else:
            mainasu.sort()
            cnt=0
            ans=1
            while cnt<k:
                ans=ans*mainasu[cnt]%mod
                cnt+=1
            ans=abs(ans-mod)
    #偶数個選択可能
    else:
        if len(mainasu)%2==0:
            mainasu.sort(reverse=True)
            cnt=0
            ans=1
            while cnt<k:
                ans=ans*mainasu[cnt]%mod
                cnt+=1
        else:
            print(0)
            exit()
    print(ans%mod)
    exit()


purasu.sort(reverse=True)
mainasu.sort(reverse=True)

p_pos=0
m_pos=0
cnt=0
ans=1
while cnt<k:
    #マイナスもプラスも選択可能
    #print(">>",cnt)
    if p_pos<len(purasu) and m_pos+1<len(mainasu):
        #print("1")
        #ラスト1個しか選べない
        if cnt==k-1:
            ans=ans*purasu[p_pos]
            ans=ans%mod
            cnt+=1
            p_pos+=1
        #複数個選べる
        else:
            #マイナスの方が大きい
            if purasu[p_pos]<=mainasu[m_pos+1] or cnt<k-1:
                tmp=(mainasu[m_pos]%mod)*(mainasu[m_pos+1]%mod)
                tmp=tmp%mod
                ans=ans*tmp
                ans=ans%mod
                m_pos+=2
                cnt+=2
            else:
                ans=ans*purasu[p_pos]
                ans=ans%mod
                cnt+=1
                p_pos+=1

    #プラスのみ選べる
    elif p_pos<len(purasu):
        #print("2>>",len(purasu),p_pos)
        ans=ans*purasu[p_pos]
        ans=ans%mod
        cnt+=1
        p_pos+=1

    #マイナスのみ2個選べる
    elif m_pos+1<len(mainasu) and cnt+1<k:
        #print("3")
        tmp=(mainasu[m_pos]%mod)*(mainasu[m_pos+1]%mod)
        tmp=tmp%mod
        ans=ans*tmp
        ans=ans%mod
        m_pos+=2
        cnt+=2
    #マイナスのみ1個選べる
    elif m_pos<len(mainasu):
        #print("4")
        #ゼロがある
        if len(zero)>0:
            print(0)
            exit()
        else:
            ans=ans*mainasu[m_pos]*(-1)
            #print("mainasu",ans)
            m_pos+=1
            cnt+=1
    #print(ans)

print(ans%mod)

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 n==1:
        print(a[0]%mod)
        return
    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%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: Wrong Answer

Solution code:
n, k = map(int, input().split())
arr = [int(x) for x in input().split()]
 
mod = 10**9 + 7
 
def solve(A, n, k): 
    mod = 10**9 + 7
  
    # sorting given input array 
    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): 
            # print(i,A[i])
            product *= (A[i] % mod) 
        return product % mod
    i = 0 
    j = n - 1 
    if (k & 1): 
        product *= (A[j] % mod)
        j-= 1
        k-=1 
    k >>= 1
    for itr in range(k) :
        left_product = (A[i]%mod) * (A[i + 1]%mod)
        right_product = (A[j]%mod) * (A[j - 1]%mod)
        if (left_product > right_product) : 
            product *= (left_product % mod)
            i += 2
        else : 
            product *= (right_product % mod)
            j -= 2
    return product % mod
print(solve(arr, n, k) % mod)

Submission status: Wrong Answer

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


def checkio(numbers_array):
    return sorted(numbers_array, key=lambda x: abs(x))

a = checkio(a)[::-1]

plus = [i for i in a if i >= 0]
mainas = [i for i in a if i < 0]


cnt = 1
for i in range(k):
    cnt *= a[i]

if cnt >=0:
    print(cnt)

Submission status: Wrong Answer

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

mod = 10**9+7
res = 1
last_plus_index = -1
last_minus_index = -1
p_c = 0
m_c = 0

from collections import deque
# d = deque(A)

for i in range(K):
    t = A[i]
    # res *= t
    if t < 0:
        last_minus_index = i
        m_c += 1
    if t > 0:
        last_plus_index = i
        p_c += 1

if m_c % 2 == 0:
    for i in range(K):
        t = A[i]
        res *= t
        res = res % mod
    print(res)
    exit()

# if K-1 == last_minus_index:
#     for i in range(K, N):
#         if A[i] > 0:
#             res = res // A[last_minus_index] * A[i]
#             print(res % mod)
#             exit()
#         if i == N-1:
#             if last_plus_index != -1:
#                 res = res // A[last_plus_index] * A[K]
#                 print(res % mod)
#                 exit()
#             else:
#                 # 解が0以下
#                 A = sorted(A, reverse=True)
#                 res = 1
#                 for i in range(K):
#                     res *= A[i]
#                 print(res % mod)
#                 exit()
#
# else:
#     for i in range(K, N):
#         if A[i] < 0:
#             res = res // A[K-1] * A[i]
#             print(res % mod)
#             exit()
#         if i == N-1:
#             res = res // A[last_minus_index] * A[K]
#             print(res % mod)
#             exit()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

mod = 10 ** 9 + 7
n, k = map(int, input().split())
A = list(map(int, input().split()))
# dp = [[[0] * (2) for _ in range(k+1)]for _ in range(n+1)]
# # dp[桁][数][負数の数=1,0]

A.sort()
n_minus = bisect_left(A, 0)
n_zero = bisect_right(A, 0) - n_minus
n_plus = n - n_minus - n_zero

possible_max = min(k, n_minus)
possible_min = max(k - (n_plus + n_zero), 0)
ans = 1
if possible_max == possible_min and possible_min % 2 == 1:
    if k - (possible_min) > 0 and n_zero > 0:
        print(0)
        exit()
    A_plus = A[n - (n_plus) :]
    A_minus = A[:n_minus]
    A_minus.sort(reverse=True)
    # 負の数は奇数個小さい方から選ぶ
    for i in range(possible_min):
        ans *= A_minus[i]
        ans %= mod
    for i in range(k - possible_min):
        ans *= A_plus[i]
        ans %= mod
else:
    # 正の数に成る→大きいものがほしい
    # 負の数は偶数個、これの数を決め打つ
    # 計算すると大変だから大小を考える

    A_plus = A[n - (n_plus) :]
    A_plus.sort(reverse=True)
    A_minus = A[:n_minus]

    # 負の数を使う数を決め打つ
    # 最終的に正にできるパターン
    minus_num_max = min(n_minus // 2, k // 2)
    select = k - 2 * minus_num_max
    if n_plus < select:
        print(0)
        exit()
    # 負の数にしかできないパターン
    # 遊びがない時に奇数個の負の数を選ばざるを得ない
    # その時に0があるかどうかパターン
    kouho = []
    for i in range(minus_num_max):
        if 2 * i + 1 >= n_minus:
            break
        temp = A_minus[2 * i] * A_minus[2 * i + 1]
        kouho.append((temp, -1))
    for i in range(n_plus // 2):
        temp = A_plus[2 * i] * A_plus[2 * i + 1]
        kouho.append((temp, +1))
    kouho.sort(reverse=True)
    if k % 2 == 0:
        for i in range(k // 2):
            ans *= kouho[i][0]
            ans %= mod
    else:
        cnt = 0
        i = 0
        for i in range(k // 2):
            num, f = kouho[i]
            if f == 1:
                cnt += 1
            ans *= num
            ans %= mod
        if n_plus<=2*cnt:
            print(0)
            exit()
        ans *= A_plus[2 * cnt]
        ans %= mod


print(ans % mod)