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:
N,K = map(int,input().split())
A = list(map(int,input().split()))
ans = 1
mod = 10**9+7

if min(A) > 0:
    A.sort(reverse=True)
    for i in A[:K]:
        ans = (ans*i)%mod

elif max(A) < 0:

    if K%2 == 0:
        A.sort()
        for i in A[:K]:
            ans = (ans*abs(i))%mod
    else:
        A.sort(reverse=True)
        for i in A[:K]:
            ans = (ans*abs(i))%mod
        ans *= -1

else:
    z = []
    p = []
    m = []
    for i in A:
        if i == 0:
            z.append([i,1])
        elif i > 0:
            p.append([i,1])
        else:
            m.append(i)
    m.sort()
    mm = []
    for i in range(0,len(m),2):
        try:
            mm.append([m[i]*m[i+1],2])
        except:
            pass
    
    tot = p+z+mm

    tot.sort(reverse=True)

    for v,cost in tot:
        if K - cost >= 0:
            ans = (ans*v)%mod
            K -= cost
        else:
            continue

print(ans%mod)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,K=map(int,input().split())
A=list(map(int,input().split()))
A_m=[x for x in A if x<0]
A_pz=[x for x in A if x>=0]
A_m.sort()
A_pz.sort(reverse=1)
if N==K:
    ans=1
    for x in A:
        ans*=x
        ans%=MOD
elif not A_pz and K%2==1:
    ans=1
    for x in A_m[::-1][:K]:
        ans*=x
        ans%=MOD
