Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

We will choose exactly K of these elements. Find the maximum possible product of the chosen elements.

Then, print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Constraints

1 \leq K \leq N \leq 2\times 10^5

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

Print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

The possible products of the two chosen elements are 2, -3, -4, -6, -8, and 12, so the maximum product is 12.

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

The possible products of the three chosen elements are -24, -12, -8, and -6, so the maximum product is -6.

We print this value modulo (10^9+7), that is, 1000000001.

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

The possible products of the one chosen element are -1 and 1000000000, so the maximum product is 1000000000.

Sample Input 4

10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1

Sample Output 4

999983200

Be sure to print the product modulo (10^9+7).



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 10 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

MOD = 10 ** 9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(sorted(A,key=lambda x: abs(x), reverse=True))

negs = 0
ans = 1
min_abs_neg = INF
max_abs_neg = 0
for i in range(K):
    if B[i] < 0:
        negs += 1
        if abs(min_abs_neg) > abs(B[i]):
            min_abs_neg = B[i]
        if abs(max_abs_neg) < abs(B[i]):
            max_abs_neg = B[i]
    ans *= B[i]
if negs % 2 == 0:
    print(ans % MOD)
    exit()

max_pos = -1
for i in range(K, N):
    if B[i] > 0:
        max_pos = B[i]
        break

min_neg = INF
for i in range(N - 1, K - 1, -1):
    if B[i] < 0:
        min_neg = B[i]
        break

def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

A = -INF
B = -INF
if max_pos != -1:
    # A = (ans // min_abs_neg) * max_pos
    A = ans * my_pow(min_abs_neg, MOD - 2, MOD) * max_pos
if min_neg != INF:
    # B = (ans // max_abs_neg) * min_neg
    B = ans * my_pow(max_abs_neg, MOD - 2, MOD) * min_neg

print(max(ans, A, B) % MOD)
# print(min_abs_neg)
# print(max_abs_neg)

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

    if Z==[]:
        print(ANS)
    elif ANS<0:
        print(0)
    else:
        print(ANS)

    sys.exit()

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

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

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

    print(S%mod)

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

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

        ind=K-len(B)

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

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

        ind=K-len(B)+1
        

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

    print(S%mod)

Submission status: Wrong Answer

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

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

from fractions import Fraction

def solve():
    if N == K:
        return product(A)

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

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

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

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

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

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


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

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

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

print(solve())

Submission status: Wrong Answer

Solution code:
from itertools import combinations as comb
n,k=map(int, input().split())
a=list(map(int, input().split()))
p=comb(a,k)
q=0
for i in p :
    t=1
    for j in i :
        t*=j
    print(t)
    if t>q :
        q=t
print(q%(10**9+7))

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:
        # 答えが0
        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))
        # log(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
        last_p = 0
        for i in range(k):
            a = A[i]
            ans =  (ans * a) % MOD
            if a < 0:
                n_count += 1
                last_n = a
            elif a > 0:
                last_p = a
                # log(i, last_n)

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

main()

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7


class modint():
    """
    MODはクラスの上で宣言しておく
    """

    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def main():
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    posi = [a for a in A if a > 0]
    nega = [a for a in A if a < 0]
    posi.sort(reverse=True)
    nega.sort(reverse=True)
    A.sort(reverse=True, key=abs)
    if len(posi) + len(nega) < K:
        # 0を含まなければいけないとき
        return print(0)

    ans = modint(1)
    if K % 2 == 1 and len(posi) < K:
        # 結果が負数
        # 絶対値が小さいやつをK個取ってくる
        A.sort(key=abs)
        for a in A[:K]:
            ans *= a
    else:
        # 結果が正になるように注意しなければいけない
        # skipしてかけるものがなくなったからこわい
        nega_cnt = 0
        cnt = 0
        skip = False
        for i, a in enumerate(A):
            if cnt == K-1:
                if a < 0 and nega_cnt % 2 == 0:
                    skip = True
                elif a > 0 and nega_cnt % 2 == 1:
                    skip = True
                else:
                    skip = False
            if skip:
                continue
            if a < 0:
                nega_cnt += 1
            cnt += 1
            ans *= a
            if cnt >= K:
                break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K=map(int,input().split())
