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:
from heapq import heappush,heappop,heapify
MOD = 10**9+7

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

hqp = []
hqm = []
for ai in a:
  if ai >= 0:
    heappush(hqp,-ai)
  else:
    heappush(hqm,ai)

ans = 1
if k-len(hqp) > 0 and (k-len(hqp))%2 == 1:
  hqp = []
  hqm = []
  for ai in a:
    if ai >= 0:
      heappush(hqp,ai)
    else:
      heappush(hqm,-ai)
  while(k > 0):
    if k > 1:
      if len(hqp) > 1 and len(hqm) > 1:
        if hqp[0]*hqp[1] > hqm[0]*hqm[1]:
          ans *= hqp[0]*hqp[1]
          heappop(hqp)
          heappop(hqp)
        else:
          ans *= hqm[0]*hqm[1]
          heappop(hqm)
          heappop(hqm)
      elif len(hqp) <= 1 and len(hqm) > 1:
        ans *= hqm[0]*hqm[1]
        heappop(hqm)
        heappop(hqm)
      elif len(hqp) > 1 and len(hqm) <= 1:
        ans *= hqp[0]*hqp[1]
        heappop(hqp)
        heappop(hqp)
      else:
        ans *= hqp[0]*-hqm[0]
        heappop(hqp)
        heappop(hqm)
      k -= 2
    else:
      if len(hqp) > 0:
        ans *= hqp[0]
        heappop(hqp)
      else:
        ans *= -hqm[0]
        heappop(hqm)
      k -= 1
    ans %= MOD
else:
  while(k > 0):
    if k > 1:
      if len(hqp) > 1 and len(hqm) > 1:
        if hqp[0]*hqp[1] > hqm[0]*hqm[1]:
          ans *= hqp[0]*hqp[1]
          heappop(hqp)
          heappop(hqp)
        else:
          ans *= hqm[0]*hqm[1]
          heappop(hqm)
          heappop(hqm)
      elif len(hqp) <= 1 and len(hqm) > 1:
        ans *= hqm[0]*hqm[1]
        heappop(hqm)
        heappop(hqm)
      elif len(hqp) > 1 and len(hqm) <= 1:
        ans *= hqp[0]*hqp[1]
        heappop(hqp)
        heappop(hqp)
      else:
        ans *= -hqp[0]*hqm[0]
        heappop(hqp)
        heappop(hqm)
      k -= 2
    else:
      if len(hqp) > 0:
        ans *= -hqp[0]
        heappop(hqp)
      else:
        ans *= hqm[0]
        heappop(hqm)
      k -= 1
    ans %= MOD
print(ans)

Submission status: Wrong Answer

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

mod = 10**9 + 7

minus = []
plus = []
zero = []
new_ls = []
for i in ls:
    if i > 0:
        plus.append(i)
        new_ls.append(i)
    elif i < 0:
        minus.append(i)
        new_ls.append(-i)
    else:
        zero.append(i)
        new_ls.append(i)

ans = 1
new_ls.sort()
minus.sort()
plus.sort()
if (len(plus) == 0 and k%2 == 1) or (len(minus)%2 == 1 and k == n):
    if len(zero) != 0:
        ans = 0
    else:
        for i in range(k):
            ans *= -new_ls[i]
            ans %= mod
elif k%2 == 0:
    m_ind = 0
    p_ind = 0
    for i in range(k//2):
        if m_ind+1 < len(minus) and p_ind+1 < len(plus):
            if minus[m_ind] * minus[m_ind+1] > plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]:
                ans *= minus[m_ind] * minus[m_ind+1]
                ans %= mod
                m_ind += 2
            else:
                ans *= plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]
                ans %= mod
                p_ind += 2
        elif m_ind+1 < len(minus):
            ans *= minus[m_ind] * minus[m_ind+1]
            ans %= mod
            m_ind += 2
        elif p_ind+1 < len(plus):
            ans *= plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]
            ans %= mod
            p_ind += 2
        #else:
