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
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
#import numba

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

    plus = [a for a in A if a >= 0]
    minus = [-a for a in A if a < 0]

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

    P, M  = [1], [1]
    for p in plus:
        P.append((P[-1] * p) % mod)
    for m in minus:
        M.append(((M[-1] * (-m)) % mod))
    #print(P, M)
    max_ans = -1

    for i in range(K, -1, -2):
        if len(plus) < i:continue
        if len(minus) < K - i:continue
        if max_ans == -1:
            max_ans = P[i] * M[K-i] % mod
        else:
            if not plus[i] or not plus[i + 1]:
                max_ans = P[i] * M[K-i] % mod
                continue
            if plus[i+1] / minus[K-i-1] < minus[K-i-2] / plus[i]:
                max_ans = P[i] * M[K-i] % mod

    if max_ans == -1:
        plus = plus[::-1]
        minus = minus[::-1]
        P, M = [1], [1]
        for p in plus:
            P.append((P[-1] * p) % mod)
        for m in minus:
            M.append(((M[-1] * (-m)) % mod))

        for i in range(K-1, -1, -2):
            if len(plus) < i: continue
            if len(minus) < K - i: continue
            if max_ans == -1:
                max_ans = P[i] * M[K - i] % mod
            else:
                if not plus[i] or not plus[i+1]:
                    max_ans = 0
                    break
                if plus[i + 1] / minus[K - i - 1] > minus[K - i - 2] / plus[i]:
                    max_ans = P[i] * M[K - i] % mod

    print(max_ans)

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

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

plus = []
minus = []

for i in a:
	if i >= 0:
		plus.append(i)
	else:
		minus.append(i)

plus.sort()
minus.sort()

#print(plus, minus)

"""
貪欲チックに求める
numplus … 前からnumplus番目まで掛け合わせる
numminus … 前からnumminus番目まで掛け合わせる

入力例2に合わせるのは場合分けが必要だが, minusは2個単位で管理する.
"""
numplus = k
numminus = 0

"""
kがplusを超える場合, うまく処理ができないのでリスト参照できる範囲まで下げる.
"""
while numplus > len(plus):
	numplus -= 2
	numminus += 2

tmpminus = -1

#print(numplus, numminus)

while numplus-2 >= 0 and numminus+1 < len(minus):
	if plus[numplus-1] * plus[numplus-2] <= minus[numminus] * minus[numminus+1]:
		numplus -= 2
		numminus += 2
		tmpminus = numminus
	else:
		break

#print(tmpminus, tmpplus)

ans = 1
if tmpminus != -1:
	plus = plus[::-1]
	for i in range(numplus):
		ans = ans * plus[i] % mod
	for i in range(numminus):
		ans = ans * minus[i] % mod
else:
	"""
	これは, ansが負になる場合や, minusが1個だけの場合, minusしかない場合, plusしかない場合に使える.
	"""
	#print("ここに来ました！")
	tmp = sorted(a, key=lambda x:-x)
	for i in range(k):
		ans = ans * tmp[i]%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
        
        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:
                ans = ans * modinv(Ap[ip]) % MOD
                ip -= 1
            if im > 0:
                ans = ans * modinv(Am[im]) % MOD
                im -= 1
            # 正、負のリストから、まだ選んでない中で絶対値が大きいもの2つを選び、その積の大きいほうを選ぶ
            a = Ap[ip] * Ap[ip+1]
            b = Am[im] * Am[im+1]

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

    print(ans)

if __name__ == '__main__':
    main()

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
    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())
a = list(map(int,input().split()))
mod = 10**9 + 7

plus = []
minus = []

for i in a:
	if i >= 0:
		plus.append(i)
	else:
		minus.append(i)

plus.sort()
minus.sort(key=lambda x:-x)

#print(plus, minus)

"""
貪欲チックに求める
numplus … 前からnumplus番目まで掛け合わせる
numminus … 前からnumminus番目まで掛け合わせる

入力例2に合わせるのは場合分けが必要だが, minusは2個単位で管理する.
"""
numplus = k
numminus = 0

