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:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,K = IL()
A = IL()
A = sorted(A,key= lambda x:-abs(x))
S = [a//abs(a) if abs(a)!=0 else 0 for a in A]

count_M = 0
last_M = None
last_P = None
for i in range(K):
  if S[i] == 0:
    print(0)
    exit()
  if S[i] == -1:
    last_M = i
    count_M += 1
  if S[i] == 1:
    last_P = i

if count_M%2 == 0:
  ans = 1
  for i in range(K):
    ans *= A[i]
    ans %= MOD
  print(ans)
  exit()
else:
  if last_M!=None:
    for i in range(K,N):
      if S[i] == 1:
        ans = 1
        for ii in range(K):
          if ii != last_M:
            ans *= A[ii]
            ans %= MOD
        ans *= A[i]
        ans %= MOD
        print(ans)
        exit()
  if last_P!=None:
    for i in range(K,N):
      if S[i] == -1:
        ans = 1
        for ii in range(K):
          if ii != last_P:
            ans *= A[ii]
            ans %= MOD
        ans *= A[i]
        ans %= MOD
        print(ans)
        exit()
  if A[-1] == 0:
    print(0)
    exit()
  else:
    ans = 1
    for i in range(K):
      ans *= A[N-1-i]
      ans %= MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def cal(xx):
    res=1
    for x in xx:
        res=res*x%md
    return res

md=10**9+7
n,k=MI()
aa=LI()
if n==k:
    print(cal(aa))
    exit()
aa.sort(key=lambda x:-abs(x))
#print(aa)
pre=aa[:k]
pos=aa[k:]
mnp=mnn=md
mnpi=mnni=-1
neg=0
for i,a in enumerate(pre):
    if a==0:
        print(0)
        exit()
    if a<0:neg+=1
    if a>0 and a<mnp:
        mnp=a
        mnpi=i
    if a<0 and -a<mnn:
        mnn=-a
        mnni=i
if neg%2:
    mxp=mxn=0
    for a in pos:
        if a > 0 and a > mxp:
            mxp = a
        if a < 0 and -a > mxn:
            mxn = -a
    if (mnni!=-1 and mxp) or (mnpi!=-1 and mxn):
        if mxp*mnp>mxn*mnn:pre[mnni]=mxp
        else:pre[mnpi]=-mxn
    else:
        aa.sort(key=lambda x: abs(x))
        pre=aa[:k]

print(cal(pre))

Submission status: Wrong Answer

Solution code:
# N = int(input())
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
MOD = 10 ** 9 + 7
A_abs = [[abs(a), True] if a >= 0 else [abs(a), False] for a in A]
A_abs.sort(reverse=True)
ans = 1
count_n = 0
for i in range(K-1):
  ans = (ans * A_abs[i][0]) % MOD
  if not A_abs[i][1]:
    count_n += 1
for i in range(K-1, N):
  if count_n % 2 == 0 and A_abs[i][1] or A_abs[i][0] == 0:
    ans = (ans * A_abs[i][0]) % MOD
    break
  if count_n % 2 == 1 and not A_abs[i][1] or A_abs[i][0] == 0:
    ans = (ans * A_abs[i][0]) % MOD
    break
else:
  A_abs.sort()
  ans = 1
  for i in range(K):
    ans = (ans * A_abs[i][0]) % MOD
  ans = (-ans) % MOD
print(ans)

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)
    x.sort(reverse=1)
    y.sort()
    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:
        c=1
        for i in x+y[::-1][:k-len(x)]:
            c=c*i%M
        print(c)
        exit()
    x=x[:k]
    i=len(x)
    if i<k:
        j=k-i
        x+=y[:j]
        y=y[j:]
    m=len(y)
    j=0
    while i>1 and j+1<m:
        if 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, = 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 and first_minus_outof_k:
            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:
            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:
            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:
from math import log2

N, K = map(int, input().split())
A = [int(i) for i in input().split()]

mod = 10 ** 9 + 7

p = []
m = []
for a in A :
  if a > 0 :
    p.append(a)
  elif a < 0 :
    m.append(-a)
    
p.sort(reverse=True)
m.sort(reverse=True)
pl = [0]
ml = [0]