A = sorted([int(i) for i in input().split()])
def prod(list):
  a=1
  for i in list:
    a*=i
  return(a)

print(max(prod(A[N-K:N]),prod(A[0:K]))%(10**9+7))

Submission status: Wrong Answer

Solution code:
def prod(llst):
	P=1
	if len(llst)==0:
		p=P*0
	else:
		for i in llst:
			P=P*i
	return P
n,k=map(int,input().split())
lst=list(map(int,input().split()))
lst.sort()
minlst=[]
i=0
while i<n:
	if lst[i]>=0:
		break
	minlst.append(lst[i])
	i=i+1
maxlst=lst[i:]
minlst.sort(reverse=True)
maxlst.sort(reverse=True)
maxp=prod(maxlst[:k])
mp=prod(minlst[:k])
if k%2==0:
	if mp>maxp:
		print(mp%1000000007)
	else:
		print(maxp%1000000007)
else:
	if len(maxlst)==0:
		print(mp%1000000007)
	else:
		print(maxp%1000000007)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


# mod m におけるaの逆元
def modinv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= m

    # 負の場合は m を足して正の数にする
    if u < 0:
        u += m
    return u


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

    if N == K:
        ans = 1
        for a in A:
            ans *= a
            ans %= MOD
        print(ans)
        return

    B = []
    n_plus = 0
    for a in A:
        if a >= 0:
            B.append((a, True))
            n_plus += 1
        else:
            B.append((-a, False))

    if n_plus == 0:
        A.sort(reverse=True)
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= MOD
        print(ans)
        return

    B.sort(key=lambda x: x[0], reverse=True)
    cnt = 0
    prev_minus = None
    prev_plus = None
    ans = 1
    for i in range(K):
        b, flag = B[i]

        ans *= b
        ans %= MOD

        if flag:
            prev_plus = b
        else:
            cnt += 1
            prev_minus = b

    if cnt % 2 == 0 or ans == 0:
        print(ans)
        return

    if N == K:
        print(-ans)
        return

    next_minus = None
    next_plus = None
    for i in range(K, N):
        b, flag = B[i]
        if flag:
            if next_plus is None:
                next_plus = b
        else:
            if next_minus is None:
                next_minus = b

    if next_plus is not None and prev_minus is not None:
        inv = modinv(prev_minus, MOD)
        tmp1 = inv * ans
        tmp1 %= MOD
        tmp1 *= next_plus
        tmp1 %= MOD
    else:
        tmp1 = -INF

    if next_minus is not None and prev_plus is not None:
        inv = modinv(prev_plus, MOD)
        tmp2 = inv * ans
        tmp2 %= MOD
        tmp2 *= next_minus
        tmp2 %= MOD
    else:
        tmp2 = -INF

    print(max(tmp1, tmp2))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations
import numpy as np

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

n_c = list(combinations(a,k))

Submission status: Wrong Answer

Solution code:
mod = 10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort(key=lambda x:-abs(x))
p = []
n = []
for i in range(K):
    a = A[i]
    if a>0:
        p.append(a)
    elif a<0:
        n.append(a)

if len(n)%2==0:
    ans = 1
    for a in n:
        ans *= a
        ans %= mod
    for a in p:
        ans *= a
        ans %= mod