"""
kがplusを超える場合, うまく処理ができないのでリスト参照できる範囲まで下げる.
"""
while numplus > len(plus):
	numplus -= 2
	numminus += 2

tmpminus = -1

#print(numplus, numminus)

while numplus-2 >= 0 and numminus+1 < len(minus):
	if plus[numplus-1] * plus[numplus-2] <= minus[numminus] * minus[numminus+1]:
		numplus -= 2
		numminus += 2
		tmpminus = numminus
	else:
		break

#print(tmpminus, tmpplus)

ans = 1
if tmpminus != -1:
	for i in range(numplus):
		ans = ans * plus[i] % mod
	for i in range(numminus):
		ans = ans * minus[i] % mod
else:
	"""
	これは, ansが負になる場合や, minusが1個だけの場合, minusしかない場合, plusしかない場合に使える.
	"""
	#print("ここに来ました！")
	tmp = sorted(a, key=lambda x:-x)
	for i in range(k):
		ans = ans * tmp[i]%mod

print(ans)

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:
    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:
n, k = map(int, input().split())
a = list(map(int,input().split()))

a_p =[]
a_m =[]
for i in a:
    if i >= 0:
        a_p.append(i)
    else :
        a_m.append(i)

a_p.sort()
a_m.sort(reverse=True)


a_select =[]

if n == k:
    a_select = a
elif len(a_p) == 0:
    for i in range(k):
        a_select.append(a_m[i])


while len(a_select) < k:
    if len(a_select) == k - 1:
        a_select.append(a_p[-1])
        break
    if len(a_p) == 1 and (k-len(a_select))%2 == 1:
        a_select.append(a_p.pop(-1))
    elif len(a_p) == 1 and (k-len(a_select))%2 == 0:
        a_select.append(a_m.pop(-1))
        a_select.append(a_m.pop(-1))
    elif len(a_p) == 0:
        a_select.append(a_m.pop(-1))
        a_select.append(a_m.pop(-1))
    elif len(a_m) <= 1:
        a_select.append(a_p.pop(-1))
    elif a_p[-1]*a_p[-2] > a_m[-1]*a_m[-2] :
        a_select.append(a_p.pop(-1))
    else:
        a_select.append(a_m.pop(-1))
        a_select.append(a_m.pop(-1))

#print(a_select)
ans = 1
for i in a_select:
    ans = ans*i % (10**9 + 7)

print(ans)

Submission status: Wrong Answer

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

As.sort()
dic = {-1:0, 1:0}
for a in As:
  if a < 0:
    dic[-1] += 1
  else:
    dic[1] += 1

rlt = 1
j = 0
if N == K:
  for a in As:
    rlt *= a
    rlt %= P
  while rlt < 0:
    rlt += P
elif As[N-1] < 0 and K%2 == 1:
  for i in range(1,K+1):
    rlt *= As[-i]
    rlt %= P
  while rlt < 0:
    rlt += P
else:
  s = 0
  i = 0
  j = 1
  while s < K:
    if i+1 >= dic[-1] or s+1 == K:
      rlt *= As[-j]
      rlt %= P
      j += 1
      s += 1
    elif j+1 > dic[1]:
      rlt *= As[i]*As[i+1]
      rlt %= P
      j += 2
      s += 2
    else:
      if As[i]*As[i+1] > As[-j]*As[-(j+1)]:
        rlt *= As[i]*As[i+1]
        rlt %= P
        j += 2
        s += 2
      else:
        rlt *= As[-j]
        rlt %= P
        j += 1
        s += 1
        
print(rlt)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

def list_safe_get(l, index, default=None):
    if 0 < index < len(l):
        return l[index]
    return default

class ModInt(int):

    MOD = 10 ** 9 + 7

    def __add__(self, other):
        self = ModInt(int.__add__(self, other) % ModInt.MOD)
        return self

    def __mul__(self, other):
        self = ModInt(int.__mul__(self, other) % ModInt.MOD)
        return self