else:
    m_ind = 0
    p_ind = 0
    for i in range(k//2):
        if m_ind+1 < len(minus) and p_ind+1 < len(plus):
            if minus[m_ind] * minus[m_ind+1] > plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]:
                ans *= minus[m_ind] * minus[m_ind+1]
                ans %= mod
                m_ind += 2
            else:
                ans *= plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]
                ans %= mod
                p_ind += 2
        elif m_ind+1 < len(minus):
            ans *= minus[m_ind] * minus[m_ind+1]
            ans %= mod
            m_ind += 2
        elif p_ind+1 < len(plus):
            ans *= plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]
            ans %= mod
            p_ind += 2
        #else:
    ans *= plus[len(plus)-p_ind-1]
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
MOD = int(1e9+7)
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
flag = 0
for a in A:
    if a>0:
        flag = 1
        break
#すべてマイナスか0
if flag == 0 and K%2==1:
    A.sort(reverse = True)
    ans = 1
    for i in range(K):
        ans = (ans*A[i]) % MOD
    print(ans)
#それ以外
else:
    A = sorted(A, key=abs, reverse = True)
    last_pos = -1
    last_neg = -1
    count_neg = 0
    is_zero = 0
    ans = 1
    for i in range(K):
        ans = (ans*A[i]) % MOD
        if A[i]>0:
            last_pos = i
        elif A[i]<0:
            last_neg = i
            count_neg += 1
        else:
            is_zero = 1
            break
    if is_zero == 1:
        print(0)
    elif count_neg%2 == 0:
        print(ans)
    else:
        flag_pos = 0
        flag_neg = 0
        new_pos = -1
        new_neg = -1
        for i in range(K,N):
            if A[i]>0 and flag_pos==0:
                flag_pos = 1
                new_pos = i
            elif A[i]<0 and flag_neg==0:
                flag_neg = 1
                new_neg = i
            if flag_pos == 1 and flag_neg == 1:
                break

        if last_pos > -1 and last_neg > -1 and new_pos > -1 and new_neg > -1:
            f1 = - A[new_pos] * A[last_pos]
            f2 = - A[new_neg] * A[last_neg]
            if f1>f2:
                ans = 1
                for i in range(K):
                    if i != last_neg:
                        ans = (ans*A[i]) % MOD
                ans = (ans*A[new_pos]) % MOD
            else:
                ans = 1
                for i in range(K):
                    if i != last_pos:
                        ans = (ans*A[i]) % MOD
                ans = (ans*A[new_neg]) % MOD
        elif last_pos > -1 and new_neg > -1:
            ans = 1
            for i in range(K):
                if i != last_pos:
                    ans = (ans*A[i]) % MOD
            ans = (ans*A[new_neg]) % MOD
        elif last_neg > -1 and new_pos > -1:
            ans = 1
            for i in range(K):
                if i != last_neg:
                    ans = (ans*A[i]) % MOD
            ans = (ans*A[new_pos]) % MOD
        else:
            ans = 0
            
        print(ans)

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

if N == 1:
    print(A[0]%mod)
else:
    if K == 1:
        print(max(A)%mod)
        exit()

    if all([a<0 for a in A]) and K%2:
        ans = 1
        for i in range(1,K+1):
            ans *= abs(A[-i])
            ans %= mod
        print(-ans%mod)
    else:
        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
            if N == K:
                print(-ans%mod)
                exit()

            ans1 = -float('inf')
            ans2 = -float('inf')

            #Aが正負を一つずつもつならどっかに引っかかる(と思う)
            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')
            ans = max(ans1,ans2)
            print(ans%mod)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n, k = inpl()
a = inpl()
data = [[abs(i), i < 0] for i in a]
all_minus = 0
for t in data:
    if t[1]:
        all_minus += 1
if all_minus == n:
    ans = 1
    data.sort()
    for i in range(k):
        ans = ans * data[i][0] % mod
    print(-ans % mod)
    exit()
data.sort(reverse=True)
last_minus = 0
last_plus = 0
ans = 1
minus_amount = 0
for i in range(k):
    elem, sign = data[i][0], data[i][1]
    if elem == 0:
        print(0)
        exit()
    ans = ans * elem % mod
    minus_amount += sign
    if sign:
        last_minus = elem
    else:
        last_plus = elem