else:
    B=[]
    for i in range(len(A_m)//2):
        B.append(A_m[i*2]*A_m[i*2+1])
    B.sort(reverse=1)
    i,j=0,0
    ans=1
    while i+j*2<=K-2:
        if i<len(A_pz) and j<len(B):
            if A_pz[i]>B[j]:
                ans*=A_pz[i]
                i+=1
            else:
                ans*=B[j]
                j+=1
        elif i<len(A_pz):
            ans*=A_pz[i]
            i+=1
        else:
            ans*=B[j]
            j+=1
        ans%=MOD
    if i+j*2==K-2:
        if i<len(A_pz)-1 and j<len(B):
            ans*=max(A_pz[i]*A_pz[i+1],B[j])
        elif i<len(A_pz)-1:
            ans*=A_pz[i]*A_pz[i+1]
        else:
            ans*=B[j]
    elif i+j*2==K-1:
        if i<len(A_pz):
            ans*=A_pz[i]
        else:
            ans*=A_m[-1]
    ans%=MOD
print(ans)

Submission status: Wrong Answer

Solution code:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, k = MAP()

a = LIST()

pos = []
neg = []
zero = []

for el in a:
    if(el<0):
        neg.append(el)
    elif(el>0):
        pos.append(el)
    else:
        zero.append(el)

pos = sorted(pos)[::-1]
neg = sorted(neg)[::-1]

ans = 1

if(len(pos)==0):
    if(k%2==0):
        temp = 0
        for i in range(len(neg)-1, -1, -1):
            if(temp==k):
                break
            ans = (ans%mod*neg[i]%mod)%mod
            temp+=1
        if(temp>k):
            ans = 0
    else:
        temp = 0
        for i in range(len(neg) - 1):
            if (temp == k):
                break
            ans = (ans%mod * neg[i]%mod) % mod
            temp += 1
        if (temp > k):
            ans = 0
else:
    if(k==n):
        for el in a:
            ans = (ans%mod*el%mod)%mod
    else:
        left = k

        i,j = 0, len(neg)-1

        while(left>1):
            temp, temp1 = 0, 0
            if(i<len(pos)-2):
                temp = pos[i]*pos[i+1]
                # i+=2
            if(j>=1):
                temp1 = neg[j]*neg[j-1]
                # j-=2
            if(temp==0 and temp1==0):
                break
            if(temp1>temp):
                ans = (ans*(temp1%mod))%mod
                j-=2
            else:
                ans = (ans*(temp%mod))%mod
                i+=2
            left -= 2

        if(left>1):
            ans = 0
        elif(left==1):
            ans = ((ans%mod)*pos[i])%mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heappush
from collections import deque

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    mod = 7 + 10 ** 9
    q = []
    for a in A:
        if a < 0: heappush(q, (a, -1))
        else: heappush(q, (-a, 1))

    qu = deque()
    minus = 0
    plus = 1
    mc = 0
    ans = 1
    for i in range(K):
        a, pm = heappop(q)
        if pm == 1:
            ans *= plus
            ans %= mod
            plus = -a
        else:
            if mc == 1:
                ans *= (minus * a) % mod
                ans %= mod
            else:
                minus = a
            mc ^= 1
        qu.append((a, pm))
    if mc == 1:
        for i in range(K, N):
            a, pm = heappop(q)
            if pm == 1:
                ans *= (-a * plus) % mod
                ans %= mod
                print(ans)
                break
            else:
                ans *= (a * minus) % mod
                ans %= mod
                break
            qu.append((a, pm))
        else:
            ans = 1
            for i in range(K):
                a, pm = qu.pop()
                if pm == 1:
                    ans *= -a
                else:
                    ans *= a
                ans %= mod
            print(ans)
    else: 
        print((ans * plus) % mod)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
A.sort()
B = []
flag = False
F = False
tmp = 0
num = -1
ans = 1
tmp_ = -1
for i, a in enumerate(A):
    if a < 0:
        if flag:
            B.append(tmp * a)
            flag = False
        else:
            tmp = a
            flag = True
    elif a == 0:
        F = True
    else:
        tmp_ = tmp
        num = i
        break

if num == -1:
    if K % 2 == 1:
        for i, a in enumerate(A[::-1]):
            if i == K:
                print(ans)
                exit()
            ans *= a
            ans %= mod

A = A[num:]
A.sort(reverse=True)
if K % 2 == 1:
    ans = A[0]
    A = A[1:]
    K -= 1
ans %= mod
flag = False
for a in A:
    if flag:
        B.append(tmp * a)
        flag = False
    else:
        tmp = a
        flag = True
K //= 2
if len(B) < K:
    if F:
        print(0)
        exit()
    else:
        ans *= tmp_

B.sort(reverse=True)
for i, b in enumerate(B):
    if K == i:
        break
    ans *= b
    ans %= mod

print(ans)

Submission status: Wrong Answer

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


def choose(ans):
    if ans < 0:
        if a_list[-1]*a_list[-2] >= a_list[0]*a_list[1]:
            ans *= a_list.pop(0)
            ans *= a_list.pop(0)
        else:
            ans *= a_list.pop(-1)
            ans *= a_list.pop(-1)
    else:
        if a_list[-1]*a_list[-2] >= a_list[0]*a_list[1]:
            ans *= a_list.pop(-1) % MOD
            ans *= a_list.pop(-1) % MOD
        else:
            ans *= a_list.pop(0) % MOD
            ans *= a_list.pop(0) % MOD
    return ans 


ans = 1
if K == 1:
    print(a_list[-1]%MOD)
    exit()
else:
    if K % 2 == 0:
        for _ in range(K//2):
            ans = choose(ans) % MOD
            
    else:
        ans *= a_list.pop(-1)
        for _ in range((K-1)//2):
            ans = choose(ans) % MOD

print(ans%MOD)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jul  5 21:33:15 2020

"""

N, K = map(int,input().split())
A = list(map(int, input().split())) 
A = sorted(A, key=abs, reverse=True)
mod = 10**9+7
ans = 1
lp = 10**6
lm = 10**6
lpflag = 0
lmflag = 0
rp = 10**6
rm = 10**6
rpflag = 0
rmflag = 0
ans1 = 0
ans2 = 0
minus = 0
for i in range(K):
    if A[i] < 0:
        minus = (minus+1)%2
    ans = ans * A[i] % mod
if not minus:
    print(ans)
else:
    for i in range(K-1,-1,-1):
        if lp < 10**6 and lm < 10**6:
            break
        if A[i] > 0 and lpflag == 0:
            lpflag = 1
            lp = i
        elif A[i] < 0 and lmflag == 0:
            lmflag = 1
            lm = i
    for i in range(K,N):
        if rp < 10**6 and rm < 10**6:
            break
        if A[i] > 0 and rpflag == 0:
            rpflag = 1
            rp = i
        elif A[i] < 0 and rmflag == 0:
            rmflag = 1
            rm = i
    if lpflag*rmflag == 1:
        ans = 1
        for i in range(K):
            if not i == lpflag:
                ans = ans * A[i] % mod
        ans = ans * A[rmflag] % mod
        ans1 = ans
    if lmflag*rpflag == 1:
        ans = 1
        for i in range(K):
            if not i == lmflag:
                ans = ans * A[i] % mod
        ans = ans * A[rpflag] % mod    
        ans2 = ans
    if lpflag*rmflag == 0 and lmflag*rpflag == 0:
        ans = 1
        for i in range(N-1,N-1-K,-1):
            ans = ans * A[i] % mod
        print(ans)
    else:
        print(max(ans1,ans2))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

MOD = 10 ** 9 + 7


def MUL(a, b):
    return a * b % MOD


def main():

    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    res = 1
    if A[N - 1] == 0 and K % 2 == 1:
        print(0)
    elif A[N - 1] <= 0 and K % 2 == 1:
        for i in range(N - 1, N - K - 1, -1):
            res = MUL(res, A[i])
        if res < 0:
            res += MOD
    else:
        i = 0
        j = N - 1
        if K % 2 == 1:
            res = MUL(res, A[j])
            j -= 1
            K -= 1
        K >>= 1
        for p in range(K):
            left = A[i] * A[i + 1]
            right = A[j] * A[j - 1]
            if left > right:
                res = MUL(res, left)
                i += 2
            else:
                res = MUL(res, right)
                j -= 2
        if res < 0:
            res += MOD
    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def find(lst, k):
  for i in range(len(lst)):
    if lst[i] == k:
      return True
  return False
  

n, k = map(int, input().split())

lst = list(map(int, input().split()))

plus_list = []
minus_list = []
for i in range(n):
  if lst[i] >= 0:
    plus_list.append(lst[i])
  else:
    minus_list.append(lst[i])
    lst[i] = -1 * lst[i]
lst.sort()    
plus_list.sort()
minus_list.sort()
plus_Flag = True
ans_list = []
ans = 0
sum = 1
if k == 1:
  ans = lst[n-1]
else:
  for i in range(1, k+1):
      ans_list.append(lst[len(lst)-i])
      if find(minus_list, lst[len(lst)-i]) and not find(plus_list, lst[len(lst)-i]):
        plus_Flag = False 
  for i in range(len(ans_list)):
    ans *= ans_list[i]
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
A.sort(key=lambda x:-abs(x))
mod=10**9+7


ans=1
flg=1
flgcnt=0
save=1
for i in range(k-1):
    now=A[i]
    if now <0:
        flg*=-1
        flgcnt+=1
    ans=ans*abs(now)%mod
    if i==k-3:
        save=ans

#print(ans,flg)
for i in range(k-1,n):
    now=A[i]
    if now >=0:
        lasflg=1
    else:
        lasflg=-1
    if flg*lasflg==1:
        print(ans*abs(now)%mod)
        break
else:
    if flgcnt==k-1 and k>=2:
        ans=save
        two=2
        for i in range(k-2,n):
            now=A[i]
            if now>=0:
                two-=1
                ans=ans*abs(now)%mod
            if two==0:
                print(ans)
                break
        else:
            ans=1
            for i in range(k):
                ans=ans*A[n-1-i]%mod
            print(ans)
            
    else:
        ans=1
        for i in range(k):
            ans=ans*A[n-1-i]%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:
    for m in minus:
        if plus[0] < abs(m):
            plus.insert(0, m)
            continue
        for i in range(1, len(plus)-1):
            if plus[i] > abs(m) > plus[i+1]:
                plus.insert(i+1, m)
                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:
# 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])
            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)
            lpointer+=2
        else:
            product=(product*rproduct)
            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())
a = list(map(int, input().split()))

b = [(abs(i), 1 if i >= 0 else -1) for i in a]

b = sorted(b)
b = list(reversed(b))
mod = int(1e9 + 7)

def fp(x,y):
	res=1
	while y > 0:
		if y % 2 == 1:
			res *= x
		x *= x
		y //= 2
		x %= mod
		res %= mod
	return res

def inv(x):
	return fp(x,mod-2)

p = 1
signe = 1
for i in range(k):
	p *= b[i][0]
	p %= mod
	if b[i][0] == 0:
		signe = 0
	signe *= b[i][1]

if signe >= 0:
	print(p % mod)
else:
	# choice between replacing the last positive by the next negative
	# and replacing the last negative by the next positive
	lastP, nextP, lastN, nextN = -1, -1, -1, -1
	for i in range(k):
		if b[i][0] * b[i][1] >= 0:
			lastP = i
		if b[i][0] * b[i][1] <= 0:
			lastN = i
	for i in range(k, n):
		if b[i][0] * b[i][1] >= 0 and nextP==-1:
			nextP = i
		if b[i][0] * b[i][1] <= 0 and nextN==-1:
			nextN = i
	if (lastP!=-1 and nextN !=-1) and (lastN!=-1 and nextP!=-1):
		if b[nextN][0] * b[lastN][0] >= b[nextP][0] * b[lastP][0]:
			ans = p * inv(b[lastP][0]) * b[nextN][0]
			ans %= mod
			print(ans)
		else:
			ans = p * inv(b[lastN][0]) * b[nextN][0]
			ans %= mod
			print(ans)
	elif lastP!=-1 and nextN!=-1:
		ans = p * inv(b[lastP][0]) * b[nextN][0]
		ans %= mod
		print(ans)
	elif lastN!=-1 and nextP!=-1:
		ans = p * inv(b[lastN][0]) * b[nextP][0]
		ans %= mod
		print(ans)
	else:
		# tout le monde est negatif
		a = list(reversed(sorted(a)))
		p = 1
		for i in range(k):
			p *= a[i]
			p %= mod
		print(p)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from scipy.sparse.csgraph import floyd_warshall
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush, heapify
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    a.sort()
    ans = 1
    cnt = 0
    l = 0
    r = n-1
    x = bisect.bisect_left(a,0)
    y = bisect.bisect_right(a,0)
    flag = 0
    if n == 1:
        print(a[0]%mod)
        return
    if n == 2:
        if k == 1:
            print((max(a[0],a[1]))%mod)
        else:
            print(a[0]*a[1]%mod)
        return
    if k == n:
        if x%2 == 0:
            flag = 1
    elif k == n-1:
        if x == n:
            if k%2 == 0:
                flag = 1
        else:
            if x%2 == 1:
                flag = 1
            else:
                if x != n:
                    flag = 1
    else:
        if x == n:
            if k%2 == 0:
                flag = 1
        flag = 1
    if flag:
        while True:
            if a[l+1] >= 0:
                ans *= a[r]
                ans %= mod
                cnt += 1
                r -= 1
            else:
                if a[l]*a[l+1] >= a[r]*a[r-1] and cnt < k-1:
                    ans *= a[l]
                    ans *= a[l+1]
                    ans %= mod
                    cnt += 2
                    l += 2
                else:
                    ans *= a[r]
                    ans %= mod
                    cnt += 1
                    r -= 1
            if cnt == k:
                break
        print(ans)
    else:
        if 0 in a:
            print(0)
            return
        for i in range(n):
            a[i] = abs(a[i])
        a.sort()
        for i in range(k):
            ans *= a[i]
            ans %= mod
        ans *= -1
        ans %= mod
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
#t=int(input())
#d=defaultdict(int)
#for _ in range(t):
n,k=map(int,input().split())
l=list(map(int,input().split()))
l.sort(reverse=True)
p=1
for i in range(k):
  if l[i]==0:
    p=0
    break
  else:
    p*=l[i]%1000000007
print(p%1000000007)

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
P=1
if N==K:
  for i in range(N):
    P=P*A[i]%mod
  print(P)
  exit()
B=[]
C=False
for i in range(N):
  if A[i]:
    B.append(A[i])
  else:
    C=True
if len(B)<K:
  print(0)
  exit()
B.sort(reverse=True,key=lambda x:abs(x))
Y=0
for i in range(K):
  if B[i]<0:
    Y+=1
  P=P*B[i]%mod
if Y&1==0:
  print(P)
  exit()
if Y==K:
  B.sort()
  if B[-1]<0:
    if C:
      print(0)
      exit()
    P=1
    for i in range(K):
      P=P*B[-(i+1)]%mod
    print(P)
    exit()
  P=P*pow(B[0],mod-2,mod)*B[-1]%mod
  print(P)
  exit()
Y,Z=0,0
for i in range(K,len(B)):
  if B[i]<0:
    Y=B[i]
    break
for i in range(K,len(B)):
  if B[i]>0:
    Z=B[i]
    break
if Y==0:
  for i in range(K-1,-1,-1):
    if B[i]<0:
      P=P*pow(B[i],mod-2,mod)
      break
    if i==0:
      if C:
        print(0)
      else:
        print(P)
      exit()
  print(P*Z%mod)
elif Z==0:
  for i in range(K-1,-1,-1):
    if B[i]>0:
      P=P*pow(B[i],mod-2,mod)
      break
    if i==0:
      if C:
        print(0)
      else:
        print(P)
      exit()
  print(P*Y%mod)
if Y==0 or Z==0:
  exit()
V,W=0,0
for i in range(K-1,-1,-1):
  if B[i]<0:
    V=B[i]
    break
for i in range(K-1,-1,-1):
  if B[i]>0:
    W=B[i]
    break
if Y*V>Z*W:
  print(P*Y*pow(W,mod-2,mod)%mod)
else:
  print(P*Z*pow(V,mod-2,mod)%mod)

Submission status: Wrong Answer

Solution code:
import sys
def inv(a,m):
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

n,k=map(int,input().split())
mod=10**9+7
ax=list(map(int,input().split()))
a=[]

for i in range(n):
    if ax[i]>0: a.append([abs(ax[i]),1])
    elif ax[i]<0: a.append([abs(ax[i]),-1])
    else: a.append([0,0])
a=sorted(a,reverse=True)

if not -1 in [a[i][1] for i in range(n)]:
    ans=1
    for i in range(k):
        ans=ans*a[i][0]%mod
    print(ans)
    sys.exit()
if (1 not in [a[i][1] for i in range(n)]):
    ans=1
    for i in range(n-1,n-k-1,-1):
        ans=ans*a[i][0]%mod
    print(mod-ans)
    sys.exit()


lastp,lastm=-1,-1
cntm=0
ans=1
for i in range(k):
    [p,sgn]=a[i]
    ans*=p%mod
    if sgn==1: lastp=p
    elif sgn==-1:
        lastm=p
        cntm=cntm^1
if cntm==0 or ans==0: print(ans)
else:
    newp,newm=-1,-1
    for i in range(k+1,n):
        if a[i][1]==-1: newm=a[i][0];break
    for i in range(k+1,n):
        if a[i][1]>=0: newp=a[i][0];break

    x=1 if (lastp!=-1 and newm!=-1) else 0
    y=1 if (lastm!=-1 and newp!=-1) else 0
    if x==1 and y==1:
        if newp*lastp>=newm*lastm: ans=ans*inv(lastm,mod)*newp
        else: ans=ans*inv(lastp,mod)*newm
    elif x==-1 and y==1: ans=ans*inv(lastm,mod)*newp
    elif x==1 and y==-1: ans=ans*inv(lastp,mod)*newm
    print(ans)

Submission status: Wrong Answer

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

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)
#print(N)
for i in range(K):
    o=o*list[N-i-1]
#print(o)
if m > o:
    #if m > (10^9)+7:
    print(m%((10^9)+7))
    #else:
    #    print(m)
    #print("a")
else:
    #if o > (10^9)+7:
    print(o%((10^9)+7))
    #else:
    #print(o)
    #print(o%((10^9)+7))
    #print("b")