def mysplit(data):
    ps = [] # include 0
    ms = []
    for d in data:
        if d < 0:
            ms.append(ModInt(d))
        else:
            ps.append(ModInt(d))
    return list(reversed(sorted(ps))), sorted(ms)

def small_abs(ms, k):
    ans = ModInt(1)
    ms = list(reversed(ms))
    for i in range(k):
        ans *= ModInt(ms[i])
    return ans

def factor_all(ps, pk, ms, mk):
    ans = ModInt(1)
    for i in range(pk):
        #print('ps[i]', ps[i]) # debug
        ans *= ps[i]
    for i in range(mk):
        #print('ms[i]', ms[i]) # debug
        ans *= ms[i]
    return ans

def adjust(ps, pk, ms, mk):
    if pk == 0:
        return pk + 1, mk - 1
    if mk == 0:
        return pk - 1, mk + 1
    if pk == len(ps):
        return pk - 1, mk + 1
    if mk == len(ms):
        return pk + 1, mk - 1
    cand_rm_p = ps[pk - 1]
    cand_add_m = ms[mk]
    cand_rm_m = ms[mk - 1]
    cand_add_p = ps[pk]
    if cand_rm_m * cand_add_m > cand_rm_p * cand_add_p:
        return pk - 1, mk + 1
    else:
        return pk + 1, mk - 1

def solve(data, k):
    if len(data) == k:
        ans = ModInt(1)
        for d in data:
            ans *= d
        return ans % ModInt.MOD
    ps, ms = mysplit(data)
    if len(ps) == 0:
        return small_abs(ms, k)
    pk = 0
    mk = 0
    while k > 0:
        if pk >= len(ps):
            mk += 1; k -= 1; continue
        if mk >= len(ms):
            pk += 1; k -= 1; continue
        if ps[pk] > -1 * ms[mk]:
            pk += 1; k -= 1; continue
        else:
            mk += 1; k -= 1; continue
    #print('pk, mk') # debug
    #print(pk, mk) # debug
    if mk % 2 != 0:
        pk, mk = adjust(ps, pk, ms, mk)
    #print('pk, mk') # debug
    #print(pk, mk) # debug
    return factor_all(ps, pk, ms, mk)


if __name__ == '__main__':
    n, k = list(map(int, input().split()))
    data = list(map(int, input().split()))
    ans = solve(data, k)
    #print('ans') # debug
    print(ans)



    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Wrong Answer

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

plus = []
minus = []

for i in a:
	if i >= 0:
		plus.append(i)
	else:
		minus.append(i)

plus.sort(key=lambda x:-x)
minus.sort()

#print(plus, minus)

"""
貪欲チックに求める
numplus … 前からnumplus番目まで掛け合わせる
numminus … 前からnumminus番目まで掛け合わせる

入力例2に合わせるのは場合分けが必要だが, minusは2個単位で管理する.
"""
numplus = k
numminus = 0

"""
kがplusを超える場合, うまく処理ができないのでリスト参照できる範囲まで下げる.
"""
while numplus > len(plus):
	numplus -= 2
	numminus += 2

tmpminus = -1

#print(numplus, numminus)

while numplus-2 >= 0 and numminus+1 < len(minus) and numminus >= 0:
	if plus[numplus-1] * plus[numplus-2] <= minus[numminus] * minus[numminus+1]:
		numplus -= 2
		numminus += 2
		tmpminus = numminus
	else:
		break

#print(tmpminus, tmpplus)

ans = 1
if tmpminus != -1:
	for i in range(numplus):
		ans = ans * plus[i] % mod
	for i in range(numminus):
		ans = ans * minus[i] % mod
else:
	"""
	これは, ansが負になる場合や, minusが1個だけの場合, minusしかない場合, plusしかない場合に使える.
	"""
	#print("ここに来ました！")
	tmp = sorted(a, key=lambda x:-x)
	for i in range(k):
		ans = ans * tmp[i]%mod

print(ans)

Submission status: Wrong Answer

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

list.sort(a, reverse=True)
total = 1
count_a = 0
count_b = N-1