else:
    ap = 0
    an = 0
    for i in range(K,N):
        if ap==0 and A[i]>0:
            ap = A[i]
        if an==0 and A[i]<0:
            an = -A[i]
    if len(p)*len(n)>0:
        ap_ = p[-1]
        an_ = -n[-1]
        if ap_*an_==0:
            ans = 0
        else:
            if ap*ap_>an*an_:
                n.pop()
                p.append(ap)
            else:
                p.pop()
                n.append(-an)
            ans = 1
            for a in n:
                ans *= a
                ans %= mod
            for a in p:
                ans *= a
                ans %= mod
    elif len(p)>0:
        ans = 1
        for a in p:
            ans *= a
            ans %= mod
    elif len(n)>0:
        ans = 1
        for a in n:
            ans *= a
            ans %= mod
if len(p)+len(n)<K:
    ans = 0
if len(p)==0 and len(n)==K and K%2==1:
    An = [A[i] for i in range(N) if A[i]<0]
    An.sort()
    An = An[::-1]
    ans = 1
    for i in range(K):
        ans *= An[i]
        ans %= mod
    if A[-1]==0:
        ans = 0
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = sorted([int(i) for i in input().split()], reverse=True)
b = sorted([(abs(ai), ai) for ai in a], reverse=True)
c = 1
mod = 10**9 + 7
if a[0] < 0:
    for ai in a[:k]:
        c = c * ai % mod
    print(c)
