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:
MOD = 10**9 + 7

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math
def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()
n,k = MI()
a = LI()
mod = 10**9+7
x = []
y = []
for i in range(n):
	if a[i]<0:
		x.append(a[i])
	else:
		y.append(a[i])
x2 = []
x.sort()
x3 = []
pro = 1
for i in range(0,len(x)):
	pro*=x[i]
	if pro>=mod:
		pro%=mod
	elif pro<=-mod:
		pro*=-1
		pro%=mod
		pro*=-1
	x2.append(pro)
x = x[:][::-1]
pro = 1
for i in range(0,len(x)):
	pro*=x[i]
	x3.append(pro)
y.sort(reverse  = True)
y2 = []
pro = 1
for i in range(len(y)):
	pro*=y[i]
	pro%=mod
	y2.append(pro)
l1 = len(x2)
l2 = len(y2)
if k>l1+l2:
	print(0)
else:
	m = -10**9-7
	for i in range(-1,l1):
		if i+1>k:
			break
		if i == -1:
			if l2>=k:
				m = max(m,y2[k-1])
		else:
			if l2>=k-i-1:
				if k-i-2>=0:
					m = max(m,x2[i]*y2[k-i-2])
				else:
					m = max(m,x2[i])
	for i in range(-1,l1):
		if i+1>k:
			break
		if i == -1:
			if l2>=k:
				m = max(m,y2[k-1])
		else:
			if l2>=k-i-1:
				if k-i-2>=0:
					m = max(m,x3[i]*y2[k-i-2])
				else:
					m = max(m,x3[i])
	print(m%(10**9+7))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 1000000007

zeros = []
pluss = []
minuss = []

for i in range(N):
    if A[i]>0:
        pluss.append(A[i])
    elif A[i]==0:
        zeros.append(A[i])
    else:
        minuss.append(A[i])

pluss = sorted(pluss, reverse = True)
minuss = sorted(minuss)