if a[0]<0 and K%2 != 0:
	for i in range(N):
		a[i] = abs(a[i])
	list.sort(a, reverse=False)
	for i in range(K):
		total *= a[i]
		total  =total%(10**9 +7)
	total *= -1
	total  =total%(10**9 +7)
else:
	while K>0:
		if K> 1:
			if a[count_a]*a[count_a+1] >a[count_b]*a[count_b-1]:
				total *= a[count_a] * a[count_a+1]
				total  =total%(10**9 +7)
				count_a += 2
			else:
				total *= a[count_b]*a[count_b-1]
				count_b -= 2
				total  =total%(10**9 +7)
			K-=2
		else:
			total *= max( a[count_a], a[count_b])
			total  =total%(10**9 +7)
		K -= 1
print(total)

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):
    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()

if lp + lm == k:
    raise SystemExit

# プラスにできそうなとき
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:
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 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:
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)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
n,k = map(int,input().split())
a_list = sorted(map(int,input().split()))
mod = 10**9+7
if n-k < a_list.count(0):
    print(0)
    exit()
if (sum([1 for a in a_list if np.sign(a)!=-1])==0 and k%2==1) or (k==n and len([1 for a in a_list if np.sign(a)==-1])%2==1):
    a_list.sort(key = abs)
    ans = 1
    for num in a_list[:k]:
        ans *= num
        ans %= mod
    print(ans)
    exit()
else:
    a_list.sort(key = abs,reverse = True)
    add = 1
    remove = 1
    if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
        negative_big = [num for num in a_list[:k] if np.sign(num)==-1]
        positive_big = [num for num in a_list[:k] if np.sign(num)!=-1]
        negative_small = [num for num in a_list[k:] if np.sign(num)==-1]
        positive_small = [num for num in a_list[k:] if np.sign(num)!=-1]
        
        
        if len(negative_big)==0 or len(positive_small)==0:
            remove = min(positive_big)
            add = min(negative_small)
        elif len(positive_big)==0 or len(negative_small)==0:
            remove = max(negative_big)
            add = max(positive_small)
        else:
            positive_small_max = max(positive_small)
            negative_big_max = max(negative_big)
            negative_small_min = min(negative_small)
            positive_big_min = min(positive_big)
            if positive_small_max/negative_big_max < negative_small_min/positive_big_min:
                remove = negative_big_max
                add = positive_small_max
            else:
                remove = positive_big_min
                add = negative_small_min
ans = 1
for num in a_list[:k]:
    ans *= num
    ans %= mod
    
if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
    ans *= add
    ans %= mod
    ans *= pow(remove, mod-2, mod)
    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 = []

for i in a:
	if i >= 0:
		plus.append(i)
	else:
		minus.append(i)

plus.sort(key=lambda x:-x)
minus.sort()

#print(plus, minus)

"""
貪欲チックに求める
numplus … 前からnumplus番目まで掛け合わせる
numminus … 前からnumminus番目まで掛け合わせる

入力例2に合わせるのは場合分けが必要だが, minusは2個単位で管理する.
"""
numplus = k
numminus = 0

"""
kがplusを超える場合, うまく処理ができないのでリスト参照できる範囲まで下げる.
"""
while numplus > len(plus):
	numplus -= 2
	numminus += 2

tmpminus = -1

#print(numplus, numminus)

while numplus-2 >= 0 and numminus+1 < len(minus):
	if plus[numplus-1] * plus[numplus-2] <= minus[numminus] * minus[numminus+1]:
		numplus -= 2
		numminus += 2
		tmpminus = numminus
	else:
		break

#print(tmpminus, tmpplus)

ans = 1
if tmpminus != -1:
	for i in range(numplus):
		ans = ans * plus[i] % mod
	for i in range(numminus):
		ans = ans * minus[i] % mod
else:
	"""
	これは, ansが負になる場合や, minusが1個だけの場合, minusしかない場合, plusしかない場合に使える.
	"""
	#print("ここに来ました！")
	tmp = sorted(a, key=lambda x:-x)
	for i in range(k):
		ans = ans*tmp[i]%mod

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):
    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