else:
    for i in range(k // 2 * 2):
        c = c * b[i][1] % mod
    if k % 2:
        for i in range(k // 2 * 2, n):
            if b[i][0] >= 0:
                c = c * b[i][1] % mod
                break
    print(c)

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:
  ANS1 = -INF
  ANS2 = -INF
  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
        ANS1 = ans
        break
  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
        ANS2 = ans
        break
  if max(ANS1,ANS2)!=-INF:
    print(max(ANS1,ANS2))
    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:
n, k = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7

plus = []
minus = []
zero = []
for i in range(n):
    if a[i] < 0:
        minus.append(abs(a[i]))
    elif a[i] > 0:
        plus.append(a[i])
    else:
        zero.append(0)


len_p = len(plus)
len_m = len(minus)
len_z = len(zero)

is_z = False
is_p = False
if len_z != 0:
    is_z = True

cnt = 2 * (len_m // 2) + len_p
if cnt >= k:
    is_p = True
if len_p == 0 and k % 2 == 1:
    is_p = False

if is_p:
    minus = sorted(minus, reverse=True)
    plus = sorted(plus, reverse=True)
    ans = 1
    if k % 2 == 1:
        k -= 1
        ans = plus[0]
        del plus[0]
    tmp = []
    for i in range(len(minus) // 2):
        tmp.append(minus[2 * i] * minus[2 * i + 1])
    for i in range(len(plus) // 2):
        tmp.append(plus[2 * i] * plus[2 * i + 1])
    tmp = sorted(tmp, reverse=True)
    for i in range(k // 2):
        ans *= tmp[i]
        ans %= MOD
    print(ans)
    exit()

elif is_z:
    print(0)
    exit()

else:
    print(0)

    exit()

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:]
    if len(x)!=k:1/0
    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:
#!/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:
        if K % 2:
            A.sort(reverse=True)
        else:
            A.sort()
        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
        if min_nn % 2: # can be pos
            ns.sort()
            ps.sort(reverse=True)
        else:
            ns.sort(reverse=True)
            ps.sort()
        ret = 1
        for i in range(min_nn):
            ret *= ns[i]
            ret %= MOD
        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:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


import math
n,k = map(int, input().split())
a = list(map(int, input().split()))
a1 = [item for item in a if item>0]
a2 = [item for item in a if item<0]
n1 = sum(item>0 for item in a)
n2 = sum(item<0 for item in a)
nz = sum(item==0 for item in a)
a1.sort(reverse=True)
a2.sort()
c1 = [math.log2(item) for item in a1]
c2 = [math.log2(-item) for item in a2]
def cumsum(a):
    """l[i] = sum(a[:i]) なるlを返す
    sum(a[i:j]) == l[j+1] - l[i]
    """
    c = 0
    l = [None] * (len(a)+1)
    for i,num in enumerate(a):
        l[i] = c
        c += num
    l[-1] = c
    return l
cc1 = cumsum(c1)
cc2 = cumsum(c2)
if n1+n2<k:
    ans = 0
else:
    best = -10**12
    ind = None
    for i in range(n2//2+1):
        # マイナスを偶数個
        if 2*i>k:
            continue
        if 2*i+n1+nz<k:
            continue
        if k-2*i<=n1:
            val = cc2[2*i] + cc1[k-2*i]
            if val>best:
                ind = i
                best = val
    M = 10**9+7
    if ind is None:
        if nz>0:
            ans = 0
        else:
            # マイナスだけ
            ans = 1
            if k<=n2:
                for i in range(k):
                    ans *= a2[-(i+1)]
                    ans %= M
            else:
                for i in range(n2):
                    ans *= a2[i]
                    ans %= M
                for i in range(n1):
                    ans *= a1[i]
                    ans %= M
    else:
        ans = 1
        for i in range(2*i):
            ans *= a2[i]
            ans %= M
        for i in range(k-2*i):
            ans *= a1[i]
            ans %= M
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
n,k = map(int,stdin.readline().split())
arr = sorted(list(map(int,stdin.readline().split())),key=lambda x:abs(x))
mod = 10**9+7
pos,neg = [],[]
for i in arr:
    if i>=0:
        pos.append(i)
    else:
        neg.append(i)
if not len(pos):
    ans = 1
    if k%2:
        for i in range(k):
            ans *= neg[i]
            ans %= mod
    else:
        for i in range(k):
            ans *= neg[-1-i]
            ans %= mod
else:
    ans = 1
    i=len(pos)-1
    j=len(neg)-1
    val = 0
    if k%2:
        ans *= pos[i]
        i -= 1
        val += 1
    while val != k:
        if i<1:
            ans *= neg[j]*neg[j-1]
            ans %= mod
            j -= 2
        elif j<1:
            ans *= pos[i]*pos[i-1]
            ans %= mod
            i -= 2
        else:
            if pos[i]*pos[i-1]>neg[j]*neg[j-1]:
                ans *= pos[i]*pos[i-1]
                ans %= mod
                i -= 2
            else:
                ans *= neg[j] *neg[j-1]
                ans %= mod
                j -= 2
        k -= 2
print(ans)

Submission status: Wrong Answer

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

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

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

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

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

    if ANS<0 and Z!=[]:
        print(0)
    else:
        print(ANS)
    sys.exit()

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

    if Z==[]:
        print(ANS)
    elif ANS<0:
        print(0)
    else:
        print(ANS)

    sys.exit()

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

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

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

    print(S%mod)

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

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

        ind=K-len(B)

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

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

        ind=K-len(B)+1
        

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

    print(S%mod)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    if N == K:
        ans = 1
        for a in A:
            ans *= a
            ans %= mod
        return ans

    neg = []
    pos = []
    for a in A:
        if a >= 0:
            pos.append(a)
        elif a < 0:
            neg.append(a)
    pos.sort()
    neg.sort(reverse=True)

    if len(neg) == N:
        res = 1
        for x in neg[:K]:
            res *= x
            res %= mod
        return res

    ans = 1

    if K & 1:
        ans *= pos.pop()
        K -= 1
    while K and len(pos) > 1 and len(neg) > 1:
        K -= 2
        x = 1
        if pos[-1] * pos[-2] > neg[-1] * neg[-2]:
            x *= pos.pop()
            x *= pos.pop()
            x %= mod
        else:
            x *= neg.pop()
            x *= neg.pop()
            x %= mod
        ans *= x
        ans %= mod
    while K and pos:
        K -= 1
        ans *= pos.pop()
        ans %= mod
    return ans


if __name__ == "__main__":
    print(main())