if minus_amount % 2 == 0:
    print(ans%mod)
    exit()
if n==k:
    print(-ans % mod)
    exit()
tmp_plus = 0
tmp_minus = 0
for i in range(k, n):
    elem, sign = data[i][0], data[i][1]
    if last_plus and sign and not tmp_minus:
        tmp_minus = elem
    elif last_minus and not sign and not tmp_plus:
        tmp_plus = elem
if tmp_plus == 0 and tmp_minus == 0:
    ans = 0
elif last_plus == 0:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
elif last_minus == 0:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
elif tmp_plus * last_plus > tmp_minus * last_minus:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
else:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
print(ans)

Submission status: Wrong Answer

Solution code:
from typing import Reversible


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

A.sort(key=lambda x: abs(x),reverse=True)
if N - K < A.count(0):
    print(0)
    exit()
if all(a <= 0 for a in A):
    if 0 in A:
        print(0)
    else:
        ans = 1
        A.sort(reverse=True)
        for a in A[:K]:
            ans = ans * a % mod
        print(ans)
    exit()
minus1 = 0
minus2 = 0
ans1 = 1
ans2 = 0
last_minus = 1
last_plus = -1
n = 0
for a in A:
    if a == 0:
        continue
    n += 1
    ans1 = ans1 * a % mod
    if a < 0:
        minus1 += 1
        last_minus = a
    if n == K:
        if minus1 % 2 != 0:
            ans1 = ans1 * pow(last_minus, mod-2, mod) % mod
            n -= 1
            minus1 -= 1
        else:
            break
for a in A:
    if a == 0:
        continue
    n += 1
    ans2 = ans2 * a % mod
    if a < 0:
        minus2 += 1
    else:
        last_plus = a
    if n == K:
        if minus2 % 2 != 0:
            ans2 = ans2 // last_plus % mod
            n -= 1
        else:
            break
print(max(ans1, ans2))

Submission status: Wrong Answer

Solution code:
a = list(map(int, input().split(" ")))
N = a[0]
K = a[1]
if K % 2 == 1:
    k = int(K / 2 - 1)
    end = 1
else:
    k = int(K / 2)
    end = 0
max_ = 1
mi = 0
pl = 0
A = list(map(int, input().split(" ")))
if N == K:
    for i in range(N):
        max_ *= A[i]
else:
    if K % 2 == 1 and A[-1] <= 0:
        for i in range(K):
            max_ *= A[i]
    else:
        for i in range(k):
            if A[0] * A[1] == A[-1] * A[-2]:
                try:
                    if A[2] * A[3] >= A[-3] * A[-4]:
                        max_ *= A[0] * A[1]
                        A.pop(0)
                        A.pop(1)
                    else:
                        max_ *= A[-1] * A[-2]
                        A.pop(-1)
                        A.pop(-2)
                except IndexError:
                    max_ *= A[0] * A[1]
                    A.pop(0)
                    A.pop(1)
            elif A[0] * A[1] > A[-1] * A[-2]:
                max_ *= A[0] * A[1]
                A.pop(0)
                A.pop(1)
            elif A[0] * A[1] <= A[-1] * A[-2]:
                max_ *= A[-1] * A[-2]
                A.pop(-2)
                A.pop(-1)
        if end == 1:
            max_ *= A[-1]
print(max_ % 1000000007)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
MOD = 10**9 + 7
A = list(map(int,input().split()))
Ap = [a for a in A if a >= 0]
An = [-a for a in A if a < 0]
Ap.sort()
Ap.reverse()
An.sort()
An.reverse()

if len(Ap) == 0 and K % 2 == 1:
	ans = 1
	An.reverse()
	for i in range(K):
		ans = (ans * -An[i]) % MOD
	print(ans)
	exit()

B = [(a, 1) if a >= 0 else (-a, -1) for a in A]
B.sort()
B.reverse()
M = [0 if B[0][1] > 0 else 1]
for i in range(1, N):
	M.append(M[i-1] + (0 if B[i][1] > 0 else 1))

i = K-1
if M[i] % 2 == 0 or K == N:
	ans = 1
	for j in range(K):
		ans = (ans * B[j][0] * -1 * (M[i]%2)) % MOD
	print(ans)