AA = []
for a in A:
    AA.append((a, abs(a)))

AA.sort(key=lambda x: x[1], reverse=True)
ans = 1

if K&1 and all([0>x for x in A]):
    AAA = list(reversed(AA))
    for a in AAA[:K]:
        # print(a)
        ans *= a[0] % M
    # print(ans)
    ans %= M
    print(ans)
    exit(0)

for x in range(K):
    ans *= (AA[x][0] % M)
ans %= M
if ans > 0:
    print(ans)
    exit(0)
else:
    #マイナスを抜いて、プラスを足すか、プラスを抜いて、マイナスを入れるか

    ## マイナス抜く
    mans = ans
    for ri in reversed(AA[:K]):
        if ri[0] < 0:
            mans /= ri[0]%M
            break
    for i, _ in AA[K:]:
        if i > 0:
            mans *= i %M
    
    pans = ans
    for ri in reversed(AA[:K]):
        if ri[0] > 0:
            pans /= ri[0]%M
            break

    for i, _ in AA[K:]:
        if i < 0:
            mans *= i %M
    
    if mans > pans:
        ans = mans
    else:
        ans = pans
    
    print(ans)
    exit(0)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

def list_safe_get(l, index, default=None):
    if 0 < index < len(l):
        return l[index]
    return default

class ModInt(int):

    MOD = 10 ** 9 + 7

    def __add__(self, other):
        self = ModInt(int.__add__(self, other) % ModInt.MOD)
        return self

    def __mul__(self, other):
        self = ModInt(int.__mul__(self, other) % ModInt.MOD)
        return self

def mysplit(data):
    ps = [] # include 0
    ms = []
    for d in data:
        if d < 0:
            ms.append(ModInt(d))
        else:
            ps.append(ModInt(d))
    return list(reversed(sorted(ps))), sorted(ms)

def small_abs(ms, k):
    ans = ModInt(1)
    ms = list(reversed(ms))
    for i in range(k):
        ans *= ms[i]
    return ans

def factor_all(ps, pk, ms, mk):
    ans = ModInt(1)
    for i in range(pk):
        #print('ps[i]', ps[i]) # debug
        ans *= ps[i]
    for i in range(mk):
        #print('ms[i]', ms[i]) # debug
        ans *= ms[i]
    return ans

def adjust(ps, pk, ms, mk):
    if pk == 0:
        return pk + 1, mk - 1
    if mk == 0:
        return pk - 1, mk + 1
    if pk == len(ps):
        return pk - 1, mk + 1
    if mk == len(ms):
        return pk + 1, mk - 1
    cand_rm_p = ps[pk - 1]
    cand_add_m = ms[mk]
    cand_rm_m = ms[mk - 1]
    cand_add_p = ps[pk]
    if cand_rm_m * cand_add_m > cand_rm_p * cand_add_p:
        return pk - 1, mk + 1
    else:
        return pk + 1, mk - 1

def solve(data, k):
    if len(data) == k:
        ans = ModInt(1)
        for d in data:
            ans *= d
        return ans
    ps, ms = mysplit(data)
    if len(ps) == 0:
        return small_abs(ms, k)
    pk = 0
    mk = 0
    while k > 0:
        if pk >= len(ps):
            mk += 1; k -= 1; continue
        if mk >= len(ms):
            pk += 1; k -= 1; continue
        if ps[pk] > -1 * ms[mk]:
            pk += 1; k -= 1; continue
        else:
            mk += 1; k -= 1; continue
    #print('pk, mk') # debug
    #print(pk, mk) # debug
    if mk % 2 != 0:
        pk, mk = adjust(ps, pk, ms, mk)
    #print('pk, mk') # debug
    #print(pk, mk) # debug
    return factor_all(ps, pk, ms, mk)


if __name__ == '__main__':
    n, k = list(map(int, input().split()))
    data = list(map(int, input().split()))
    ans = solve(data, k)
    #print('ans') # debug
    print(ans)



    #print('\33[32m' + 'end' + '\033[0m') # debug

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):
    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)