if len(pluss) + (min(len(minuss), K)//2)*2 >= K:
    answer_type = 1
elif len(zeros) > 0:
    answer_type = 2
else:
    answer_type = 3


#%%
rest = K
if answer_type == 1:
    plus_now = 0
    minus_now = 0
    minus_counter = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = -1000000000000
        
        if minus_now < len(minuss):
            minus_target = -minuss[minus_now]
        else:
            minus_target = -1000000000000
        
        if plus_target >= minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
            minus_counter += 1
    
    if minus_counter%2 == 1:
        if minus_now >= len(minuss):
            answer = answer * pow(-minuss[minus_now-1],mod-2,mod)
            answer = answer * pluss[plus_now]
        elif plus_now >= len(pluss):
            answer = answer * pow(pluss[plus_now-1],mod-2,mod)
            answer = answer * -minuss[minus_now]
        elif pluss[plus_now]/(-1*minuss[minus_now-1]) > -1*minuss[minus_now]/(pluss[plus_now-1]):
            answer = answer * pow(-minuss[minus_now-1],mod-2,mod)
            answer = answer * pluss[plus_now]
        else:
            answer = answer * pow(pluss[plus_now-1],mod-2,mod)
            answer = answer * pluss[plus_now]


elif answer_type == 2:
    answer = 0
elif answer_type == 3:
    minuss = sorted(minuss, reverse = True)
    pluss = sorted(pluss, reverse = True)
    plus_now = 0
    minus_now = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = 10000000000000
        
        if minus_now < len(minuss):
            minus_target = minuss[minus_now]
        else:
            minus_target = -1000000000000  
        
        if plus_target <= -minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
print(answer%mod)

Submission status: Wrong Answer

Solution code:
import sys
import math
def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()
n,k = MI()
a = LI()
mod = 10**9+7
x = []
y = []
for i in range(n):
	if a[i]<0:
		x.append(a[i])
	else:
		y.append(a[i])
x2 = []
x.sort()
x3 = []
pro = 1
for i in range(0,len(x)):
	pro*=x[i]
	pro%=mod
	x2.append(pro)
x = x[:][::-1]
pro = 1
for i in range(0,len(x)):
	pro*=x[i]
	pro%=mod
	x3.append(pro)
y.sort(reverse  = True)
y2 = []
pro = 1
for i in range(len(y)):
	pro*=y[i]
	pro%=mod
	y2.append(pro)
l1 = len(x2)
l2 = len(y2)
m = -10**9-7
for i in range(-1,l1):
	if i+1>k:
		break
	if i == -1:
		if l2>=k:
			m = max(m,y2[k-1])
	else:
		if l2>=k-i-1:
			if k-i-2>=0:
				m = max(m,x2[i]*y2[k-i-2])
			else:
				m = max(m,x2[i])
for i in range(-1,l1):
	if i+1>k:
		break
	if i == -1:
		if l2>=k:
			m = max(m,y2[k-1])
	else:
		if l2>=k-i-1:
			if k-i-2>=0:
				m = max(m,x3[i]*y2[k-i-2])
			else:
				m = max(m,x3[i])
print(m%(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 max(a)<0:
  if k%2:a.sort(reverse=1)
  else:a.sort()
  ans=1
  for i in a[:k]:ans=(ans*i)%mod
  exit(print(ans))
p=[(0,0)]
m=[(0,0)]
for i in a:
  if i<0:m.append((-i,1))
  else:p.append((i,0))
pp=mm=1
p.sort()
m.sort()
oe=0
ans=1
for i in range(k):
  if p[-1][0]>m[-1][0]:
    t,f=p.pop()
    pp=t
  else:
    t,f=m.pop()
    mm=t
  ans=(ans*t)%mod
  if ans==0:exit(print(0))
  oe^=f
if oe:
  if pp*p[-1][0]>mm*m[-1][0]:
    ans=(ans*pow(mm,mod-2,mod)*p[-1][0])%mod
  else:
    ans=(ans*pow(pp,mod-2,mod)*m[-1][0])%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

pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(a)

flag = False  # 積を正にできるか

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


if len(pos) > 0:
    flag = True
else:
    if K % 2 == 0:
        flag = True

ans = 1
if not flag:
    # 積を正にできないとき
    # 絶対値の小さい方からK個とる
    A = sorted([abs(x) for x in A])
    for a in A[:K]:
        ans *= a % MOD
    ans *= -1
else:
    pos.sort(reverse=True)
    neg.sort()
    if K % 2 == 1:
        # Kが奇数の時
        # 一番大きい偶数を1つとる。
        ans *= pos.pop() % MOD

    # pos, neg sort -> 2個ずつペア -> 降順sort -> 上から K//2 個とる
    pairs = []
    while len(pos) >= 2:
        x = pos.pop()
        x *= pos.pop()
        pairs.append(x)
    while len(neg) >= 2:
        x = neg.pop()
        x *= neg.pop()
        pairs.append(x)
    pairs = sorted(pairs, reverse=True)
    for p in pairs[: K // 2]:
        ans *= p % MOD

print(ans % MOD)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = [int(i) for i in input().split()]

mod = 10**9+7

pl = 0
zr = 0
mn = 0

a.sort()

for i in range(n):
    if a[i] == 0:
        zr += 1
    elif a[i] > 0:
        pl += 1
    elif a[i] < 0:
        mn += 1

hugo = 0

tmp = k-pl
        
if zr == 0 and pl == 0 and k % 2 == 1:
    hugo = 3#mn
elif zr == 1 and pl == 0 and k % 2 == 1:
    hugo = 2#zr
else:
    hugo = 1#pl

ans = 1
tmp_ans = 1
    
if hugo == 3:
    for i in range(k):
        ans *= a[mn-1-i]
        ans %= mod
    print(ans%mod)
elif hugo == 2:
    print(0)
else:
    if mn == 0:
        for i in range(k):
            tmp_ans *= a[n-1-i]
            tmp_ans %= mod
        print(tmp_ans)
    else:
        tmp = k
        pl_num = 0
        mn_num = 0
        if tmp % 2 == 1:
            tmp -= 1
            k -= 1
            pl_num += 1
            tmp_ans = a[n-1]
        while tmp > 0:
            if tmp >= 2:
                tmp -= 2
                tmp_p_seki = 1
                tmp_m_seki = 1
                if pl_num+1 <= pl:
                    tmp_p_seki = a[n-1-pl_num]*a[n-1-pl_num-1]
                if mn_num+1 <= mn:
                    tmp_m_seki = a[mn_num+0]*a[mn_num+1]
                if tmp_p_seki > tmp_m_seki:
                    tmp_seki = tmp_p_seki
                    pl_num += 2
                else:
                    tmp_seki = tmp_m_seki
                    mn_num += 2
            elif tmp == 1:
                tmp_seki = a[n-1-pl_num]
                tmp -= 1
            tmp_ans *= tmp_seki
            tmp_ans %= mod
                    
            
        print(tmp_ans%mod)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = [int(i) for i in input().split()]

mod = 10**9+7

pl = 0
zr = 0
mn = 0

a.sort()

for i in range(n):
    if a[i] == 0:
        zr += 1
    elif a[i] > 0:
        pl += 1
    elif a[i] < 0:
        mn += 1

hugo = 0

tmp = k-pl
        
if zr == 0 and pl == 0 and k % 2 == 1:
    hugo = 3#mn
elif zr == 1 and pl == 0 and k % 2 == 1:
    hugo = 2#zr
else:
    hugo = 1#pl

ans = 1
tmp_ans = 1
    
if hugo == 3:
    for i in range(k):
        ans *= a[mn-1-i]
        ans %= mod
    print(ans%mod)
elif hugo == 2:
    print(0)
else:
    if mn == 0:
        for i in range(k):
            tmp_ans *= a[n-1-i]
            tmp_ans %= mod
        print(tmp_ans)
    else:
        tmp = k
        pl_num = 0
        mn_num = 0
        if tmp % 2 == 1:
            k -= 1
            pl_num += 1
            tmp_ans = a[n-1]
        while tmp > 0:
            if tmp >= 2:
                tmp -= 2
                tmp_p_seki = 1
                tmp_m_seki = 1
                if pl_num+1 <= pl:
                    tmp_p_seki = a[n-1-pl_num]*a[n-1-pl_num-1]
                if mn_num+1 <= mn:
                    tmp_m_seki = a[mn_num+0]*a[mn_num+1]
                if tmp_p_seki > tmp_m_seki:
                    tmp_seki = tmp_p_seki
                    pl_num += 2
                else:
                    tmp_seki = tmp_m_seki
                    mn_num += 2
            elif tmp == 1:
                tmp_seki = a[n-1-pl_num]
                tmp -= 1
            tmp_ans *= tmp_seki
            tmp_ans %= mod
                    
            
        print(tmp_ans%mod)

Submission status: Wrong Answer

Solution code:
import sys
import math
def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()
n,k = MI()
a = LI()
mod = 10**9+7
x = []
y = []
for i in range(n):
	if a[i]<0:
		x.append(a[i])
	else:
		y.append(a[i])
x2 = []
x.sort()
x3 = []
pro = 1
for i in range(0,len(x)):
	pro*=x[i]
	if pro>=mod:
		pro%=mod
	elif pro<=-mod:
		pro*=-1
		pro%=mod
		pro*=-1
	x2.append(pro)
x = x[:][::-1]
pro = 1
for i in range(0,len(x)):
	pro*=x[i]
	if pro>=mod:
		pro%=mod
	elif pro<=-mod:
		pro*=-1
		pro%=mod
		pro*=-1
	x3.append(pro)
y.sort(reverse  = True)
y2 = []
pro = 1
for i in range(len(y)):
	pro*=y[i]
	pro%=mod
	y2.append(pro)
l1 = len(x2)
l2 = len(y2)
m = -10**9-7
for i in range(-1,l1):
	if i+1>k:
		break
	if i == -1:
		if l2>=k:
			m = max(m,y2[k-1])
	else:
		if l2>=k-i-1:
			if k-i-2>=0:
				m = max(m,x2[i]*y2[k-i-2])
			else:
				m = max(m,x2[i])
for i in range(-1,l1):
	if i+1>k:
		break
	if i == -1:
		if l2>=k:
			m = max(m,y2[k-1])
	else:
		if l2>=k-i-1:
			if k-i-2>=0:
				m = max(m,x3[i]*y2[k-i-2])
			else:
				m = max(m,x3[i])
print(m%(10**9+7))

Submission status: Wrong Answer

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

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])
ans, num, cnt = 1, [], 0

for _ in range(k):
    if len(mia) == 0 or (len(pla) > 0 and abs(mia[-1]) <= pla[-1]):
        tmp = pla.pop()
    elif len(pla) == 0 or (len(mia) > 0 and abs(mia[-1]) > pla[-1]):
        tmp = mia.pop()
        cnt += 1
    num.append(tmp)
    ans = ans * tmp % mod

if cnt % 2 == 1:
    p, q, r, s = 1, 0, -1, 0
    if len(mia) > 0 and cnt != k:
        p, q = min(i for i in num if i >= 0), mia[-1]
    if len(pla) > 0:
        r, s = max(i for i in num if i < 0), pla[-1]
    if len(mia) > 0 or (len(pla) > 0 and cnt != k):
        if q * r >= p * s:
            ans *= q * pow(p, mod - 2, mod)
        if q * r < p * s:
            ans *= s * pow(r, mod - 2, mod)
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
na = a[:bisect_left(a, 0)]
pa = a[bisect_right(a, 0):][::-1]
mod = 10**9+7
if k==n:
    ans = 1
    for i in a:
        ans *= i
        ans %= mod
    print(ans)
    exit(0)
if k%2==1 and len(pa)==0:
    ans = 1
    for i in a[::-1][:k]:
        ans *= i
        ans %= mod
    print(ans)
    exit(0)
if k==1:
    print(a[-1])
    exit(0)
na += [0]*n
pa += [0]*n
nn = 0
pn = 0
ans = 1
for i in range(k//2):
    if i==k//2-1 and k%2==1:
        break
    if pa[pn]*pa[pn+1]>=na[nn]*na[nn+1]:
        ans *= pa[pn]*pa[pn+1]
        pn += 2
    else:
        ans *= na[nn]*na[nn+1]
        nn += 2
    ans %= mod
if k%2==1:
    ans *= max(pa[pn]*pa[pn+1]*pa[pn+2], na[nn]*na[nn+1]*pa[pn])
print(ans%mod)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
na = a[:bisect_left(a, 0)]
pa = a[bisect_right(a, 0):][::-1]
mod = 10**9+7
if k==n:
    ans = 1
    for i in a:
        ans *= i
        ans %= mod
    print(ans)
    exit(0)
if k%2==1 and len(pa)==0:
    ans = 1
    for i in a[::-1][:k]:
        ans *= i
        ans %= mod
    print(ans)
    exit(0)
na += [0]*n
pa += [0]*n
nn = 0
pn = 0
ans = 1
for i in range(k//2):
    if i==k//2-1 and k%2==1:
        break
    if pa[pn]*pa[pn+1]>=na[nn]*na[nn+1]:
        ans *= pa[pn]*pa[pn+1]
        pn += 2
    else:
        ans *= na[nn]*na[nn+1]
        nn += 2
    ans %= mod
if k%2==1:
    ans *= max(pa[pn]*pa[pn+1]*pa[pn+2], na[nn]*na[nn+1]*pa[pn])
print(ans%mod)

Submission status: Wrong Answer

Solution code:
# Contest No.: ABC173
# Problem No.: E
# Solver:      JEMINI
# Date:        20200705

import sys
import heapq

def main():
    modVal = 10 ** 9 + 7
    # parsing
    n, k = map(int, sys.stdin.readline().split())
    nums = list(map(int, sys.stdin.readline().split()))
    
    # edge case; n == k
    if n == k:
        ans = 1
        for i in nums:
            ans *= i % modVal
            ans %= modVal
        print(ans)
        return
    
    # edge case; all neg
    if max(nums) < 0:
        nums.sort()
        ans = 1
        # odd k
        if k % 2:
            for i in range(k):
                ans *= nums[-i - 1] % modVal
                ans %= modVal
        # even k
        else:
            for i in range(k):
                ans *= nums[i] % modVal
                ans %= modVal
        print(ans)
        return
    
    # convert to absolute value & count zeros
    absNums = []
    zeroCnt = 0
    for i in nums:
        if i == 0:
            zeroCnt += 1
        else:
            absNums.append([abs(i), i])
    absNums.sort()  # sorted by absolute value
    
    # edge case; non-zero is less than k
    if len(absNums) < k:
        print(0)
        return

    posOverK = []
    posLessK = []
    negOverK = []
    negLessK = []
    for i in range(k):
        temp = absNums.pop()
        if temp[1] > 0:
            posOverK.append(temp[0])
        else:
            negOverK.append(temp[0])
    while absNums:
        temp = absNums.pop()
        if temp[1] > 0:
            posLessK.append(temp[0])
        else:
            negLessK.append(temp[0])
    
    # all values are absolute value
    posOverK.sort()
    posLessK.sort()
    negOverK.sort()
    negLessK.sort()
    ans = 1

    # odd negative numbers; if able, change to even
    if len(negOverK) % 2:
        minNeg = None
        minPos = None
        if posOverK:
            minPos = posOverK[0]
        if negOverK:
            minNeg = negOverK[0]

        maxNeg = None
        maxPos = None
        if posLessK:
            maxPos = posLessK[-1]
        if negLessK:
            maxNeg = negLessK[-1]
        
        if (minNeg != None and maxPos != None) and (minPos != None and maxNeg != None):
            if maxPos / minNeg > maxNeg / minPos:
                negOverK[0] = maxPos
            else:
                posOverK[0] = maxNeg
        elif not (minNeg != None and maxPos != None) and (minPos != None and maxNeg != None):
            posOverK[0] = maxNeg
        elif (minNeg != None and maxPos != None) and not (minPos != None and maxNeg != None):
            negOverK[0] = maxPos
        elif zeroCnt:
            print(0)
            return
    
    for i in posOverK:
        ans *= i % modVal
        ans = ans % modVal
    for i in negOverK:
        ans *= i % modVal
        ans = ans % modVal
    
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

MOD = 10 ** 9 + 7

pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(a)

flag = False  # 積を正にできるか

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


if len(pos) > 0:
    flag = True
else:
    if K % 2 == 0:
        flag = True

ans = 1
if not flag:
    # 積を正にできないとき
    # 絶対値の小さい方からK個とる
    A = sorted([abs(x) for x in A])
    for a in A[:K]:
        ans *= a % MOD
    ans *= -1
else:
    if K % 2 == 0:
        # Kが偶数の時
        # pos, neg sort -> 2個ずつペア -> 降順sort -> 上から K//2 個とる
        pos.sort(reverse=True)
        neg.sort()
        newpos = []
        newneg = []
        for i in range(len(pos) // 2):
            newpos.append(pos[i] * pos[i + 1])
        for i in range(len(neg) // 2):
            newneg.append(neg[i] * neg[i + 1])
        pairs = sorted(newpos + newneg, reverse=True)
        for p in pairs[: K // 2]:
            ans *= p % MOD
    else:
        # Kが奇数の時
        # 一番大きい偶数を1つとる。pos, neg sort -> 2個ずつペア -> 降順sort -> 上から (K-1)//2 個とる
        pos.sort()
        ans *= pos.pop()
        pos.sort(reverse=True)
        neg.sort()
        newpos = []
        newneg = []
        for i in range(len(pos) // 2):
            newpos.append(pos[i] * pos[i + 1])
        for i in range(len(neg) // 2):
            newneg.append(neg[i] * neg[i + 1])
        pairs = sorted(newpos + newneg, reverse=True)
        for p in pairs[: (K - 1) // 2]:
            ans *= p % MOD

print(ans % MOD)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
na = a[:bisect_left(a, 0)]
pa = a[bisect_right(a, 0):][::-1]
mod = 10**9+7
if k==n:
    ans = 1
    for i in a:
        ans *= i
        ans %= mod
    print(ans)
    exit(0)
if k%2==1 and len(pa)==0:
    ans = 1
    for i in a[::-1][:k]:
        ans *= i
        ans %= mod
    print(ans)
    exit(0)
na += [0]*n
pa += [0]*n
nn = 0
pn = 0
ans = 1
for i in range(k//2):
    if pa[pn]*pa[pn+1]>=na[nn]*na[nn+1]:
        ans *= pa[pn]*pa[pn+1]
        pn += 2
    else:
        ans *= na[nn]*na[nn+1]
        nn += 2
    ans %= mod
if k%2==1:
    ans *= pa[pn]
print(ans%mod)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
na = a[:bisect_left(a, 0)]
pa = a[bisect_right(a, 0):][::-1]
mod = 10**9+7
if k%2==1 and len(pa)==0:
    ans = 1
    for i in a[::-1][:k]:
        ans *= i
        ans %= mod
    print(ans)
    exit(0)
if k==n:
    ans = 1
    for i in a:
        ans *= i
        ans %= mod
    print(ans)
    exit(0)
na += [0,0]
pa += [0]*n
nn = 0
pn = 0
ans = 1
for i in range(k//2):
    if pa[pn]*pa[pn+1]>=na[nn]*na[nn+1]:
        ans *= pa[pn]*pa[pn+1]
        pn += 2
    else:
        ans *= na[nn]*na[nn+1]
        nn += 2
    ans %= mod
if k%2==1:
    ans *= pa[pn]
print(ans%mod)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
na = a[:bisect_left(a, 0)]
pa = a[bisect_right(a, 0):][::-1]
mod = 10**9+7
if k%2==1 and len(pa)==0:
    ans = 1
    for i in a[::-1][:k]:
        ans *= i
        ans %= mod
    print(ans)
    exit(0)
na += [0,0]
pa += [0]*n
nn = 0
pn = 0
ans = 1
for i in range(k//2):
    if pa[pn]*pa[pn+1]>=na[nn]*na[nn+1]:
        ans *= pa[pn]*pa[pn+1]
        pn += 2
    else:
        ans *= na[nn]*na[nn+1]
        nn += 2
    ans %= mod
if k%2==1:
    ans *= pa[pn]
print(ans%mod)

Submission status: Wrong Answer

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

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])
ans, num = 1, []

if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

for _ in range(k):
    if len(mia) > 0 and len(pla) > 0:
        if abs(mia[-1]) <= pla[-1]:
            tmp = pla.pop()
        elif abs(mia[-1]) > pla[-1]:
            tmp = mia.pop()
    elif len(mia) == 0:
        tmp = pla.pop()
    elif len(pla) == 0:
        tmp = mia.pop()
    num.append(tmp)

cnt = sum(i < 0 for i in num)
for i in num:
    ans = ans * i % mod

if cnt % 2 == 1:
    p, q, r, s = 1, 0, -1, 0
    if len(mia) > 0 and cnt != k:
        for i in num[::-1]:
            if i >= 0:
                p, q = i, mia[-1]
                break
    if len(pla) > 0:
        for i in num[::-1]:
            if i < 0:
                r, s = i, pla[-1]
                break
    if len(mia) > 0 and len(pla) > 0 and cnt != k:
        if q * r >= p * s:
            ans *= q * pow(p, mod - 2, mod)
        if q * r < p * s:
            ans *= s * pow(r, mod - 2, mod)
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
na = a[:bisect_left(a, 0)]
pa = a[bisect_right(a, 0):][::-1]
mod = 10**9+7
if k%2==1 and len(pa)==0:
    ans = 1
    for i in na[::-1][:k]:
        ans *= i
    print(ans%mod)
    exit(0)
na += [0,0]
pa += [0]*n
nn = 0
pn = 0
ans = 1
for i in range(k//2):
    if pa[pn]*pa[pn+1]>=na[nn]*na[nn+1]:
        ans *= pa[pn]*pa[pn+1]
        pn += 2
    else:
        ans *= na[nn]*na[nn+1]
        nn += 2
    ans %= mod
if k%2==1:
    ans *= pa[pn]
print(ans%mod)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
na = a[:bisect_left(a, 0)]
pa = a[bisect_right(a, 0):][::-1]
mod = 10**9+7
if k%2==1 and len(pa)==0:
    print(sum(na[::-1][:k])%mod)
    exit(0)
na += [0,0]
pa += [0]*n
nn = 0
pn = 0
ans = 1
for i in range(k//2):
    if pa[pn]*pa[pn+1]>=na[nn]*na[nn+1]:
        ans *= pa[pn]*pa[pn+1]
        pn += 2
    else:
        ans *= na[nn]*na[nn+1]
        nn += 2
    ans %= mod
if k%2==1:
    ans *= pa[pn]
print(ans%mod)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

P = [a for a in A if a >= 0]
N = [a for a in A if a < 0]

def canPositive():
    for i in range(0, len(N) + 1, 2):
        p = K - i
        if p < 0:
            break
        if len(P) >= p:
            return True
    return False

if not canPositive():
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

if not P or not N or len(A) == K:
    A.sort(key=lambda a: abs(a), reverse=True)
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

P.sort(key=lambda a: abs(a))
N.sort(key=lambda a: abs(a))
P = deque(P)
N = deque(N)

ans = 1
sign = 1
while K > 0:
    ans %= MOD
    if ans == 0:
        break
    if K == 1:
        if sign < 0:
            ans *= N.pop()
        else:
            ans *= P.pop()
        break

    if len(P) >= 2 and len(N) >= 2:
        p = P[-1] * P[-2]
        n = N[-1] * N[-2]
        if p > n:
            ans *= P.pop() * P.pop()
        else:
            ans *= N.pop() * N.pop()
        K -= 2
        continue
    if len(P) <= 1 or len(N) <= 1:
        if len(N) == 0:
            ans *= P.pop()
            K -= 1
            continue

        if len(P) == 0:
            ans *= N.pop()
            K -= 1
            sign *= -1
            continue

        if len(P) == len(N) == 1:
            ans *= P.pop() * N.pop()
            K -= 2
            sign *= -1
            continue

        if len(N) == 1:
            n = N.pop()
            if sign < 0:
                ans *= n
                K -= 1
                sign *= -1
            continue

        if len(P) == 1:
            p = P.pop()
            if K % 2 == 1 and sign > 0 or K % 2 == 0 and sign < 0:
                ans *= p
                K -= 1
            continue

print(ans % MOD)