for i in range(len(p)) :
  pl.append(log2(p[i]))
for i in range(len(m)) :
  ml.append(log2(m[i]))
for i in range(1, len(pl)) :
  pl[i] += pl[i - 1]
for i in range(1, len(ml)) :
  ml[i] += ml[i - 1]

Mi = -1
Mv = 0
for i in range(0, len(ml), 2) :
  j = K - i
  if len(pl) <= j or j < 0 : continue
  if ml[i] + pl[j] > Mv :
    Mi, Mv = i, ml[i] + pl[j]

if Mi != -1 :
  ret = 1
  for i in range(K - Mi) :
    ret *= p[i]
    ret %= mod
  for i in range(Mi) :
    ret *= m[i]
    ret %= mod
else :
  x = [abs(a) for a in A]
  x.sort()
  ret = 1
  for i in range(K) :
    ret *= x[i]
    ret %= mod
  ret = -ret % mod
  
print(ret)

Submission status: Wrong Answer

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


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


mod = 10 ** 9 + 7

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

if flg == 0:
    A.reverse()


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


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


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

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

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def solve(N: int, K: int, A: "List[int]"):
    nn = 0
    ns = []
    ps = []
    for a in A:
        if a <= 0:
            nn += 1
            ns.append(a)
        else:
            ps.append(a)
    pp = N - nn
    if N == K or nn == N:
        A.sort(reverse=True)
        ret = 1
        for i in range(K):
            ret *= A[i]
            ret %= MOD
    elif pp < K: # pp > 0
        min_nn = K - pp
        if min_nn % 2 and min_nn < nn:
            min_nn += 1
        ns.sort()
        ret = 1
        for i in range(min_nn):
            ret *= ns[i]
            ret %= MOD
        if min_nn % 2:
            ps.sort(reverse=True)
        else:
            ps.sort(reverse=True)
        for i in range(K - min_nn):
            ret *= ps[i]
            ret %= MOD
    else: # pp >= K
        ret = 1
        A.sort(key=lambda x: abs(x), reverse=True)
        neg = []
        for i in range(K):
            if A[i] > 0:
                ret *= A[i]
                ret %= MOD
            else:
                neg.append(A[i])
        if len(neg) % 2 == 0:
            for ne in neg:
                ret *= ne
                ret %= MOD
        else:
            for ne in neg[:-1]:
                ret *= ne
                ret %= MOD
            for i in range(K, N):
                if A[i] > 0:
                    ret *= A[K]
                    ret %= MOD
                    break
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft



def main():
    n, k = map(int, input().split())
    a = sorted([(abs(i), (1 if i > 0 else -1)) for i in map(int, input().split())], reverse=True)
    if n == k:
        s = 1
        for x in a:
            s = s * x[0] * x[1] % mod
        print(s)
        return
    if len([i for i in a if i[1] == -1]) == n:
        if k % 2 == 0:
            s = 1
            for i in a[:k]:
                s = (s * i[0]) % mod
            print(s)
        else:
            s = 1
            for i in a[-k:]:
                s = (s * i[0]) % mod
            print((-s) % mod)
        return
    s = 1
    c = 1
    for i in range(k):
        s = s * a[i][0] % mod
        c *= a[i][1]
    if c == 1:
        print(s)
        return
    j = 0
    for i in range(k, n):
        if a[i][1] == -1:
            j = i
            break
    s = (s * inverse(a[j][0])) % mod
    for i in range(k, n):
        if a[i][1] == 1:
            print(s * a[i][0] % mod)
            return

main()

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    mod = 10 ** 9 + 7
    A = list(map(int, input().split()))
    P = [a for a in A if a >=0]
    M = [a for a in A if a < 0]
    PP, MM = len(P), len(M)
    P.sort(reverse=True)
    M.sort()
    k = 0
    p, m = 0, 0
    while p + m < K:
        if m == MM:
            p += 1
        elif p == PP:
            m += 1
        elif P[p] > -M[m]:
            p += 1
        else:
            m += 1
    if m % 2 != 0:
        if m == MM:
            m -= 1
            p += 1
        elif p == PP:
            m += 1
            p -= 1
        elif M[m - 1] * M[m] >= P[p - 1] * P[p]:
            m += 1
            p -= 1
        else:
            m -= 1
            p += 1
    def prod(l):
        r = 1
        for a in l:
            r = (r * a) % mod
        return r
    if p < 0:
        return prod(M[-K:])
    return prod(P[:p] + M[:m]) 

