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:
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

import heapq
import collections

class HeapQueue:

    def __init__(self, xs, mode):
        if   mode == "min": self.xs = [+x for x in xs]
        elif mode == "max": self.xs = [-x for x in xs]
        else              : raise NotImplementedError("HeapQueue.__init__: mode should be 'min' or 'max'")
        heapq.heapify(xs)
        self.mode = mode

    def __len__(self):
        return len(self.xs)

    def pop(self):
        if   self.mode == "min": return heapq.heappop(self.xs)
        elif self.mode == "max": return heapq.heappop(self.xs) * (-1)

    def push(self, x):
        if   self.mode == "min": return heapq.heappush(self.xs,  x)
        elif self.mode == "max": return heapq.heappush(self.xs, -x)

    # @staticmethod
    # def __test01__():
    #     xs = HeapQueue([-3, 2, 9, -4], "min")
    #     x0 = xs.pop()
    #     x1 = xs.pop()
    #     x2 = xs.pop()
    #     x3 = xs.pop()
    #     return (x0 == -4 and x1 == -3 and x2 == 2 and x3 == 9)


N, K = tuple(map(int, input().strip().split()))
As = list(map(int, input().strip().split()))

D = int(1E9 + 7)
r = 1

if N == K:

    for a in As:
        r = (r * a) % D
    print(r)
    exit()

if all(a >= 0 for a in As):

    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * a) % D
    print(r)
    exit()

if K % 2 == 1 and all(a < 0 for a in As):

    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * a) % D
    print(r)
    exit()

if K % 2 == 0 and all(a < 0 for a in As):

    As = sorted(As)
    for a in As[:K]:
        r = (r * a) % D
    print(r)
    exit()

else:

    As = sorted(As, key = lambda a: abs(a), reverse=True)

    used = As[:K]
    rest = As[K:]
    num_negative_sign = sum([1 if x < 0 else 0 for x in used])

    if num_negative_sign % 2 != 0:

        used_min_pos = None
        used_min_neg = None
        for k in range(K-1, -1, -1):
            if   used_min_pos is None and used[k] >= 0: used_min_pos = k
            elif used_min_neg is None and used[k] <  0: used_min_neg = k
            if used_min_pos and used_min_neg:
                break

        rest_min_pos = None
        rest_min_neg = None
        for k in range(N-K-1, -1, -1):
            if   rest_min_pos is None and rest[k] >= 0: rest_min_pos = k
            elif rest_min_neg is None and rest[k] <  0: rest_min_neg = k
            if rest_min_pos and rest_min_neg:
                break

        if used_min_pos is None or rest_min_neg is None:
            used[used_min_neg] = rest_min_pos
        elif used_min_neg is None or rest_min_pos is None:
            used[used_min_pos] = rest_min_neg
        else:
            v1 = abs(used[used_min_pos] * rest[rest_min_neg])
            v2 = abs(used[used_min_neg] * rest[rest_min_pos])
            if v1 < v2:
                used[used_min_pos] = rest_min_neg
            else:
                used[used_min_neg] = rest_min_pos

    for a in used:
        r = (r * a) % D
    print(r)
    exit()


##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker

Submission status: Wrong Answer

Solution code:
from math import *
ln,k=list(map(int,input().split()))
l=list(map(int,input().split()))
l.sort(reverse=True,key = lambda s: abs(s))
# print(l)
lul = 10**9 + 7

temp = []
for i in range(ln):
	if l[i]<0:
		temp.append(-1*l[i])
ct = 0
p = -1; n = -1
ans = []
temp = temp[::-1]
for i in range(k):
	ans.append(i)
	if l[i]<0:
		ct+=1
		n = max(n,i)
	else:
		p = max(p,i)
# print(ct)
if ct%2!=0:
	for i in range(k,ln):
		if l[i]<0 and p!=-1:
			ans.remove(p)
			ans.append(i)
			ct+=1
			break
		elif l[i]>=0:
			ans.remove(n)
			ans.append(i)
			ct-=1
			break
# print(ct)
if ct%2!=0:
	v = 1
	if ct==ln:
		for i in range(k):
			v = (v*temp[i])%lul
	else:
		for i in ans:
			v = (v*abs(l[i]))%lul
	v = ((lul-1)*v)%lul
else:
	v = 1
	# print(ans)
	# print(l)
	for i in ans:
		v = (v*abs(l[i]))%lul
