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:
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = []
c = []
d = 1
m = 10**9+7
for i in range(n):
    if a[i] < 0:
        c.append(a[i])
    else:
        b.append(a[i])
b.sort()
c.sort(reverse=True)
if len(b) == 0 and k%2 == 1:
    for i in range(k):
        d = d*a[i]%m
else:
    while k > 0:
        if len(b) > 1 and len(c) > 1:
            if b[-1]*b[-2] < c[-1]*c[-2] and k > 1:
                d = d*c.pop()%m
                d = d*c.pop()%m
                k -= 2
            else:
                d = d*b.pop()%m
                k -= 1
        elif len(b) == 1 and len(c) > 1:
            if k > 1:
                d = d*c.pop()%m
                d = d*c.pop()%m
                k -= 2
            else:
                d = d*b.pop()%m
                k -= 1
        elif len(b) >= 1 and len(c) <= 1:
            d = d*b.pop()%m
            k -= 1
        else:
            d = d*c.pop()%m
            k -= 1
print(d)

Submission status: Wrong Answer

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,k = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
plus = []
minus = []
zero= 0 
for ai in A:
  if ai <0:
    minus.append(ai)
  else:
    plus.append(ai)
pn = len(plus)
mn = len(minus)
minusdouble = []
plus0double = []
plus1double = []
for i in range(pn//2):
  plus0double.append(plus[i*2]*plus[i*2+1])
for i in range(1,(pn+1)//2):
  plus1double.append(plus[i*2-1]*plus[i*2])
for i in range(mn//2):
  minusdouble.append(minus[i*2]*minus[i*2+1])
alldouble0 = plus0double + minusdouble
alldouble1 = plus1double + minusdouble
alldouble0.sort(reverse = True)
alldouble1.sort(reverse = True)
if k == 1:
  print(max(A)%mod)
elif n-mn%2 < k:
  out = 1
  for i in range(k):
    out *= A[i]
    out%= mod
  print(out)
else:
  if pn == 0:
    ans1 = ans2 = 1
    for i in range(k):
      ans1 *= minus[i]
      ans1 %= mod
    for i in range(mn-1,mn-1-k,-1):
      ans2 *= minus[i]
      ans2 %= mod
    print(max(ans1,ans2))
  elif k % 2 == 1:
    out = 1
    out *= plus[0]
    for i in range(k//2):
      out *= alldouble1[i]
      out %= mod
    print(out)
  else:
    out = 1
    for i in range(k//2):
      out *= alldouble0[i]
      out %=mod
    print(out)

# print(alldouble0)
# print(alldouble1)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
a = LI()
a.sort(key = lambda x:abs(x), reverse = True)
ans = 1
p = 0
m = 0
plus = []
minus = []
f = 0
for i in range(n):
    if a[i] >= 0:
        p += 1
        if i < k:
            plus.append(a[i])
            ans *= a[i]
            ans %= mod
    else:
        m += 1
        if i < k:
            minus.append(a[i])
            f ^= 1
            ans *= -a[i]
            ans %= mod
if f:
    ans = -ans
if ans < 0:
    if k == n:
        print(ans % mod)
    elif p == 0:
        a.sort(key = lambda x:abs(x))
        ans = 1
        for i in range(k):
            ans *= -a[i]
            ans %= mod
        if k % 2:
            ans = -ans
        print(ans % mod)
    else:
        for i in range(k, n):
            if a[i] < 0:
                break
        else:
            ans = -ans * pow(-minus[-1], mod-2, mod)
            ans *= a[k]
            ans %= mod
            print(ans)
            quit()
        if plus:
            ans1 = ans * pow(plus[-1], mod-2, mod) * min(a[k:])
            ans2 = -ans * pow(-minus[-1], mod-2, mod) * max(a[k:])
            print(max(ans1, ans2) % mod)
        else:
            ans = -ans * pow(-minus[-1], mod-2, mod) * max(a[k:])
            print(ans % mod)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=sorted(list(map(int,input().split())),reverse=True)
MOD=10**9+7
if N==K:
    ans=1
    for i in A:
        ans=ans*i%MOD
    print(ans)
    exit()
if K==1:
    print(A[0]%MOD)
    exit()
if K%2==1 and A[0]==0:
    print(0)
    exit()
if K%2==1 and A[0]<0:
    ans=1
    for i in range(K):
        ans=ans*A[i]%MOD
    print(ans)
    exit()
if N-A.count(0) <K:
    print(0)
    exit()
if A[-1]>=0:
    ans=1
    for i in range(K):
        ans=ans*A[i]%MOD
    print(ans)
    exit()
l=0
r=N-1
t=[]
c=0
while c<K:
    if c==K-1 or A[l]*A[l+1]<=A[r]*A[r-1]:
        t.append(A[r])
        r-=1
        c+=1
    else:
        t.append(A[l])
        t.append(A[l+1])
        l+=2
        c+=2
ans=1
for i in t:
    ans=ans*i%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from math import log2
from itertools import accumulate
from decimal import Decimal, getcontext

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

getcontext().prec = 14

N, K = MAP()
A = LIST()

A1 = []
A2 = []
B1 = []
B2 = []
zero = 0
for a in A:
    if a > 0:
        A1.append(a)
        # logした値をDecimalで持つ
        B1.append(Decimal(a).log10())
    elif a < 0:
        A2.append(-a)
        B2.append(Decimal(-a).log10())
    else:
        zero += 1

A1.sort()
A2.sort()
B1.sort()
B2.sort()
acc1 = [0] + list(accumulate(B1))
accrev1 = [0] + list(accumulate(B1[::-1]))
acc2 = [0] + list(accumulate(B2))
accrev2 = [0] + list(accumulate(B2[::-1]))
mx = -INF
mn = INF
idx1 = (-1, -1)
idx2 = (-1, -1)
for i in range(K+1):
    j = K - i
    if len(B1) < i or len(B2) < j:
        continue
    if j % 2 == 0:
        sm = accrev1[i] + accrev2[j]
        if sm > mx:
            mx = sm
            idx1 = (i, j)
    else:
        sm = acc1[i] + acc2[j]
        if sm < mn:
            mn = sm
            idx2 = (i, j)

if mx != -INF:
    ans = 1
    n, m = idx1
    A1.reverse()
    A2.reverse()
    for i in range(n):
        ans *= A1[i]
        ans %= MOD
    for i in range(m):
        ans *= -A2[i]
        ans %= MOD
    print(ans)
elif zero:
    print(0)
else:
    ans = 1
    n, m = idx2
    for i in range(n):
        ans *= A1[i]
        ans %= MOD
    for i in range(m):
        ans *= -A2[i]
        ans %= MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
mod = 10**9 + 7
nums = []
p_cnt = 0
for i in list(map(int, input().split())):
    if i >= 0:
        nums.append((i, True))
        p_cnt += 1
    else:
        nums.append((-i, False))
nums.sort()
if p_cnt == 0 and K%2!=0:
    ans = 1
    for k in range(K):
        ans *= -nums[k][0]
        ans %= mod
    print(ans)
    import sys
    sys.exit()
pl = []
ml = []
for k in range(K):
    x, b = nums.pop()
    if x == 0:
        print(0)
        import sys
        sys.exit()
    if b:
        pl.append(x)
    else:
        ml.append(x)
if len(ml) % 2 != 0:
    p = float("inf")
    px = float("inf")
    m = float("inf")
    mx = float("inf")
    while nums:
        x, b = nums.pop()
        if b:
            if ml and p == float("inf"):
                p = ml[-1]
                px = x
                continue
        else:
            if pl and m == float("inf"):
                m = pl[-1]
                mx = x
                continue
        if m != float("inf") and p != float("inf"):
            if px * m > mx * p:
                ml.pop()
                pl.append(px)
            else:
                pl.pop()
                ml.append(mx)
            break
    else:
        if p != float("inf"):
            ml.pop()
            pl.append(px)
        elif m != float("inf"):
            pl.pop()
            ml.append(mx)
ans = 1
for x in pl:
    ans *= x
    ans %= mod
for x in ml:
    ans *= -x
    ans %= mod
print(ans)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
a = LI()
a.sort(key = lambda x:abs(x), reverse = True)
ans = 1
p = 0
m = 0
plus = []
minus = []
f = 0
for i in range(n):
    if a[i] >= 0:
        p += 1
        if i < k:
            plus.append(a[i])
            ans *= a[i]
            ans %= mod
    else:
        m += 1
        if i < k:
            minus.append(a[i])
            f ^= 1
            ans *= -a[i]
            ans %= mod
if f:
    ans = -ans
if ans < 0:
    if k == n:
        print(ans)
    elif p == 0:
        a.sort(key = lambda x:abs(x))
        ans = 1
        for i in range(k):
            ans *= -a[i]
            ans %= mod
        if k % 2:
            ans = -ans
        print(ans % mod)
    else:
        for i in range(k, n):
            if a[i] < 0:
                break
        else:
            ans = -ans * pow(-minus[-1], mod-2, mod)
            ans *= a[k]
            ans %= mod
            print(ans)
            quit()
        if plus:
            ans1 = ans * pow(plus[-1], mod-2, mod) * min(a[k:])
            ans2 = -ans * pow(-minus[-1], mod-2, mod) * max(a[k:])
            print(max(ans1, ans2) % mod)
        else:
            ans = -ans * pow(-minus[-1], mod-2, mod) * max(a[k:])
            print(ans % mod)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

A_p = [i for i in A if i >= 0]
A_n = [i for i in A if i < 0]
if A_p:
    A_p.sort()
    A_p.reverse()
if A_n:
    A_n.sort()
    A_n.reverse()
A_p = deque(A_p)
A_n = deque(A_n)

ans = 1
mod = 10 ** 9 + 7
if K % 2 == 0:
    while K != 0:
        if len(A_p) >= 2 and len(A_n) >= 2:
            if A_p[0] * A_p[1] > A_n[0] * A_n[1]:
                ans = ans * A_p[0] * A_p[1] % mod
                A_p.popleft()
                A_p.popleft()
            else:
                ans = ans * A_n[0] * A_n[1] % mod
                A_n.popleft()
                A_n.popleft()
        elif len(A_p) >= 2:
            ans = ans * A_p[0] * A_p[1] % mod
            A_p.popleft()
            A_p.popleft()
        elif len(A_n) >= 2:
            ans = ans * A_n[0] * A_n[1] % mod
            A_n.popleft()
            A_n.popleft()
        K -= 2
elif len(A_p) > 0:
    while K != 0:
        if K >= 2:
            if len(A_p) >= 2 and len(A_n) >= 2:
                if A_p[0] * A_p[1] > A_n[0] * A_n[1]:
                    ans = ans * A_p[0] * A_p[1] % mod
                    A_p.popleft()
                    A_p.popleft()
                else:
                    ans = ans * A_n[0] * A_n[1] % mod
                    A_n.popleft()
                    A_n.popleft()
            elif len(A_p) >= 2:
                ans = ans * A_p[0] * A_p[1] % mod
                A_p.popleft()
                A_p.popleft()
            elif len(A_n) >= 2:
                ans = ans * A_n[0] * A_n[1] % mod
                A_n.popleft()
                A_n.popleft()
            K -= 2
        elif K == 1:
            ans = ans * A_p[0] % mod
            A_p.popleft()
            K -= 1
else:
    while K != 0:
        ans = ans * A_n[0] % mod
        A_n.popleft()
        K -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
mod = 10**9 + 7
nums = []
p_cnt = 0
m_cnt = 0
for i in list(map(int, input().split())):
    if i >= 0:
        nums.append((i, True))
        p_cnt += 1
    else:
        nums.append((-i, False))
        m_cnt += 1
print(p_cnt, m_cnt)
print(p_cnt+m_cnt)
from collections import Counter
print(Counter(nums))
nums.sort()
if p_cnt == 0 and K%2!=0:
    ans = 1
    for k in range(K):
        ans *= -nums[k][0]
        ans %= mod
    print(ans)
    import sys
    sys.exit()
pl = []
ml = []
for k in range(K):
    x, b = nums.pop()
    if x == 0:
        print(0)
        import sys
        sys.exit()
    if b:
        pl.append(x)
    else:
        ml.append(x)
if len(ml) % 2 != 0:
    p = float("inf")
    px = float("inf")
    m = float("inf")
    mx = float("inf")
    while nums:
        x, b = nums.pop()
        if b:
            if ml and p == float("inf"):
                p = ml[-1]
                px = x
                continue
        else:
            if pl and m == float("inf"):
                m = pl[-1]
                mx = x
                continue
        if m != float("inf") and p != float("inf"):
            if px * m > mx * p:
                ml.pop()
                pl.append(px)
            else:
                pl.pop()
                ml.append(mx)
            break
    else:
        if p != float("inf"):
            ml.pop()
            pl.append(px)
        elif m != float("inf"):
            pl.pop()
            ml.append(mx)
ans = 1
for x in pl:
    ans *= x
    ans %= mod
for x in ml:
    ans *= -x
    ans %= mod
print(ans)

Submission status: Wrong Answer

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

p_list = []
n_list = []
z_count = 0

for A in map(int, input().split()):
	if A < 0:
		n_list.append(A)
	elif A > 0:
		p_list.append(A)
	else:
		z_count += 1

p_list.sort()
n_list.sort()

#print(p_list)
#print(n_list)

if len(p_list) + len(n_list) < K:
	print(0)
else:
	values = []
	
	if len(p_list) + len(n_list) == K:
		values = p_list + n_list
		n_count = 0
		for v in values:
			if v < 0:
				n_count += 1
		if n_count % 2 == 1 and z_count > 0:
			values = [0]
	elif len(p_list) + len(n_list) == K + 1 and len(p_list) == 0 and K % 2 == 1:
		if z_count > 0:
			values = [0]
		else:
			for i in range(min(len(n_list), K)):
				values.append(n_list.pop())
	else:
		n_list.reverse()
		values_pair = []
		values_left = None
		values_left_count = 0
		if len(p_list) >= K:
			if K % 2 == 1:
				values_left = p_list.pop()
				values_left_count = 1
				p_count = K - 1
			else:
				p_count = K
			
			while len(values_pair) * 2 + values_left_count < K:
				v1 = p_list.pop()
				v2 = p_list.pop()
				values_pair.append((v1 * v2, v1, v2))
		
		else:
			if (K - len(p_list)) % 2 == 1 and len(p_list) > 0:
				p_count = len(p_list) - 1
			else:
				p_count = len(p_list)
			
			if p_count % 2 == 1:
				values_left = p_list.pop()
				values_left_count = 1
				p_count -= 1
			
			for i in range(0, p_count - 1, 2):
				v1 = p_list.pop()
				v2 = p_list.pop()
				values_pair.append((v1 * v2, v1, v2))
			
			while len(values_pair) * 2 + values_left_count < K:
				v1 = n_list.pop()
				v2 = n_list.pop()
				values_pair.append((v1 * v2, v1, v2))
		
		values_pair.sort()
		
#		print(values_pair)
		
		i = 0
		for i in range(len(values_pair)):
			if len(n_list) < 2:
				break
			elif values_pair[i][0] < n_list[-1] * n_list[-2]:
				v1 = n_list.pop()
				v2 = n_list.pop()
				values_pair[i] = (v1 * v2, v1, v2)
			else:
				break
		if values_left != None:
			values.append(values_left)
		
		for prod, v1, v2 in values_pair:
			values.append(v1)
			values.append(v2)
	
#	print(values)
	total = 1
	for v in values:
		total = (total * v) % M
#		total = (total * v)
	print(total)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
a = LI()
a.sort(key = lambda x:abs(x), reverse = True)
ans = 1
p = 0
m = 0
plus = []
minus = []
f = 0
for i in range(n):
    if a[i] >= 0:
        p += 1
        if i < k:
            plus.append(a[i])
            ans *= a[i]
            ans %= mod
    else:
        m += 1
        if i < k:
            minus.append(a[i])
            f ^= 1
            ans *= -a[i]
            ans %= mod
if f:
    ans = -ans
if ans < 0:
    if k == n:
        print(ans)
    elif p == 0:
        a.sort(key = lambda x:abs(x))
        ans = 1
        for i in range(k):
            ans *= -a[i]
            ans %= mod
        if k % 2:
            ans = -ans
        print(ans % mod)
    else:
        for i in range(k, n):
            if a[i] < 0:
                break
        else:
            ans = ans // minus[-1]
            ans *= a[k]
            ans %= mod
            print(ans)
            quit()
        if plus:
            ans1 = ans * pow(plus[-1], mod-2, mod) * min(a[k:])
            ans2 = -ans * pow(-minus[-1], mod-2, mod) * max(a[k:])
            print(max(ans1, ans2) % mod)
        else:
            ans = -ans * pow(-minus[-1], mod-2, mod) * max(a[k:])
            print(ans % mod)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = []
c = []
d = 1
m = 10**9+7
for i in range(n):
    if a[i] < 0:
        c.append(a[i])
    else:
        b.append(a[i])
b.sort()
c.sort(reverse=True)
if len(b) == 0:
    for i in range(k):
        d = d*a[i]%m
else:
    while k > 0:
        if len(b) > 1 and len(c) > 1:
            if b[-1]*b[-2] <= c[-1]*c[-2] and k > 1:
                d = d*c.pop()%m
                d = d*c.pop()%m
                k -= 2
            else:
                d = d*b.pop()%m
                k -= 1
        elif len(b) == 1 and len(c) > 1:
            if k > 1:
                d = d*c.pop()%m
                d = d*c.pop()%m
                k -= 2
            else:
                d = d*b.pop()%m
                k -= 1
        elif len(b) >= 1 and len(c) <= 1:
            d = d*b.pop()%m
            k -= 1
        else:
            d = d*c.pop()%m
            k -= 1
print(d)

Submission status: Wrong Answer

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

p_list = []
n_list = []
z_count = 0

for A in map(int, input().split()):
	if A < 0:
		n_list.append(A)
	elif A > 0:
		p_list.append(A)
	else:
		z_count += 1

p_list.sort()
n_list.sort()

#print(p_list)
#print(n_list)

if len(p_list) + len(n_list) < K:
	print(0)
else:
	values = []
	
	if len(p_list) + len(n_list) == K:
		values = p_list + n_list
		n_count = 0
		for v in values:
			if v < 0:
				n_count += 1
		if n_count % 2 == 1 and z_count > 0:
			values = [0]
	elif len(p_list) + len(n_list) == K + 1 and len(p_list) == 0 and K % 2 == 1:
		if z_count > 0:
			values = [0]
		else:
			for i in range(min(len(n_list), K)):
				values.append(n_list.pop())
	else:
		n_list.reverse()
		values_pair = []
		values_left = None
		values_left_count = 0
		if len(p_list) >= K:
			if K % 2 == 1:
				values_left = p_list.pop()
				values_left_count = 1
				p_count = K - 1
			else:
				p_count = K
			
			while len(values_pair) * 2 + values_left_count < K:
				v1 = p_list.pop()
				v2 = p_list.pop()
				values_pair.append((v1 * v2, v1, v2))
		
		else:
			if (K - len(p_list)) % 2 == 1 and len(p_list) > 0:
				p_count = len(p_list) - 1
			else:
				p_count = len(p_list)
			
			if p_count % 2 == 1:
				values_left = p_list.pop()
				values_left_count = 1
				p_count -= 1
			
			for i in range(0, p_count - 1, 2):
				v1 = p_list.pop()
				v2 = p_list.pop()
				values_pair.append((v1 * v2, v1, v2))
			
			while len(values_pair) * 2 + values_left_count < K:
				v1 = n_list.pop()
				v2 = n_list.pop()
				values_pair.append((v1 * v2, v1, v2))
		
		values_pair.sort()
		
#		print(values_pair)
		
		i = 0
		for i in range(len(values_pair)):
			if len(n_list) < 2:
				break
			elif values_pair[i][0] < n_list[-1] * n_list[-2]:
				v1 = n_list.pop()
				v2 = n_list.pop()
				values_pair[i] = (v1 * v2, v1, v2)
			else:
				break
		if values_left != None:
			values.append(values_left)
		
		for prod, v1, v2 in values_pair:
			values.append(v1)
			values.append(v2)
	
#	print(values)
	total = 1
	for v in values:
#		total = (total * v) % M
		total = (total * v)
	print(total)

Submission status: Wrong Answer

Solution code:
MOD=10**9 + 7
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
s=0
e=n-1
ans=1
lp=[1]
ln=[1]
if a[e]<0:
    if k%2==1:
        for i in range(k):
            ans= ans * a[e-i] % MOD
    else:
        for i in range(k):
            ans = ans * a[i] % MOD
    print(ans)
    exit()
if a[s]>=0 or n==k:
    for i in range(k):
        ans = ans* a[e-i] % MOD
    print(ans)
    exit()
isneg = False
while k>0:
    if a[s]+a[e]>=0:
        lp.append(a[e])
        e-=1
        k-=1
    else:
        ln.append(a[s])
        s+=1
        isneg= ~isneg
        k-=1

if isneg:
    if a[e]<=0:
        ln.append(a[s])
        lp[len(lp)-1]=1
    elif a[s]>=0:
        ln[len(ln)-1]=0
        lp.append(a[e])
    else:
        if a[s]+a[e]>=0:
            lp.append(a[e])
            ln[len(ln)-1]=0
        else:
            lp[len(lp)-1]=1
            ln.append(a[s])
for p in lp:
    ans = ans * p %MOD
for n in ln:
    ans = ans * n %MOD

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
mod = 10**9 + 7
nums = []
p_cnt = 0
m_cnt = 0
for i in list(map(int, input().split())):
    if i >= 0:
        nums.append((i, True))
        p_cnt += 1
    else:
        nums.append((-i, False))
nums.sort()
if p_cnt == 0 and K%2!=0:
    ans = 1
    for k in range(K):
        ans *= -nums[k][0]
        ans %= mod
    print(ans)
    import sys
    sys.exit()
pl = []
ml = []
for k in range(K):
    x, b = nums.pop()
    if x == 0:
        print(0)
        import sys
        sys.exit()
    if b:
        pl.append(x)
    else:
        ml.append(x)
if len(ml) % 2 != 0:
    p = -1
    px = -1
    m = -1
    mx = -1
    while nums:
        x, b = nums.pop()
        if b:
            if ml and p == -1:
                p = x/ml[-1]
                px = x
                continue
        else:
            if pl and m == -1:
                m = x/pl[-1]
                mx = x
                continue
        if m != -1 and p != -1:
            if p > m:
                ml.pop()
                pl.append(px)
            else:
                pl.pop()
                ml.append(mx)
            break
    else:
        if p != -1:
            ml.pop()
            pl.append(px)
        elif m != -1:
            pl.pop()
            ml.append(mx)
ans = 1
for x in pl:
    ans *= x
    ans %= mod
for x in ml:
    ans *= -x
    ans %= mod
print(ans)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
a = LI()
a.sort(key = lambda x:abs(x), reverse = True)
ans = 1
p = 0
m = 0
plus = []
minus = []
f = 0
for i in range(n):
    if a[i] >= 0:
        p += 1
        if i < k:
            plus.append(a[i])
            ans *= a[i]
            ans %= mod
    else:
        m += 1
        if i < k:
            minus.append(a[i])
            f ^= 1
            ans *= -a[i]
            ans %= mod
if f:
    ans = -ans
if ans < 0:
    if k == n:
        print(ans)
    elif p == 0:
        a.sort(key = lambda x:abs(x))
        ans = 1
        for i in range(k):
            ans *= -a[i]
            ans %= mod
        if k % 2:
            ans = -ans
        print(ans % mod)
    else:
        for i in range(k, n):
            if a[i] < 0:
                break
        else:
            ans = ans // minus[-1]
            ans *= a[k]
            ans %= mod
            print(ans)
            quit()
        if plus:
            ans1 = ans // plus[-1] * min(a[k:])
            ans2 = ans // minus[-1] * max(a[k:])
            print(max(ans1, ans2) % mod)
        else:
            ans = ans // minus[-1] * max(a[k:])
            print(ans % mod)
else:
    print(ans)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
a = LI()
a.sort(key = lambda x:abs(x), reverse = True)
ans = 1
p = 0
m = 0
plus = []
minus = []
f = 0
for i in range(n):
    if a[i] >= 0:
        p += 1
        if i < k:
            plus.append(a[i])
            ans *= a[i]
            ans %= mod
    else:
        m += 1
        if i < k:
            minus.append(a[i])
            f ^= 1
            ans *= -a[i]
            ans %= mod
if f:
    ans = -ans
if ans < 0:
    if k == n:
        print(ans)
    elif p == 0:
        a.sort(key = lambda x:abs(x))
        ans = 1
        for i in range(k):
            ans *= -a[i]
            ans %= mod
        if k % 2:
            ans = -ans
        print(ans % mod)
    else:
        for i in range(k, n):
            if a[i] < 0:
                break
        else:
            ans = ans // minus[-1]
            ans *= a[k]
            ans %= mod
            print(ans)
            quit()
        if plus:
            print(1)
            ans1 = ans // plus[-1] * min(a[k:])
            ans2 = ans // minus[-1] * max(a[k:])
            print(max(ans1, ans2) % mod)
        else:
            ans = ans // minus[-1] * max(a[k:])
            print(ans % mod)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
ans = 1

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

if n == k:
    for x in a:
        ans *= x
    print(ans % MOD)
    exit()

pos = []
neg = []

for x in a:
    if x >= 0:
        pos.append(x)
    else:
        neg.append(x)

pos.sort(reverse=True)
neg.sort()

if len(pos) == 0 and k % 2:
    for i in range(1, k+1):
        ans *= neg[-i]
    print(ans % MOD)
    exit()

if k % 2:
    ans *= pos[0]
    k -= 1


l = []

for i in range(1, len(pos), 2):
    l.append(pos[i] * pos[i - 1])

for i in range(1, len(neg), 2):
    l.append(neg[i] * neg[i - 1])

l.sort(reverse=True)

for i in range(k // 2):
    ans *= l[i]

print(ans % MOD)