else:
	n = M[i]
	p = K - n
	if len(An) == n or p == 0:
		n -= 1
		p += 1
	elif len(Ap) == p:
		n += 1
		p -= 1
	elif Ap[p-1] * Ap[p] >= An[n-1] * An[n]:
		n -= 1
		p += 1
	else:
		n += 1
		p -= 1
	ans = 1
	for i in range(p):
		ans = (ans * Ap[i]) % MOD
	for i in range(n):
		ans = (ans * An[i]) % MOD
	print(ans)

Submission status: Wrong Answer

Solution code:
from functools import reduce
from operator import mul

mod = 1000000007

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

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

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


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

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9 + 7
b_p = []
b_n = []
ab = []
for i in range(n):
    ab.append(abs(a[i]))
    if a[i] >= 0:
        b_p.append(a[i])
    else:
        b_n.append(a[i])
b_p = sorted(b_p,reverse=True)
b_n = sorted(b_n)
ab = sorted(ab)
ans = 1
i = 0
x = 0
y = 0
if k%2 == 1:
    if len(b_p) >= 1:
        ans *= b_p[0]
        x += 1
        i += 1
while i < k-1:
    i += 2
    if x < len(b_p)-1 and y < len(b_n)-1:
        if b_p[x]*b_p[x+1] > b_n[y]*b_n[y+1]:
            ans *= b_p[x]*b_p[x+1]
            ans %= mod
            x += 2
        else:
            ans *= b_n[y]*b_n[y+1]
            ans %= mod
            y += 2
    
    elif x < len(b_p)-1:
        ans *= b_p[x]*b_p[x+1]
        ans %= mod
        x += 2
    elif y < len(b_n)-1:
        ans *= b_n[y]*b_n[y+1]
        ans %= mod
        y += 2
    else:
        break
if i != k:
    if 0 in b_p:
        ans = 0
    else:
        ans = 1
        for i in range(k):
            ans *= ab[i]
            ans %= mod
        ans *= -1
print(ans%mod)

Submission status: Wrong Answer

Solution code:

# Author : raj1307 - Raj Singh
# Date   : 05.07.2020

from __future__ import division, print_function

import os,sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def ii():  return int(input())
def si():  return input()
def mi():  return map(int,input().strip().split(" "))
def msi(): return map(str,input().strip().split(" "))
def li():  return list(mi())

def dmain():
    sys.setrecursionlimit(1000000)
    threading.stack_size(1024000)
    thread = threading.Thread(target=main)
    thread.start()
    
#from collections import deque, Counter, OrderedDict,defaultdict
#from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace
#from math import log,sqrt,factorial,cos,tan,sin,radians
#from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
#from decimal import *
#import threading
#from itertools import permutations
#Copy 2D list  m = [x[:] for x in mark] .. Avoid Using Deepcopy

abc='abcdefghijklmnopqrstuvwxyz'
abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod=1000000007
#mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]
def getKey(item): return item[1] 
def sort2(l):return sorted(l, key=getKey,reverse=True)
def d2(n,m,num):return [[num for x in range(m)] for y in range(n)]
def isPowerOfTwo (x): return (x and (not(x & (x - 1))) )
def decimalToBinary(n): return bin(n).replace("0b","")
def ntl(n):return [int(i) for i in str(n)]
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))

def ceil(x,y):
    if x%y==0:
        return x//y
    else:
        return x//y+1

def powerMod(x,y,p):
    res = 1
    x %= p
    while y > 0:
        if y&1:
            res = (res*x)%p
        y = y>>1
        x = (x*x)%p
    return res

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x
    
def isPrime(n) : # Check Prime Number or not 
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
    return True



def read():
    sys.stdin  = open('input.txt', 'r')  
    sys.stdout = open('output.txt', 'w') 