print(v)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
N,K=map(int, input().split())
A=list(map(int, input().split()))
p=10**9+7
A=sorted(A)
thresh=bisect_left(A,0)
minus=A[:thresh]
plus=A[thresh:][::-1]

#print(plus, minus)
if len(plus)==0:
    ans=1
    if K%2!=0:
        minus=minus[::-1]
        for i in range(K):
            ans*=minus[i]
            ans%=p
    else:
        for i in range(K):
            ans*=minus[i]
            ans%=p
    print(ans)
    exit()

if len(minus)==0:
    ans=1
    for i in range(K):
        ans*=plus[i]
        ans%=p
    print(ans)
    exit()

midx=0
pidx=0
ans=1
"""
while K>0 and (0<=midx<len(minus) or 0<=pidx<len(plus)):
    if midx==len(minus)-1:
        nexmin=minus[midx]
    elif midx>=len(minus):
        nexmin=-1
    else:
        nexmin=minus[midx]*minus[midx+1]

    if pidx==len(plus)-1:
        nexplus=plus[pidx]
    elif pidx>=len(plus):
        nexplus=-float("INF")
    else:
        if plus[pidx+1]!=0:
            nexplus=plus[pidx]*plus[pidx+1]
        else:
            nexplus=plus[pidx]

    if nexmin>=nexplus and K>=2:
        ans*=nexmin
        ans%=p
        midx+=2
        K-=2
    else:
        ans*=plus[pidx]
        ans%=p
        pidx+=1
        K-=1
"""

print(ans)

Submission status: Wrong Answer

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


plus_lst = list(filter(lambda num: num >= 0 , a_lst))
minus_lst = list(filter(lambda num: num < 0 , a_lst))
plus_lst.sort(reverse=True)
minus_lst.sort(reverse=True)


# +,-どちらもk以上ある
	# max(abs+,abs-)で大きい方をk-1回目までとる, k-1回目で+だったら+, -だったら-
# +: kない, -: kある
	# +の数が残り1になるまでabsでやる,最後に+を使って調整する
# +: kある, -: kない
	# -の数が1になるまでabsでやる, 最後に-を使って調整
# +: kない, -: kない
	# どちらかが残り1になるまでやる,最後に調整
# -のみ
	# absでできるだけ小さいものを使う

# 0を抜いたらk個なかった場合、絶対どっかで0を掛けるので0
# 全部-の場合
if(len(plus_lst) == 0):
	total = 1
	for i in range(k):
		total *=minus_lst[i]
	print(total % (10**9 + 7))
elif(len(minus_lst) == 0):
	total = 1
	for i in range(k):
		total *= plus_lst[i]
	print(total % (10**9 + 7))
else:
	total = 1
	for i in range(k):
		if(i == k - 1):
			if(total > 0):
				total *= plus_lst.pop(0)
			else:
				total *= minus_lst.pop(0)
		else:
			# plus残り1の場合
			if(len(plus_lst) == 1):
				total *= minus_lst.pop(0)
			# minus残り1の場合
			elif(len(minus_lst) == 1):
				total += plus_lst.pop(0)					
			# +-どっちも十分あった場合
			else:
				plus_max = plus_lst[0]
				minus_max = minus_lst[0]
				if(abs(plus_max) > abs(minus_max)):
					plus_lst.pop(0)
					total *= plus_max
				else:
					minus_lst.pop(0)
					total *= minus_max
	print(total % (10**9 + 7))

Submission status: Wrong Answer

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

a.sort(reverse=True, key=lambda x:abs(x))
cnt = 0
im = -1
ip = -1
cp = 0
mod = 10 ** 9 + 7
nm = 0
np = 0

for i, ai in enumerate(a):
    if i < k:
        if ai < 0:
            im = i
            cnt += 1
        if ai > 0:
            ip = i
    else:
        if ai < 0 and nm == 0:
            nm = ai
        if ai > 0 and np == 0:
            np = ai
    if ai > 0:
        cp += 1

ans = 1
f = 0

