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%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:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
mod = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
pm = 1
ans = 1

a.sort()
if k%2 == 1 and a[n - 1] < 0:
    if 0 in a:
        print(0)
        sys.exit()
    for i in range(k):
        ans = (ans * a[n - 1 - i])%mod
    print(ans%mod)
    sys.exit()
for i in range(k//2):
    p = a[n-1] * a[n-2]
    m = a[0] * a[1]
    if p >= m:
        ans = (ans * p)%mod
        a.pop(n - 1)
        a.pop(n - 2)
    else:
        ans = (ans * m)%mod
        a.pop(1)
        a.pop(0)
    n -= 2
if k%2 == 1:
    ans = (ans * a[n - 1])%mod
print(ans%mod)

Submission status: Wrong Answer

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

m = 1000000007

a = [e for e in A if e > 0]
b = [e for e in A if e < 0]
c = [e for e in A if e == 0]
# プラスルート
if len(a) >= K or (K % 2 == 0 and len(a) + (len(b) // 2) * 2 >= K):
    a.sort(reverse=True)
    b.sort()
    result = 1
    i = 0
    j = 0
    k = 0
    while k < K:
        if k < K - 1 and i < len(a) - 1 and j < len(b) - 1:
            x = a[i] * a[i + 1]
            y = b[j] * b[j + 1]
            if y >= x:
                result *= y
                result %= m
                j += 2
                k += 2
            else:
                result *= a[i]
                result %= m
                i += 1
                k += 1
        elif k < K - 1 and j < len(b) - 1:
            y = b[j] * b[j + 1]
            result *= y
            result %= m
            j += 2
            k += 2
        elif i < len(a):
            result *= a[i]
            result %= m
            i += 1
            k += 1
        elif j < len(b):
            result *= b[j]
            result %= m
            j += 1
            k += 1
    print(result)
# 0 ルート
elif len(c) != 0:
    print(0)
# マイナスルート
else:
    a.sort()
    b.sort(reverse=True)
    result = 1
    i = 0
    j = 0
    k = 0
    while k < K:
        if i < len(a) and j < len(b):
            if a[i] <= -b[i]:
                result *= a[i]
                result %= m
                i += 1
                k += 1
            else:
                result *= b[j]
                result %= m
                j += 1
                k += 1
        elif i < len(a):
            result *= a[i]
            result %= m
            i += 1
            k += 1
        elif j < len(b):
            result *= b[j]
            result %= m
            j += 1
            k += 1
    print(result)

Submission status: Wrong Answer

Solution code:
def main():
    MOD = 10 ** 9 + 7

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

    A.sort(key=abs, reverse=True)

    ans = 1
    sgn = 1
    last_minus_in_k = None
    last_plus_in_k = None
    first_minus_outof_k = None
    first_plus_outof_k = None
    for i, x in enumerate(A):
        if i < K:
            if x < 0:
                sgn = -sgn
                last_minus_in_k = x
                ans = (ans * (-x)) % MOD
            else:
                last_plus_in_k = x
                ans = (ans * x) % MOD
        else:
            if x < 0:
                if first_minus_outof_k is None:
                    first_minus_outof_k = x
            else:
                if first_plus_outof_k is None:
                    first_plus_outof_k = x

    if sgn == 1 or K == N:
        print(ans % MOD)
        return

    # 交換できる場合
    if last_plus_in_k is None:
        # マイナスが奇数個のみ
        if first_plus_outof_k:
            ans = ((ans * pow(last_minus_in_k, MOD - 2, MOD)) % MOD) * first_plus_outof_k % MOD
            print(ans % MOD)
            return

        A.sort(key=abs)
        ans = 1
        sgn = 1
        for i, x in enumerate(A):
            if i < K:
                if x < 0:
                    sgn = -sgn
                    ans = (ans * (-x)) % MOD
                else:
                    ans = (ans * x) % MOD
            else:
                break
        print(ans * sgn % MOD)
        return

    else:
        if first_plus_outof_k is not None and first_minus_outof_k is not None:
            if first_minus_outof_k * last_minus_in_k >= first_plus_outof_k * last_plus_in_k:
                ans = ((ans * pow(last_plus_in_k, MOD - 2, MOD)) % MOD) * first_minus_outof_k % MOD
                print(ans % MOD)
                return
            else:
                ans = ((ans * pow(last_minus_in_k, MOD - 2, MOD)) % MOD) * first_plus_outof_k % MOD
                print(ans % MOD)
                return

        if first_plus_outof_k is not None:
            ans = ((ans * pow(last_minus_in_k, MOD - 2, MOD)) % MOD) * first_plus_outof_k % MOD
            print(ans % MOD)
            return

        if first_minus_outof_k is not None:
            ans = ((ans * pow(last_plus_in_k, MOD - 2, MOD)) % MOD) * first_minus_outof_k % MOD
            print(ans % MOD)
            return


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Wrong Answer

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

def mod_inverse(a, p):
    mod = 1
    p_bin = bin(p-2)
    for i in range(len(p_bin) - 1, 1, -1):
        if i == len(p_bin) - 1:
            mul = a
            mul %= p
            mod *= (mul ** int(p_bin[i]))
            mod %= p
        else:
            mul = mul ** 2
            mul %= p
            mod *= (mul ** int(p_bin[i]))
            mod %= p
    return mod

a2 = []
for i in range(n):
    if a[i] == 0:
        a2.append([0, 1])
    else:
        a2.append([abs(a[i]), abs(a[i]) // a[i]])
a2.sort(reverse = True)
ans = 1
count_m = 0
count_p = 0
max_p = float("inf")
max_m = float("inf")
for i in range(k):
    ans *= a2[i][0]
    ans %= mod
    if a2[i][1] == -1:
        count_m += 1
        max_m = a2[i][0]
    else:
        count_p += 1
        max_p = a2[i][0]
if count_m % 2 == 0 or ans == 0:
    print(ans)
else:
    num = k
    while num < n:
        temp = a2[num][1]
        if temp == -1:
            if max_p != float("inf"):
                ans *= mod_inverse(max_p, mod)
                ans %= mod
                ans *= a2[num][0]
                ans %= mod
                print(ans)
                break
            else:
                num += 1
        else:
            if max_m != float("inf"):
                ans *= mod_inverse(max_m, mod)
                ans %= mod
                ans *= a2[num][0]
                ans %= mod
                print(ans)
                break
            else:
                num += 1
    else:
        a2.sort()
        ans = -1
        for i in range(k):
            ans *= a2[i][0]
            ans %= mod
        print(ans)

Submission status: Wrong Answer

Solution code:
# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
    # combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
# mod = 998244353
INF = 1<<50

def readInt():
    return list(map(int,input().split()))

def main():
    n,k = readInt()
    a = readInt()
    ans = -INF
    a.sort()
    for i in range(0,k+1,2):
        res = 1
        for j in range(i):
            res *= a[j]
            res %= mod
        for j in range(n-k+i,n):
            res *= a[j]
            res %= mod
        ans = max(ans,res)
    print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

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

B=[]
C=[]
Z=[]

for a in A:
    if a>0:
        B.append(a)
    elif a<0:
        C.append(-a)
    else:
        Z.append(0)

if K==len(B)+len(C):
    ANS=1
    for b in B:
        ANS=ANS*b%mod
    for c in C:
        ANS=ANS*c%mod

    if len(C)%2==1 and Z!=[]:
        print(0)
    else:
        print(ANS)
    sys.exit()

if K>len(B)+len(C):
    print(0)
    sys.exit()

if B==[]:
    ANS=1
    for i in range(K):
        ANS=ANS*(C[i])%mod

    if Z==[]:
        print(ANS)
    elif K%2==1:
        print(0)
    else:
        print(ANS)

    sys.exit()

    
B.sort(reverse=True)
C.sort(reverse=True)

if K<=len(B):
    S=1
    for i in range(K):
        S=S*B[i]%mod

    ind=0
    while True:
        if ind+1<len(C) and K-2-ind>=0 and C[ind]*C[ind+1]>B[K-1-ind]*B[K-2-ind]:
            S=S*C[ind]*C[ind+1]*pow(B[K-1-ind]*B[K-2-ind],mod-2,mod)%mod
            ind+=2
        else:
            break

    print(S%mod)

else:
    if (K-len(B))%2==0:
        S=1
        for i in range(len(B)):
            S=S*B[i]%mod

        for j in range(K-len(B)):
            S=S*C[j]%mod

        ind=K-len(B)

    else:
        S=1
        for i in range(len(B)-1):
            S=S*B[i]%mod

        for j in range(K-len(B)+1):
            S=S*C[j]%mod

        ind=K-len(B)+1
        

    while True:
        if ind+1<len(C) and K-2-ind>=0 and C[ind]*C[ind+1]>B[K-1-ind]*B[K-2-ind]:
            S=S*C[ind]*C[ind+1]*pow(B[K-1-ind]*B[K-2-ind],mod-2,mod)%mod
            ind+=2
        else:
            break

    print(S%mod)

Submission status: Wrong Answer

Solution code:
def main():
    M=10**9+7
    n,k,*a=map(int,open(0).read().split())
    x,y=[],[]
    for i in a:
        if i>0:x.append(i)
        if i<0:y.append(i)
    if len(x)+len(y)<k or len(x)<k and (k-len(x))%2 and len(x)+len(y)<n:
        print(0)
        exit()
    if len(x)<k and (k-len(x))%2:
        x=sorted(x+[-i for i in y])[:k]
        x[0]*=-1
        c=1
        for i in x:
            c=c*i%M
        print(c)
        exit()
    x=sorted(x)[::-1][:k]
    y.sort()
    m=len(y)
    i=len(x)
    j=0
    if i<k:
        j=k-i
        x+=y[:j]
        j+=1
    while i>1 and j+1<m and x[i-1]*x[i-2]<y[j]*y[j+1]:
        x[i-1],x[i-2]=y[j],y[j+1]
        i-=2
        j+=2
    c=1
    for i in x:
        c=c*i%M
    print(c)
main()

Submission status: Wrong Answer

Solution code:
def main():
    mod = 10**9+7
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(key=lambda x: -abs(x))
    kouho = []
    minus = 0
    last_plus = None
    last_minus = None
    if k == 1:
        print(max(a))
        return
    for i in range(k):
        kouho.append(a[i])
        if a[i] >= 0:
            last_plus = a[i]
        if a[i] < 0:
            minus += 1
            last_minus = a[i]
    if minus % 2 == 0:
        ans = 1
        for i in kouho:
            ans = ans*i % mod
        print(ans)
        return
    change_plus = None
    change_minus = None
    if last_plus != None:
        # マイナスを追加する
        for i in range(k, n):
            if a[i] <= 0:
                change_plus = a[i]
                break
    if last_minus != None:
        # マイナスを追加する
        for i in range(k, n):
            if a[i] >= 0:
                change_minus = a[i]
                break

    # print(kouho)
    #print(last_plus, change_plus)
    #print(last_minus, change_minus)

    if change_plus == None and change_minus == None:
        ans = 1
        for i in range(k):
            ans = ans*a[-i-1] % mod
    elif change_plus == None:
        ans = change_minus
        for i in kouho:
            ans = ans*i % mod
        ans = ans*pow(last_minus, mod-2, mod) % mod
    elif change_minus == None:
        ans = change_plus
        for i in kouho:
            ans = ans*i % mod
        ans = ans*pow(last_plus, mod-2, mod) % mod
    else:
        if abs(change_plus*last_plus) < abs(change_minus*last_minus):
            ans = change_minus
            for i in kouho:
                ans = ans*i % mod
            ans = ans*pow(last_minus, mod-2, mod) % mod
        else:
            ans = change_plus
            for i in kouho:
                ans = ans*i % mod
            ans = ans*pow(last_plus, mod-2, mod) % mod
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
B = []
C = []
for i in range(N):
    a = A[i]
    if a < 0:
        b = -a
        B.append(b)
    else:
        b = a
        C.append(a)
S = []
while B and C:
    a = B[0]
    b = C[0]
    p = 0
    if a <= b:
        S.append(-a)
        B.pop(0)
    else:
        S.append(b)
        C.pop(0)
if B:
    for i in B:
        S.append(-i)
if C:
    for i in C:
        S.append(i)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
m=bisect_left(a,0)
ans=1
MOD=10**9+7
if m==0 or m==n:
    for i in a[-k:]:
        ans=(ans*i)%MOD
else:
    for i in range((m//2)*2,-2,-2):
        cal=1
        if k-i>n-m:
            break
        for j in a[:i]:
            cal=(cal*j)%MOD
        if k-i>0:
            for j in a[-(k-i):]:
                cal=(cal*j)%MOD
        ans=max(ans,cal)
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
MOD = 10**9+7
a = list(map(int,input().split()))
b = []
c = []
d = []
num_z = 0
for val in a:
    if val>0:
        b.append(val)
        d.append(val)
    elif val<0:
        c.append(-val)
        d.append(-val)
    else:
        num_z += 1
        d.append(0)
num_b = len(b)
num_c = len(c)
res = 1
if (N==num_c and K%2==1):
    d = sorted(d)
    for val in d[:K]:
        res = res*val%MOD
    res = -res%MOD
elif (N==K and num_c>0):
    c = sorted(c)
    for val in a:
        res = res*val%MOD
else:
    b = sorted(b,reverse=True)
    c = sorted(c,reverse=True)
    bidx = 0
    cidx = 0
    tmp = 0
    if num_b+num_c < K:
        res = 0
    else:
        if num_b >= K:
            bidx = K
        elif num_c>=2:
            bidx = num_b
            cidx = K-bidx
            if (K-num_b)%2==1:
                bidx -= 1
                cidx += 1
        else:
            print(0)
            exit()
        # print(bidx,cidx)
        for val in b[:bidx]:
            res = res*val%MOD
        for val in c[:cidx]:
            res = res*val%MOD
        for k in range(100000):
            if bidx<=1 or cidx+1 >= num_c:
                break
            if b[bidx-1]*b[bidx-2] > c[cidx]*c[cidx+1]:
                break
            else:
                res *= c[cidx]
                res *= c[cidx+1]
                res = res%MOD
                res = res*pow(b[bidx-1],MOD-2,MOD)
                res = res*pow(b[bidx-2],MOD-2,MOD)
                res = res%MOD
                bidx -= 2
                cidx += 2
print(res%MOD)

Submission status: Wrong Answer

Solution code:
from functools import reduce
import operator
MOD = 10**9+7
mprod = lambda it: reduce(lambda x,y: (x*y)%MOD,it,1)
nprod = lambda it: reduce(lambda x,y: (x*y),it,1)


from fractions import Fraction

def solve(A,K):
    N = len(A)
    if N == K:
        return mprod(A)

    if all(v <= 0 for v in A):
        A.sort()
        return mprod(A[-K:])

    A.sort(key=lambda x: abs(x))

    if A[-K] == 0:
        return 0

    parity = sum(v < 0 for v in A[-K:])%2
    if parity == 0:
        return mprod(A[-K:])

    rp = N-K
    while rp < N and A[rp] < 0:
        rp += 1

    rn = N-K
    while rn < N and A[rn] > 0:
        rn += 1


    lp = N-K-1
    while lp >= 0 and A[lp] < 0:
        lp -= 1

    ln = N-K-1
    while ln >= 0 and A[ln] > 0:
        ln -= 1

    if rp < N and ln >= 0:
        r1 = Fraction(-A[ln],A[rp])
    else:
        r1 = 0
    if rn < N and lp >= 0:
        r2 = Fraction(-A[lp],A[rn])
    else:
        r2 = 0
    if r1 > r2:
        return (mprod(A[-K:])*A[ln]*pow(A[rp],-1,MOD))%MOD
    else:
        return (mprod(A[-K:])*A[lp]*pow(A[rn],-1,MOD))%MOD

from itertools import combinations
def naive(A,K):
    return max(nprod(p) for p in combinations(A,K))%MOD


if __name__ == '__main__':
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    
    print(solve(A,K)%MOD)

    # from random import randrange

    # N = 9
    # K = 5
    # for _ in range(100000):
    #     A = [randrange(-8,8) for _ in range(5)]
    #     if solve(A.copy(),K) != naive(A.copy(), K):
    #         print(A, solve(A.copy(),K),naive(A.copy(), K) )

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])
        # pool.append(a[i])
        # if k-len(pool)%2==0 and len(pos)<k:
        #     pos.extend(pool)
        #     pool = []
    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 zeros>0:
        ans = [0]
    else:
        for i in range(k):
            ans.append(neg[i])
    k = 0
else:
    while(k>1):
        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

    if k == 1:
        if len(pos)>0:
            ans.append(pos[-1])
            pos.pop()
        elif zeros>0:
            ans.append(0)

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

print(res)

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 = -1
last_posi = -1
for i in range(K):
    if A[i] < 0:
        last_nega = i
    else:
        last_posi = 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
    ans1 = -float('inf')
    ans2 = -float('inf')
    if last_nega != -1:
        ans1 = ans*pow(abs(A[last_nega]),mod-2,mod)
        ans1 %= mod
        for i in range(K,N):
            if 0 <= A[i]:
                ans1 *= A[i]
                ans1 %= mod
                break
        else:
            ans1 = -float('inf')
    if last_posi != -1:
        ans2 = ans*pow(abs(A[last_posi]),mod-2,mod)
        ans2 %= mod
        for i in range(K,N):
            if A[i] < 0:
                ans2 *= abs(A[i])
                ans2 %= mod
                break
        else:
            ans2 = -float('inf')
    ans3 = 1
    for i in range(1,K+1):
        ans3 *= A[-i]
        ans3 %= mod
    ans = max(ans1,ans2,ans3)
    print(ans%mod)

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,K=map(int,input().split())

A=list(map(int,input().split()))
mod=10**9+7
Am=[-i for i in A if i<0]
Ap=[i for i in A if i>=0]

Am.sort()
Ap.sort()
Am=deque(Am)
Ap=deque(Ap)



if K-len(Ap)>0 and (K-len(Ap))%2:
    c=1
    while K and (Am or Ap) :
        if Am and Ap:
            if Am[0]<Ap[0]:
                c*=Am.popleft()
            else:
                c*=Ap.popleft()
        elif Am:
            c*=Am.popleft()
        elif Ap:
            c*=Ap.popleft()
        K-=1
        c=-c
        c%=mod
    #print("unko")

else:
    c=1
    while K and (len(Am)>=2 or Ap) :
        if K==1 and len(Ap)==0:
            break
        if K>=2 and len(Am)>=2:
            if len(Am)>=2 and len(Ap)>=2:
                if Ap[-1]*Ap[-2]>Am[-1]*Am[-2]:
                    c*=Ap.pop()
                    c*=Ap.pop()
                else:
                    c*=Am.pop()
                    c*=Am.pop()
                K-=2
            elif len(Ap)==1 and len(Am)>=2:
                if Ap[-1]>Am[-1]*Am[-2]:
                    c*=Ap.pop()
                    K-=1
                else:
                    c*=Am.pop()
                    c*=Am.pop()
                    K-=2
            else:
                c*=Am.pop()
                c*=Am.pop()
                K-=2
        else:
            c*=Ap.pop()
            K-=1
        c%=mod
print(c%mod)