def main():
    


    #for _ in range(ii()):


    n,k=mi()
    a=li()
    if n==k:
        ans=1
        for i in range(n):

            x=(a[i]%mod+mod)%mod;
            ans=(ans*x)%mod
        print(ans)
        return


    x=[]
    y=[]

    for i in range(n):
        if a[i]<0:
            y.append(a[i])
        else:
            x.append([a[i],1])

    neg=[]


    y.sort()
    ex=-1

    for i in range(0,len(y),2):
        if i==len(y)-1:
            ex=y[i]
            continue

        x.append([y[i]*y[i+1],2])



    x.sort(reverse=True)
   


    ans=1
    cnt=0


    p=[]
    q=[]

    ext=-1


    for i in range(len(x)):
        #print(cnt,x[i][1],cnt)


        if cnt+x[i][1]<=k:

            if x[i][1]==1:
                p.append(x[i][0])
            else:
                q.append(x[i][0])

            ans=(ans*x[i][0])%mod
            cnt+=x[i][1]

        elif cnt!=k:

            ext=max(ext,x[i][0])



    if cnt==k:
        print(ans)
        return



    if len(p)!=0:

        ans=1

        for i in range(len(p)-1):
            ans=(ans*p[i])%mod
        for j in range(len(q)):
            ans=(ans*q[j])%mod
        ans=ans*ext
        ans%=mod
        print(ans)
        return

    ans=1
    cnt=0
    for i in range(len(y)-1,-1,-1):
        if cnt==k:
            break

        x=(mod+y[i]%mod)%mod
        ans*=x
        ans%=mod
        cnt+=1

    print(ans)












    









    








# region fastio
# template taken from https://github.com/cheran-senthil/PyRival/blob/master/templates/template.py

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        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")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion


if __name__ == "__main__":
    #read()
    main()
    #dmain()

# Comment Read()

Submission status: Wrong Answer

Solution code:
mod1,mod2=10**9+7,998244353
mod=mod1
n,k=map(int,input().split())
p,m=[],[]
for i in list(map(int,input().split())):
    if i<0:m.append(i)
    elif i>0:p.append(i)
if len(p)+len(m)<k:
    print(0)
elif len(p)==0:
    m.sort()
    ans=1
    for i in range(k):ans=(ans*m[-1-i])%mod
    print(ans)
else:
    p.sort()
    m.sort()
    ans=0
    c=1
    v={0:1}
    for i in range(min(len(p),k)):
        c*=p[-1-i]
        v[i+1]=c
    if k in v:
        ans=max(ans,v[k])
    x=1
    for i in range(1,min(len(m),k)+1):
        x*=-m[i-1]
        if i%2==0 and k-i in v:
            ans=max(ans,v[k-i]*x)
    print(ans%mod)

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]
    if neg:
        ans *= -b
    else:
        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:
            assert last_neg != 1
            ans *= pow(last_neg, mod - 2, mod)
        else:
            if last_nneg != -1:
                ans *= pow(last_nneg, mod - 2, mod)
            else:
                ans *= pow(last_neg, mod - 2, mod)
                ans *= pow(-b, mod - 2, mod)
                for j in range(k + 1, n):
                    if not A[j][1]:
                        ans *= A[j][0]
                        break
        ans %= mod
        print(ans)
        exit()

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

for i in range(K):
    res *= A[i]
    if A[i] < 0:
        last_minus_index = i
    if A[i] > 0:
        last_plus_index = i

if res >= 0:
    print(res % mod)
    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:
import numpy as np

MOD = 10**9 + 7
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
ans = 1
plus = a[a >= 0]
plus = np.sort(plus)[::-1]
plus = np.append(plus, [-np.inf, np.inf])
minus = a[a < 0]
minus = np.sort(minus)
minus = np.append(minus, [np.inf, -np.inf])
if n == k:
    for i in range(len(a)):
        ans *= a[i]
        ans %= MOD
    print(ans)
    exit()
if len(plus) == 2 and k % 2 == 1:
    for i in range(3, k + 3):
        ans *= minus[-i]
        ans %= MOD
else:
    if k % 2 == 1:
        p = k // 2
        ans *= plus[0]
        cplus = 1
        cminus = 0
    else:
        p = k // 2
        cplus = 0
        cminus = 0
    for l in range(p):
        if plus[cplus] * plus[cplus + 1] > minus[cminus] * minus[cminus + 1]:
            ans *= plus[cplus] * plus[cplus + 1]
            ans %= MOD
            cplus += 2
        else:
            ans *= minus[cminus] * minus[cminus + 1]
            ans %= MOD
            cminus += 2