# print(a)
if cnt % 2 and k < n:
    if cp == 0:
        a.sort(reverse=True)
        for i, ai in enumerate(a):
            if i == k:
                break
            ans *= ai
            ans %= mod
        print(ans) # ok
    else:
        ans = 1
        cnt = 0
        f1 = 0
        f2 = 0
        for i, ai in enumerate(a):
            if cnt == k - 2:
                break
            if i == im:
                f1 = 1
                continue
            if i == ip:
                f2 = 1
                continue
            if f1 and ai <= 0:
                continue
            if f2 and ai >= 0:
                continue
            ans *= abs(ai)
            ans %= mod
            # print(i, ai)
            cnt += 1
        ans *= max(a[ip] * np, a[im] * nm)
        ans %= mod
        print(ans)
else:
    for i, ai in enumerate(a):
        if i == k:
            break
        ans *= abs(ai)
        ans %= mod
    print(ans) # ok

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
a =list(map(int, input().split()))
ans =1

if n == k:
   for i in a:
       ans *= i
       if abs(ans) >10**9+7:
           ans = ans%(10**9+7)

elif all(i <= 0 for i in a) and k%2 ==1:
    a.sort(reverse = True)
    for i in range(k):
        ans *= a[i]
        if abs(ans) > 10 ** 9 + 7:
            ans = ans % (10 ** 9 + 7)

else:
    am =[]
    ap =[]

    a.sort(key = abs,reverse = True)
    amax = a[:k]
    amin = a[k:]
    c=1
    if 0 in amax:
        ans = 0
    else:
        for i in amax:
            if i<0:
                am.append(i)
                c *=-1
            elif i>0:
                ap.append(i)
        if c ==1:
            for i in amax:
                ans *= i
                if abs(ans) > 10 ** 9 + 7:
                    ans = ans % (10 ** 9 + 7)
        else:
            if ap == []:
                amax.remove(max(am))
                amax.append(max(amin))

            elif min(amin)/min(ap) > max(amin)/max(am):
                amax.remove(max(am))
                amax.append(max(amin))
            else:
                amax.remove(min(ap))
                amax.append(min(amin))
            for i in amax:
                ans *= i
                if abs(ans) > 10 ** 9 + 7:
                    ans = ans % (10 ** 9 + 7)

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

Submission status: Wrong Answer

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

if n==k:
  ans=1
  for i in range(k):ans=ans*a[i]%MOD
  print(ans)
  exit()

p=[]
m=[]
for q in a:
  if q>=0:p+=q,
  else:m+=q,

if len(m)==n and k%2==1:
  m.sort()
  m=m[::-1]
  ans=1
  for i in range(k):
    ans=ans*m[i]%MOD
  print(ans)
  exit()

a.sort(key=lambda x:abs(x),reverse=True)

s=[]
flg=1
for i in range(k):
  s.append(a[i])
  if a[i]<0:
    flg*=-1
if flg==-1:
  tmp=s.pop()
  for i in range(k,n):
    if a[i]*tmp<0:
      s.append(a[i])
      break
ans=1
for i in s:
  ans=ans*i%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
mod = 10**9 + 7
nums = []
for i in list(map(int, input().split())):
    if i >= 0:
        nums.append((i, True))
    else:
        nums.append((-i, False))
rev_nums = sorted(nums, reverse=True)
nums.sort()

ans = 1
pl = []
ml = []
for k in range(K):
    x, b = nums.pop()
    ans *= x
    ans %= mod
    if b:
        pl.append(x)
    else:
        ml.append(x)
if len(ml) % 2 != 0:
    while nums:
        x, b = nums.pop()
        if b:
            ans //= ml[-1]
            ans %= mod
            ans *= x
            ans %= mod
            break
    else:
        ans = -1
        for k in range(K):
            x, b = rev_nums.pop()
            ans *= x
            ans %= mod
print(ans)

Submission status: Wrong Answer

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


plus_lst = list(filter(lambda num: num > 0 , a_lst))
minus_lst = list(filter(lambda num: num < 0 , a_lst))
plus_lst.sort(reverse=True)
minus_lst.sort(reverse=True)


# +,-どちらもk以上ある
	# max(abs+,abs-)で大きい方をk-1回目までとる, k-1回目で+だったら+, -だったら-
# +: kない, -: kある
	# +の数が残り1になるまでabsでやる,最後に+を使って調整する
# +: kある, -: kない
	# -の数が1になるまでabsでやる, 最後に-を使って調整
# +: kない, -: kない
	# どちらかが残り1になるまでやる,最後に調整
# -のみ
	# absでできるだけ小さいものを使う