print(main())

Submission status: Wrong Answer

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


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


mod = 10 ** 9 + 7

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

if flg == 0:
    A.reverse()


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


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


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

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

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

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
LIST = list(map(int, input().split()))
LIST = sorted(LIST)
ans1 = 1
ans2 = 1
for i in range(abs(len(LIST)-K),len(LIST)):
    ans1 *= LIST[i]
for i in range(abs(len(LIST)-K)):
    ans2 *= LIST[i]
if ans1 >ans2:  
    print(ans1%((10**9)+7))
else:
    print(ans2%((10**9)+7))

Submission status: Wrong Answer

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

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

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

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


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

use_minus=min(K, (len(minus)//2)*2)
use_plus=K-use_minus

mul=1
for i in minus[:use_minus]:
    mul*=i
for i in plus[:use_plus]:
    mul*=i
retval=mul
while use_plus<=len(plus)-2 and use_minus>=2:
    use_minus-=2
    mul=mul//(minus[use_minus]*minus[use_minus+1])
    mul*=(plus[use_plus]*plus[use_plus+1])
    use_plus+=2
    retval=max(retval,mul)

print(retval%(10**9+7))

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
mn = []
zr = 0
pl = []
t = []
for x in a:
  if x < 0:
    mn.append(-x)
    t.append((-x, 0))
  elif x == 0: zr += 1
  else:
    pl.append(x)
    t.append((x, 1))

if N - zr < K:
  print(0)
  exit(0)

t.sort(reverse = True)
#print(t)
c = 0
res = 1
lpl = -1
for x, cc in t[: K]:
  res *= x
  res %= mod
  c ^= (cc == 0)
  if cc: lpl = x
if c == 0:
  print(res)
  exit(0)
for x, cc in t[K: ]:
  if lpl == -1: break
  if cc == 0:
    res *= pow(lpl, mod - 2, mod)
    res %= mod
    res *= x
    res %= mod
    print(res)
    exit(0)
if len(pl) >= K:
  res = 1
  for x in pl[: K]:
    res *= x
    res %= mod
  print(res)
  exit(0)
if zr:
  print(0)
  exit(0)
res = 1
t.reverse()
for x, _ in t[: K]:
  res *= x
  res %= mod
print(-res % mod)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
def main():
    n, k = map(int, input().split())# 正0でコーナー
    a = list(map(int, input().split()))
    pos = []
    neg = []
    zero = []
    for v in a:
        if v == 0:
            zero.append(v)
        elif 0 < v:
            pos.append(v)
        else:
            neg.append(v)
    if len(pos) + len(neg) < k:
        print(0)
    else:
        if k%2 == 0:
            if len(pos) + len(neg) == k and len(pos) % 2 == 1:#負になる
                if len(zero) > 0:
                    print(0)
                else:
                    ans = 1
                    for v in pos:
                        ans *= v
                        ans %= MOD
                    for v in neg:
                        ans *= v
                        ans %= MOD
                    print(ans % MOD)
            else:
                pos.sort(reverse=True)
                neg.sort()
                for i in range(1, len(pos)):
                    pos[i] *= pos[i-1]
                    pos[i] %= MOD
                for i in range(1, len(neg)):
                    neg[i] *= neg[i-1]
                    neg[i] %= MOD
                ans = 0
                for i in range(0, k+1, 2):
                    if len(pos) < i or len(neg) < k-i:
                        continue
                    tmp = 1
                    if 0 < i:
                        tmp *= pos[i-1]
                    if 0 < k-i:
                        tmp *= neg[k-i-1]
                    tmp %= MOD
                    if ans < tmp:
                        ans = tmp
                print(ans)
        else:
            if 0 == len(pos):
                if 0 < len(zero):
                    print(0)
                else:
                    neg.sort(reverse=True)
                    ans = 1
                    for i in range(k):
                        ans *= neg[i]
                        ans %= MOD
                    print(ans)
            else:
                pos.sort(reverse=True)
                neg.sort()
                for i in range(1, len(pos)):
                    pos[i] *= pos[i-1]
                    pos[i] %= MOD
                for i in range(1, len(neg)):
                    neg[i] *= neg[i-1]
                    neg[i] %= MOD
                ans = 0
                for i in range(1, k+1, 2):
                    if len(pos) < i or len(neg) < k-i:
                        continue
                    tmp = 1
                    if 0 < i:
                        tmp *= pos[i-1]
                    if 0 < k-i:
                        tmp *= neg[k-i-1]
                    tmp %= MOD
                    if ans < tmp:
                        ans = tmp
                print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

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

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

    positives = 0
    zeros = 0
    negatives = 0

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

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

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

main()

Submission status: Wrong Answer

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

a_plus = []
a_minus = []
cnt_0 = 0

for ai in a:
    if(ai==0):
        cnt_0 += 1
    elif(ai > 0):
        a_plus.append(ai)
    else:
        a_minus.append(ai)

a_plus.sort(reverse = True)
a_minus.sort()

cnt_p = len(a_plus)
cnt_m = len(a_minus)

if(cnt_p + cnt_m < k):
    print(0)
    exit()


if(cnt_m == n)&(k%2==1):
    ans = 1
    for i in range(k):
        ans *= a_minus[cnt_m - 1 - i]
        ans %= mod
    print(ans)
    exit()

if(cnt_p == 0)&(k%2==1):
    print(0)
    exit()

p_ind = 0
m_ind = 0

ans = 1
if(k%2==1):
    last_p = a_plus.pop()
    cnt_p -= 1

for i in range(k//2):
    tmp_p = 0
    tmp_m = 0
    if(p_ind + 2 <= cnt_p ):
        tmp_p = a_plus[p_ind] * a_plus[p_ind+1]

    if(m_ind + 2 <= cnt_m ):
        tmp_m = a_minus[m_ind] * a_minus[m_ind+1]

    if(tmp_p > tmp_m):
        ans *= tmp_p
        p_ind += 2
    else:
        ans *= tmp_m
        m_ind += 2
    ans %= mod

if(k%2==1):
    if(p_ind < cnt_p):
        ans *= a_plus[p_ind]
    else:
        ans *= last_p

ans %= mod
print(ans)

Submission status: Wrong Answer

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

ans = 1
sei = 0
for i in a:
    if i>0:
        sei += 1

if max(0,k-sei)%2==0:
    b = sorted(a, key=lambda x: abs(x),reverse=True)
    buf = 0
    last = 1
    for i in range(n):
        if i<k:
            if b[i]>0:
                ans = ans*b[i]
                last = b[i]
            else:
                if buf==0:
                    buf = b[i]
                else:
                    ans = ans*b[i]*buf
                    buf = 0
        else:
            if buf!=0:
                if b[i]<0:
                    if ans//last*buf*b[i]>ans:
                        ans = ans//last*buf*b[i]
                        buf = 0
            else:
                break
        ans %= mod
else:
    b = sorted(a, key=lambda x: abs(x))
    for i in range(k):
        ans *= b[i]
        ans %= mod
print(ans%mod)

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

"""
pl=[]
mi=[]
ze=0
for num in A:
    if num>0:
        pl.append(num)
        break
    elif num<0:
        mi.append(num)
        break
    else:
        ze+=1

pl.sort()
mi.sort()

ans=0
if len(pl)+len(mi)<k:
    ans=0
    print(ans)

tab=[]
"""

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

#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:
    ans=1
    for i in range(k):
        ans=ans*A[n-1-i]%mod
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

mod = 10**9+7
n,k = na()
a = na()
a.sort()

ans = 1

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

s = 0
e = -1

while k > 0:
    if k == 1:
        if a[s] > a[e]:
            ans = ans*a[s]%mod
        else:
            ans = ans*a[e]%mod
        break
    p = a[s]*a[s+1]
    q = a[e]*a[e-1]
    if p > q:
        ans = p%mod*ans%mod
        s+=2
    else:
        ans = q%mod*ans%mod
        e-=2
    k-=2

print(ans)