print(int(ans))

Submission status: Wrong Answer

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

A.sort()

def get_pos_num():
    lb = -1
    ub = N

    while ub - lb > 1:
        mid = (ub + lb) // 2
        if A[mid] > 0:
            ub = mid
        else:
            lb = mid

    return ub

def get_neg_num():
    lb = -1
    ub = N

    while ub - lb > 1:
        mid = (ub + lb) // 2
        if A[mid] >= 0:
            ub = mid
        else:
            lb = mid

    return lb

pos_num = get_pos_num()
neg_num = get_neg_num()
# A[0], A[1], ... , A[neg_num] <- negative number
# A[neg_num + 1], ..., A[pos_num - 1] <- 0
# A[pos_num], ..., A[N-1] <- positive number

neg_ind = 0
pos_ind = N-1
ans = 1

if (N-1) - neg_ind < K or K % 2 == 0:
    while K > 0:
        if K >= 2:
            if pos_ind < pos_num:
                pos_tmp = -1*INF
            else:
                pos_tmp = A[pos_ind]*A[pos_ind-1]

            if neg_ind > neg_num:
                neg_tmp = -1 * INF
            else:
                neg_tmp = A[neg_ind]*A[neg_ind+1]

            if pos_tmp < neg_tmp:
                neg_ind += 2
                ans = (ans * neg_tmp + MOD) % MOD

                # ans *= neg_tmp
                K -= 2
            else:
                pos_ind -= 2
                ans = (ans * pos_tmp + MOD) % MOD

                # ans *= pos_tmp
                K -= 2
        
        else:
            ans = (ans * A[pos_ind] + MOD) % MOD
            # ans *= A[pos_ind]
            K -= 1
else:
    for i in range(K):
        ans = (ans * A[N-1-i] + MOD) % MOD
        # ans *= A[N-1-i]

print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
list=list(map(int,input().split()))
list.sort()
all_negative = True
if list[len(list)-1]>=0:
    all_negative = False
if all_negative and k%2!=0:
    list.sort(reverse=True)
    prod = 1
    for i in range(k):
        prod*=list[i]
    print(prod%1000000007)
else:
    temp=k
    for i in range(0,len(list),2):
        if temp<2:
            break
        if list[i]<0 and i+1!=len(list) and list[i+1]<0:
            list[i]*=-1
            list[i+1]*=-1
            temp-=2
    list.sort(reverse=True)
    prod = 1
    for i in range(k):
        prod*=list[i]
    print(prod % 1000000007)

Submission status: Wrong Answer

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

mod = 10**9+7
def _ans(_a):
    ret = _a[0]
    for _aa in _a[1:]:
        ret = (ret*_aa)%mod
    return ret


a = list(map(int, input().split()))
# マイナスでも全部かけるしかない
if len(a) == k:
    print(_ans(a))
    exit(0)

ap = [aa for aa in a if aa > 0]
an = [aa for aa in a if aa < 0]
apl, anl = len(ap), len(an)

# 0が入る
if apl + anl < k:
    print(0)
    exit(0)

ap.sort(reverse=True)
an.sort()

# プラスがない
if apl == 0:
    if k % 2 == 1:
        an = an[::-1]
    print(_ans(an[:k]))
    exit(0)

# マイナスは2の倍数個のみいれる
ans = 1
api, ani = 0, 0
if k % 2 == 1:
    ans = ap[0]
    api += 1
    k -= 1

while k > 0:
    if apl - api < 2:
        while k > 0:
            ans = (ans * an[ani] * an[ani+1]) % mod
            ani += 2
            k -= 2
        break
    if anl - ani < 2:
        while k > 0:
            ans = (ans * ap[api] * ap[api+1]) % mod
            api += 2
            k -= 2
        break

    app = ap[api] * ap[api+1]
    ann = an[ani] * an[ani+1]
    if app > ann:
        ans = (ans * app) % mod
        api += 2
    else:
        ans = (ans * ann) % mod
        ani += 2
    k -= 2

print(ans)