# 0を抜いたらk個なかった場合、絶対どっかで0を掛けるので0
if(len(plus_lst) + len(minus_lst) < k):
	print(0)
# 全部-の場合
elif(len(plus_lst) == 0):
	total = 1
	for i in range(k):
		total *=minus_lst[i]
	print(total % (10**9 + 7))
elif(len(minus_lst) == 0):
	total = 1
	for i in range(k):
		total *= plus_lst[i]
	print(total % (10**9 + 7))
else:
	total = 1
	for i in range(k):
		if(i == k - 1):
			if(total > 0):
				total *= plus_lst.pop(0)
			else:
				total *= minus_lst.pop(0)
		else:
			# plus残り1の場合
			if(len(plus_lst) == 1):
				total *= minus_lst.pop(0)
			# minus残り1の場合
			elif(len(minus_lst) == 1):
				total += plus_lst.pop(0)					
			# +-どっちも十分あった場合
			else:
				plus_max = plus_lst[0]
				minus_max = minus_lst[0]
				if(abs(plus_max) > abs(minus_max)):
					plus_lst.pop(0)
					total *= plus_max
				else:
					minus_lst.pop(0)
					total *= minus_max
	print(total % (10**9 + 7))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
modulo = 10 ** 9 + 7
*arr, = map(int, input().split())
inverses = [pow(v, modulo - 2, modulo) for v in arr]
neg_cnt = 0
for v in arr:
    if v < 0:
        neg_cnt += 1

def min_pos(arr):
    pass


if neg_cnt == n:
    res = 1
    arr.sort(reverse=True)
    for i in range(k):
        res *= arr[i]
        res %= modulo
    print(res)
elif k == n:
    res = 1
    for v in arr:
        res *= v
        res %= modulo
    print(res)
else:
    pos = []
    neg = []
    for i, v in enumerate(arr):
        if v < 0:
            neg.append(i)
        else:
            pos.append(i)

    neg.sort(key=lambda v: abs(arr[i]), reverse=True)
    pos.sort(key=lambda v: abs(arr[i]), reverse=True)

    if k % 2:
        res = arr[pos[0]] % modulo
        i = 1
    else:
        res = 1
        i = 0
    j = 0
    while i + j < k and (i < len(pos) - 1 or j < len(neg) - 1):
        if j >= len(neg) - 1 or i < len(pos) - 1 and arr[pos[i]] * arr[pos[i + 1]] > arr[neg[j]] * arr[neg[j + 1]]:
            res *= arr[pos[i]]
            res *= arr[pos[i + 1]]
            i += 2
        else:
            res *= arr[neg[j]]
            res *= arr[neg[j + 1]]
            j += 2
        res %= modulo
    while i + j < k:
        res *= arr[pos[i]]
        i += 1
        res %= modulo

    print(res)

Submission status: Wrong Answer

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

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
p = 10 ** 9 + 7
A.sort(key = lambda x : abs(x)) # 絶対値小→大
A_zpos = [a for a in A if a >= 0]
A_neg = [a for a in A if a < 0]

ans = 1
k = K
while k > 0:
    if k == 1:
        if A_zpos:
            ans *= A_zpos.pop()
            k -= 1
        else:
            ans = 1
            for i in range(K):
                ans = ans * A[i] % p
            break
    else:
        if len(A_zpos) == len(A_neg) == 1:
            ans = ans * A_zpos.pop() * A_neg.pop() % p
            k -= 2
        else:
            next_zpos = -1 if len(A_zpos) < 2 else A_zpos[-1] * A_zpos[-2] % p
            next_neg = -1 if len(A_neg) < 2 else A_neg[-1] * A_neg[-2] % p
            if next_zpos >= next_neg:
                ans = ans * A_zpos.pop() * A_zpos.pop() % p
            else:
                ans = ans * A_neg.pop() * A_neg.pop() % p
            k -= 2

print(ans)

Submission status: Wrong Answer

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

a_lst.sort(reverse=True)

plus_lst = list(filter(lambda num: num > 0 , a_lst))
minus_lst = list(filter(lambda num: num < 0 , a_lst))


# +,-どちらもk以上ある
	# max(abs+,abs-)で大きい方をk-1回目までとる, k-1回目で+だったら+, -だったら-
# +: kない, -: kある
	# +の数が残り1になるまでabsでやる,最後に+を使って調整する
# +: kある, -: kない
	# -の数が1になるまでabsでやる, 最後に-を使って調整
# +: kない, -: kない
	# どちらかが残り1になるまでやる,最後に調整
# -のみ
	# absでできるだけ小さいものを使う

# 0を抜いたらk個なかった場合、絶対どっかで0を掛けるので0
if(len(plus_lst) + len(minus_lst) < k):
	print(0)
# 全部-の場合
elif(len(plus_lst) == 0):
	total = 1
	for i in range(k):
		total *=a_lst[i]
	print(total % (10**9 + 7))
elif(len(minus_lst) == 0):
	total = 1
	for i in range(k):
		total *= a_lst[i]
	print(total % (10**9 + 7))
else:
	total = 1
	for i in range(k):
		if(i == k - 1):
			if(total > 0):
				total *= plus_lst.pop(0)
			else:
				total *= minus_lst.pop(0)
		else:
			# plus残り1の場合
			if(len(plus_lst) == 1):
				total *= minus_lst.pop(0)
			# minus残り1の場合
			elif(len(minus_lst) == 1):
				total += plus_lst.pop(0)					
			# +-どっちも十分あった場合
			else:
				plus_max = plus_lst[0]
				minus_max = minus_lst[0]
				if(abs(plus_max) > abs(minus_max)):
					plus_lst.pop(0)
					total *= plus_max
				else:
					minus_lst.pop(0)
					total *= minus_max
	print(total % (10**9 + 7))

Submission status: Wrong Answer

Solution code:
from collections import deque
# N = int(input())
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
MOD = 10 ** 9 + 7
A_p = []
A_n = []
for a in A:
  if a >= 0:
    A_p.append(a)
  else:
    A_n.append(-a)

A_p.sort(reverse=True)
A_n.sort(reverse=True)
A_p = deque(A_p)
A_n = deque(A_n)

p_top = 0
n_top = 0
ans_p = deque([])
ans_n = deque([])
for i in range(K):
  if len(A_p) == 0:
    ans_n.append(A_n.popleft())
  elif len(A_n) == 0:
    ans_p.append(A_p.popleft())
  elif A_p[0] >= A_n[0]:
    ans_p.append(A_p.popleft())
  else:
    ans_n.append(A_n.popleft())
if 0 in ans_p:
  ans = 0
elif len(ans_n) % 2 == 1:
  if len(ans_p) == 0 and len(A_p) > 0:
    ans_n.pop()
    ans_p.append(A_p.popleft())
  elif len(ans_n) == 0 and len(A_n) > 0:
    ans_p.pop()
    ans_n.append(A_n.popleft())
  elif len(ans_p) > 0 and len(ans_n) > 0 and len(A_p) > 0 and len(A_n) > 0 and ans_p[-1] * A_p[0] >= ans_n[-1] * A_n[0]:
    ans_n.pop()
    ans_p.append(A_p.popleft())
  elif len(ans_p) > 0 and len(A_n) > 0:
    ans_p.pop()
    ans_n.append(A_n.popleft())
ans = 1
for a in ans_p:
  ans = (a * ans) % MOD
for a in ans_n:
  ans = (-a * ans) % MOD
if ans != 0 and len(ans_n) % 2 == 1:
  ans = 1
  A_abs = [abs(a) for a in A]
  A_abs.sort()
  for i in range(K):
    ans = (ans * A_abs[i]) % MOD
  ans = (-ans) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

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

    # もしN = K なら全部選択しないといけないので、
    # 全部掛け算して返す
    if N == K:
        ans = 1
        for a in A:
            ans = (ans * a) % MOD
        print(ans)
        return

    Ap = [] # 正の数だけ入っている
    Am = [] # 負の数だけ入っている.値は絶対値で入れる
    has0 = False # 0がAの中にあるか
    for a in A:
        if a == 0:
            has0 = True
        elif a > 0:
            Ap.append(a)
        else:
            Am.append(-a)

    # それぞれを絶対値の大きい順に並べる
    Ap.sort(reverse=True)
    Am.sort(reverse=True)

    ip = 0
    im = 0
    lp = len(Ap)
    lm = len(Am)

    # もし0でない数がK個未満しかない場合、0を必ず選ばないといけないので
    # 答えは0になる
    if lp + lm < K:
        print(0)
        return

    # # 正の数+負の数=K かつ負の数が奇数のとき、0を選んだほうがマシなので、
    # # 答えは0になる
    # if lp + lm == K and lm % 2 == 1:
    #     print(0)
    #     return
    # もしKが奇数のときで、かつ正の数が1個もない時
    if K % 2 == 1 and lp == 0:
        # 0があるなら0にする
        if has0:
            print(0)
            return
        # 0がない場合は、負の数の中から絶対値の小さいものを選ぶ
        else:
            ans = 1
            for a in Am[-K:]:
                ans = (ans * a) % MOD
            print(MOD - ans)
            return

    # 戦略: Aの中から絶対値の大きい順に選んでいく
    ans = 1
    for i in range(K):
        x = None
        if ip == lp: # 正の数をこれ以上選べないのであれば負の数を選ぶ
            x = Am[im]
            im += 1
        elif im == lm: # 負の数をこれ以上選べないのであれば正の数を選ぶ
            x = Ap[ip]
            ip += 1
        # 正の数、負の数どちらも選べるのであれば、絶対値の大きいほうを選ぶ
        elif Am[im] < Ap[ip]:
            x = Ap[ip]
            ip += 1
        else:
            x = Am[im]
            im += 1
        # print(x)
        ans = ans * x % MOD

    # もし絶対値の大きい順で選んで、負の数を奇数個選んでいたとき
    if im % 2 == 1:
        # 選んだ中で一番小さい負の数を外して、まだ選んでない中で最も大きい正の数を入れるか、
        # 選んだ中で一番小さい正の数を外して、まだ選んでない中で最も（絶対値が）大きい負の数を入れるか選ぶ

        # これ以上0でない数がない場合は、0を選択して答えを0にするのが最大値になる
        if ip == lp and im == lm:
            print(0)
            return
        # 正の数をこれ以上選べない場合は負の数から選ぶ
        elif ip == lp:
            ans = ans * modinv(Ap[ip-1]) % MOD
            ans = ans * Am[im] % MOD
        # 負の数をこれ以上選べない場合は正の数から選ぶ
        elif im == lm:
            ans = ans * modinv(Am[im-1]) % MOD
            ans = ans * Ap[ip] % MOD
        # 正、負ともまだ選ぶ余裕がある場合
        else:
            # 一旦、選んだ中で一番小さい負の数と、選んだ中で一番小さい正の数を戻す（再度選べるようにする）
            if ip > 0:
                ip -= 1
                ans = ans * modinv(Ap[ip]) % MOD
                
            if im > 0:
                im -= 1
                ans = ans * modinv(Am[im]) % MOD
            # 正、負のリストから、まだ選んでない中で絶対値が大きいもの2つを選び、その積の大きいほうを選ぶ
            a = Ap[ip] * Ap[ip+1]
            b = Am[im] * Am[im+1]
            # print(a, b)

            ans = ans * max(a, b) % MOD

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

a.sort(reverse=True, key=lambda x:abs(x))
cnt = 0
im = -1
ip = -1
cp = 0
mod = 10 ** 9 + 7
nm = 0
np = 0

for i, ai in enumerate(a):
    if i < k:
        if ai < 0:
            im = i
            cnt += 1
        if ai > 0:
            ip = i
    else:
        if ai < 0 and nm == 0:
            nm = ai
        if ai > 0 and np == 0:
            np = ai
    if ai > 0:
        cp += 1

ans = 1
f = 0

# print(a)
if cnt % 2 and k < n:
    if cp == 0:
        a.sort(reverse=True)
        for i, ai in enumerate(a):
            if i == k:
                break
            ans *= ai
            ans %= mod
        print(ans) # ok
    else:
        ans = 1
        cnt = 0
        f1 = 0
        f2 = 0
        for i, ai in enumerate(a):
            if i == im:
                f1 = 1
                continue
            if i == ip:
                f2 = 1
                continue
            if f1 and ai <= 0:
                continue
            if f2 and ai >= 0:
                continue
            ans *= abs(ai)
            ans %= mod
            # print(i, ai)
            cnt += 1
        ans *= max(a[ip] * np, a[im] * nm)
        ans %= mod
        print(ans)
else:
    for i, ai in enumerate(a):
        if i == k:
            break
        ans *= abs(ai)
        ans %= mod
    print(ans) # ok

Submission status: Wrong Answer

Solution code:
def main():
    n,k = map(int,input().split())
    A = list(map(int,input().split()))

    MOD = 10**9 + 7
    m = []
    p = []
    for i in A:
        if i < 0:
            m.append(i)
        elif i >= 0:
            p.append(i)

    m.sort()
    p.sort(reverse=True)

    # print(p,m)
    if len(p) == 0:
        ans = cal_ans(m[n-k:])
        print(ans)
        exit()

    al = []
    i = 0
    j = 0
    while i+j<k:
        if j<len(p)-1 and i < len(m)-1:
            b = p[j]*p[j+1]
            a = m[i]*m[i+1]
            if a >= b:
                al.append(m[i])
                al.append(m[i+1])
                i+= 2
            else:
                al.append(p[j])
                al.append(p[j+1])
                j+=2
        elif j<len(p):
            al.append(p[j])
            j+=1
        elif i < len(m)-1:
            al.append(m[i])
            al.append(m[i+1])
            i+= 2
    if i+j == k-2:
        al.append(p[j+1])
    ans= cal_ans(al)
    print(ans)

def cal_ans(A):
    # print(A)
    MOD = 10**9+7
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    return ans

main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
modulo = 10 ** 9 + 7
*arr, = map(int, input().split())
inverses = [pow(v, modulo - 2, modulo) for v in arr]
neg_cnt = 0
for v in arr:
    if v < 0:
        neg_cnt += 1

def min_pos(arr):
    pass


if neg_cnt == n:
    res = 1
    arr.sort(reverse=True)
    for i in range(k):
        res *= arr[i]
        res %= modulo
    print(res)
elif k == n:
    res = 1
    for v in arr:
        res *= v
        res %= modulo
    print(res)
else:
    pos = []
    neg = []
    for i, v in enumerate(arr):
        if v < 0:
            neg.append(i)
        else:
            pos.append(i)

    neg.sort(key=lambda v: abs(arr[i]), reverse=True)
    pos.sort(key=lambda v: abs(arr[i]), reverse=True)

    if k % 2:
        res = arr[pos[0]] % modulo
        i = 1
    else:
        res = 1
        i = 0
    j = 0
    while i + j < k and (i < len(pos) - 1 or j < len(neg) - 1):
        if j >= len(neg) - 1 or i < len(pos) - 1 and arr[pos[i]] * arr[pos[i + 1]] > arr[neg[j]] * arr[neg[j + 1]]:
            res *= arr[pos[i]]
            res *= arr[pos[i + 1]]
            i += 2
        else:
            res *= arr[neg[j]]
            res *= arr[neg[j + 1]]
            j += 2
        res %= modulo
    while i + j < k:
        res *= arr[pos[i]]
        i += 1

    print(res)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
modulo = 10 ** 9 + 7
*arr, = map(int, input().split())
inverses = [pow(v, modulo - 2, modulo) for v in arr]
neg_cnt = 0
for v in arr:
    if v < 0:
        neg_cnt += 1

def min_pos(arr):
    pass


print(neg_cnt, n)
if neg_cnt == n:
    res = 1
    arr.sort(reverse=True)
    for i in range(k):
        res *= arr[i]
        res %= modulo
    print(res)
elif k == n:
    res = 1
    for v in arr:
        res *= v
        res %= modulo
    print(res)
else:
    pos = []
    neg = []
    for i, v in enumerate(arr):
        if v < 0:
            neg.append(i)
        else:
            pos.append(i)

    neg.sort(key=lambda v: abs(arr[i]), reverse=True)
    pos.sort(key=lambda v: abs(arr[i]), reverse=True)

    if k % 2:
        res = arr[pos[0]] % modulo
        i = 1
    else:
        res = 1
        i = 0
    j = 0
    while i + j < k and (i < len(pos) - 1 or j < len(neg) - 1):
        if j >= len(neg) - 1 or i < len(pos) - 1 and arr[pos[i]] * arr[pos[i + 1]] > arr[neg[j]] * arr[neg[j + 1]]:
            res *= arr[pos[i]]
            res *= arr[pos[i + 1]]
            i += 2
        else:
            res *= arr[neg[j]]
            res *= arr[neg[j + 1]]
            j += 2
        res %= modulo
    while i + j < k:
        res *= arr[pos[i]]
        i += 1

    print(res)

Submission status: Wrong Answer

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

allm = True
for a in A:
    if a > 0:
        allm = False
        break

if N == K:
    ans = 1
    for a in A:
        ans = (ans*a) % MOD
    print(ans)
elif allm and K % 2 == 1:
    A.sort()
    A.reverse()
    ans = 1
    for a in A[:K]:
        ans = (ans*a) % MOD
    print(ans)
else:
    p, m = [], []
    for a in A:
        if a > 0:
            p.append(a)
        if a < 0:
            m.append(-a)
    p.sort(key=lambda k: -k)
    m.sort(key=lambda k: -k)

    pi, mi = 0, 0
    ans = 1

    # Kが奇数の場合はplusから最初に一つとっておく
    if K % 2 == 1:
        pi = 1
        ans = p[0]
        K -= 1

    while K > 0:
        if K == 1:
            ans = (ans*p[pi]) % MOD
            break
        elif pi < len(p)-1 or mi < len(m)-1:
            pv, mv = 0, 0
            if pi < len(p)-1:
                pv = p[pi]*p[pi+1]
            if mi < len(m)-1:
                mv = m[mi]*m[mi+1]

            if pv > mv:
                ans = (ans*p[pi]) % MOD
                pi += 2
            else:
                ans = (ans*mv) % MOD
                mi += 2
            K -= 2
        else:
            ans = 0
            break
    print(ans)

Submission status: Wrong Answer

Solution code:
n, k = (int(x) for x in input().split())
A = list(int(x) for x in input().split())
MOD = 10**9 + 7
P = []
M = []
Z = []
for a in A:
    if a < 0:
        M.append(a)
    elif a > 0:
        P.append(a)
    else:
        Z.append(a)
P.sort()
M.sort(reverse=True)
lp = len(P)
lm = len(M)
lz = len(Z)

# どうしてもマイナスになるとき
if (lp + lm < k) or (lm == n and k % 2 == 1) or (lp == 0 and lm % 2 == 1):
    if lz > 0:
        print(0)
        exit()
    else:
        P += [-m for m in M]
        P.sort()
        tmp = 1
        for i in range(k):
            tmp *= P[i]
            tmp %= MOD
        print(-tmp % MOD)
        exit()

# プラスにできそうなとき
ans = 1
pindex = lp-1
mindex = lm-1
for _ in range(k // 2):
    if pindex > 0 and mindex > 0:
        p = P[pindex] * P[pindex - 1]
        m = M[mindex] * M[mindex - 1]
        if p > m:
            p %= MOD
            ans *= p
            ans %= MOD
            pindex -= 2
        else:
            m %= MOD
            ans *= m
            ans %= MOD
            mindex -= 2
    else:
        if pindex > 0:
            ans *= (P[pindex] * P[pindex - 1]) % MOD
            ans %= MOD
            pindex -= 2
        elif mindex > 0:
            ans *= (M[mindex] * M[mindex - 1]) % MOD
            ans %= MOD
            mindex -= 2
        else:
            print("ERROR!!!!")

if k % 2 == 0:
    print(ans)
    exit()
else:
    if pindex >= 0:
        ans *= P[pindex]
        ans %= MOD
        print(ans)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
m = 10**9+7
pos = [*filter(lambda x: x>=0, A)]
neg = [*filter(lambda x: x<0, A)]
pos.sort(reverse=True)
neg.sort()

ans = 1
i,j = 0,0# 使った数
while i+j < K:
    flag = True
    if i == len(pos):
        flag = False
    elif j == len(neg):
        flag = True
    elif pos[i] >= -neg[j]:
        flag = True
    else:
        flag = False

    if flag:
        ans = ans * pos[i] % m
        i += 1
    else:
        ans = ans * neg[j] % m
        j += 1

if j % 2 == 0 or N==K:
    print(ans)
elif len(pos) == 0:
    ans = 1
    for i in range(K):
        ans = ans * neg[len(neg)-1-i] % m
    print(ans)
else:
    flag2 = True
    if i == len(pos):
        flag2 = False
    elif j == len(neg):
        flag2 = True
    elif pos[i-1]*pos[i] > neg[j-1]*neg[j]:# = を抜いた
        flag2 = True
    else:
        flag2 = False

    if flag2:
        ans = ans * pow(neg[j-1],m-2,m) % m
        ans = ans * pos[i] % m
    else:
        ans = ans * pow(pos[i-1],m-2,m) % m
        ans = ans * neg[j] % m
    print(ans)