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:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    an = sorted([i for i in a if i < 0])
    ap = sorted([i for i in a if i > 0], reverse = True)
    a_s = list(sorted(a, key = lambda x: -abs(x)))
    num_n = 0
    num_p = 0
    zero = False
    ans = 1
    old_n = 0
    old_p = 0
    if k == 1:
        print(max(a)%mod)
        return
    if k == n:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    for ai in a_s[:k]:
        if ai < 0:
            old_n = ai
            num_n += 1
        elif ai > 0:
            old_p = ai
            num_p += 1
        else:
            zero = True
    if zero:
        print(0)
        return
    if num_n%2 == 0:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    elif len([i for i in a if i > 0]) == 0:
        a_sr = list(sorted(a, reverse=True))[:k]
        for ai in a_sr:
            ans *= ai
            ans %= mod
        print(ans)
        return
    else:
        next_n = 0
        next_p = 0
        for i in a_s[k:]:
            if i < 0:
                next_n = i
                break
        for i in a_s[k:]:
            if i > 0:
                next_p = i
                break
        if old_p*next_p > old_n*next_n or next_n == 0:
            for ai in a_s[:k]:
                if ai == old_n:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_p
            ans %= mod
            print(ans)
            return
        else:
            for ai in a_s[:k]:
                if ai == old_p:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_n
            ans %= mod
            print(ans)
            return
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=sorted(list(map(int,input().split())))
a,b,i=0,-1,0
mod=10**9+7
ans=1
while i<K-1:
  if A[a]*A[a+1]>A[-b]*A[-b-1]:
    ans*=A[a]*A[a+1]
    ans%=mod
    a+=2
    i+=2
  else:
    ans*=A[-b]
    ans%=mod
    b+=1
    i+=1
if i==K-1:
  ans*=A[-b]
  ans%=mod
if A[-1]<0 and K%2==1:
  ans=1
  for i in A[N-K:]:
    ans*=i
    ans%=mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    an = sorted([i for i in a if i < 0])
    ap = sorted([i for i in a if i > 0], reverse = True)
    a_s = list(sorted(a, key = lambda x: -abs(x)))
    num_n = 0
    num_p = 0
    zero = False
    ans = 1
    old_n = 0
    ald_p = 0
    if k == 1:
        print(max(a)%mod)
        return
    if k == n:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    for ai in a_s[:k]:
        if ai < 0:
            old_n = ai
            num_n += 1
        elif ai > 0:
            old_p = ai
            num_p += 1
        else:
            zero = True
    if zero:
        print(0)
        return
    if num_n%2 == 0:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    elif len([i for i in a if i > 0]) == 0:
        a_sr = list(sorted(a, reverse=True))[:k]
        for ai in a_sr:
            ans *= ai
            ans %= mod
        print(ans)
        return
    else:
        next_n = 0
        next_p = 0
        for i in a_s[k:]:
            if i < 0:
                next_n = i
                break
        for i in a_s[k:]:
            if i > 0:
                next_p = i
                break
        print(-1)
        return
        if old_p*next_p > old_n*next_n or next_n == 0:
            for ai in a_s[:k]:
                if ai == old_n:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_p
            ans %= mod
            print(ans)
            return
        else:
            for ai in a_s[:k]:
                if ai == old_p:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_n
            ans %= mod
            print(ans)
            return
        

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
    an = sorted([i for i in a if i < 0])
    ap = sorted([i for i in a if i > 0], reverse = True)
    a_s = list(sorted(a, key = lambda x: -abs(x)))
    num_n = 0
    num_p = 0
    zero = False
    ans = 1
    old_n = 0
    ald_p = 0
    if k == 1:
        print(max(a)%mod)
        return
    if k == n:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    for ai in a_s[:k]:
        if ai < 0:
            old_n = ai
            num_n += 1
        elif ai > 0:
            old_p = ai
            num_p += 1
        else:
            zero = True
    if zero:
        print(0)
        return
    if num_n%2 == 0:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    elif len([i for i in a if i > 0]) == 0:
        a_sr = list(sorted(a, reverse=True))[:k]
        for ai in a_sr:
            ans *= ai
            ans %= mod
        print(ans)
        return
    else:
        print(-1)
        return
        next_n = 0
        next_p = 0
        for i in a_s[k:]:
            if i < 0:
                next_n = i
                break
        for i in a_s[k:]:
            if i > 0:
                next_p = i
                break
        if old_p*next_p > old_n*next_n or next_n == 0:
            for ai in a_s[:k]:
                if ai == old_n:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_p
            ans %= mod
            print(ans)
            return
        else:
            for ai in a_s[:k]:
                if ai == old_p:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_n
            ans %= mod
            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()))
A.sort()
a,b,i=0,-1,0
mod=10**9+7
ans=1
while i<K-1:
  if A[a]*A[a+1]>A[-b]*A[-b-1]:
    ans*=A[a]*A[a+1]
    ans%=mod
    a+=2
    i+=2
  else:
    ans*=A[-b]
    ans%=mod
    b+=1
    i+=1
if i==K-1:
  ans*=A[-b]
  ans%=mod
if A[-1]<0 and K%2==1:
  ans=1
  for i in A[N-K:]:
    ans*=i
    ans%=mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
a,b,i=0,-1,0
mod=10**9+7
ans=1
while i<K-1:
  if A[a]*A[a+1]>A[-b]*A[-b-1]:
    ans*=A[a]*A[a+1]
    ans%=mod
    a+=2
    i+=2
  else:
    ans*=A[-b]
    ans%=mod
    b+=1
    i+=1
if i==K-1:
  ans*=A[-b]
  ans%=mod
if A[-1]<0 and  K%2==1:
  ans=1
  for i in range(K):
    ans*=A[N-i-1]
    ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
a,b,i=0,0,0
mod=10**9+7
ans=1
while i<K-1:
  if A[a]*A[a+1]>A[-b]*A[-b-1]:
    ans*=A[a]*A[a+1]
    ans%=mod
    a+=2
    i+=2
  else:
    ans*=A[-b]
    ans%=mod
    b+=1
    i+=1
if i==K-1:
  ans*=A[-b]
  ans%=mod
if A[-1]<0 and  K%2==1:
  ans=1
  for i in range(K):
    ans*=A[N-i-1]
    ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import exit
# import copy
# import numpy as np
# from collections import deque

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


A = sorted(A, key=abs)

A.extend([float("inf"), 0])

ans = 1
if N == K:
    for n in A[:-2]:
        ans *= n
        if abs(ans) >= 1e9+7:
            ans %= 1e9+7
    ans %= 1e9+7
    print(int(ans))
    exit()
elif K % 2 == 1 and max(A[:-2]) < 0:
    for i in range(K):
        ans *= A[i]
        if abs(ans) >= 1e9+7:
            ans %= 1e9+7
    ans %= 1e9+7
    print(int(ans))
    exit()
else:
    min_minu = -2
    min_plus = -2
    for i in range(N-K, N):
        ans *= A[i]
        if abs(ans) >= 1e9+7:
            ans %= 1e9+7
        if min_minu == -2 and A[i] < 0:
            min_minu = i
        if min_plus == -2 and A[i] > 0:
            min_plus = i

    if ans >= 0:
        print(int(ans))
        exit()
    else:
        max_minu = -1
        max_plus = -1
        for i in range(N-K-1, -1, -1):
            if max_minu == -1 and A[i] < 0:
                max_minu = i
            if max_plus == -1 and A[i] > 0:
                max_plus = i
            if max_minu != -1 and max_plus != -1:
                break

        if abs(A[max_minu] / A[min_plus]) >= abs(A[max_plus] / A[min_minu]):
            ans = 1
            A[min_plus] = A[max_minu]
            for i in range(N-K, N):
                ans *= A[i]
                if abs(ans) >= 1e9+7:
                    ans %= 1e9+7
            ans %= 1e9+7
            print(int(ans))
            exit()
        else:
            ans = 1
            A[min_minu] = A[max_plus]
            for i in range(N-K, N):
                ans *= A[i]
                if abs(ans) >= 1e9+7:
                    ans %= 1e9+7
            ans %= 1e9+7
            print(int(ans))
            exit()

Submission status: Wrong Answer

Solution code:
from sys import exit
# import copy
# import numpy as np
# from collections import deque

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


A = sorted(A, key=abs)

A.extend([float("inf"), 0])

ans = 1
if N == K:
    for n in A[:-2]:
        ans *= n
        if abs(ans) >= 1e9+7:
            ans %= 1e9+7
    ans %= 1e9+7
    print(int(ans))
    exit()
elif K % 2 == 1 and max(A[:-2]) < 0:
    for i in range(K):
        ans *= A[i]
        if abs(ans) >= 1e9+7:
            ans %= 1e9+7
    ans %= 1e9+7
    print(int(ans))
    exit()
else:
    # que = []
    min_minu = -2
    min_plus = -2
    for i in range(N-K, N):
        # que.append(A[i])
        ans *= A[i]
        if abs(ans) >= 1e9+7:
            ans %= 1e9+7
        if min_minu == -2 and A[i] < 0:
            min_minu = i
        if min_plus == -2 and A[i] > 0:
            min_plus = i

    if ans >= 0:
        print(int(ans))
        exit()
    else:
        max_minu = -1
        max_plus = -1
        for i in range(N-K-1, -1, -1):
            if max_minu == -1 and A[i] < 0:
                max_minu = i
            if max_plus == -1 and A[i] > 0:
                max_plus = i
            if max_minu != -1 and max_plus != -1:
                break

        if abs(A[max_minu] / A[min_plus]) >= abs(A[max_plus] / A[min_minu]):
            # que.remove(min_plus)
            # que.append(max_minu)
            ans = 1
            A[min_plus] = A[max_minu]
            for i in range(N-K, N):
                ans *= A[i]
                if abs(ans) >= 1e9+7:
                    ans %= 1e9+7
            ans %= 1e9+7
            print(int(ans))
            exit()
        else:
            # que.remove(min_minu)
            # que.append(max_plus)
            ans = 1
            A[min_minu] = A[max_plus]
            for i in range(N-K, N):
                ans *= A[i]
                if abs(ans) >= 1e9+7:
                    ans %= 1e9+7
            ans %= 1e9+7
            print(int(ans))
            exit()

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 = []
use = []
f = 0
for i in range(n):
    if a[i] >= 0:
        p += 1
        if i < k:
            plus.append(a[i])
            use.append(a[i])
            ans *= a[i]
            ans %= mod
    else:
        m += 1
        if i < k:
            minus.append(a[i])
            f ^= 1
            use.append(a[i])
            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 = 1
            fl = 1
            f = 0
            for i in use[::-1]:
                if fl and i < 0:
                    fl = 0
                else:
                    ans *= abs(i)
                    ans %= mod
            ans *= max(a[k:])
            print(ans % mod)
            quit()
        if plus:
            ans1 = 1
            f1 = 1
            for i in use[::-1]:
                if f1 and i >= 0:
                    f1 = 0
                else:
                    ans1 *= abs(i)
                    ans1 %= mod
            ans1 *= -min(a[k:])
            ans2 = 1
            f2 = 1
            for i in use[::-1]:
                if f2 and i < 0:
                    f2 = 0
                else:
                    ans2 *= abs(i)
                    ans2 %= mod
            ans2 *= max(a[k:])
            print(max(ans1 % mod, ans2 % mod))
        else:
            ans = 1
            fl = 1
            for i in use[::-1]:
                if fl and i < 0:
                    fl = 0
                else:
                    ans *= abs(i)
                    ans %= mod 
            ans *= 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 = []
use = []
f = 0
for i in range(n):
    if a[i] >= 0:
        p += 1
        if i < k:
            plus.append(a[i])
            use.append(a[i])
            ans *= a[i]
            ans %= mod
    else:
        m += 1
        if i < k:
            minus.append(a[i])
            f ^= 1
            use.append(a[i])
            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 = 1
            fl = 1
            f = 0
            for i in use[::-1]:
                if fl and i < 0:
                    fl = 0
                else:
                    ans *= abs(i)
                    ans %= mod
            ans *= max(a[k:])
            print(ans % mod)
            quit()
        if plus:
            ans1 = 1
            f1 = 1
            for i in use[::-1]:
                if f1 and i >= 0:
                    f1 = 0
                else:
                    ans1 *= abs(i)
                    ans1 %= mod
            ans1 *= -min(a[k:])
            ans2 = 1
            f2 = 1
            for i in use[::-1]:
                if f2 and i < 0:
                    f2 = 0
                else:
                    ans2 *= abs(i)
                    ans2 %= mod
            ans2 *= max(a[k:])
            print(max(ans1, ans2) % mod)
        else:
            ans = 1
            fl = 1
            for i in use[::-1]:
                if fl and i < 0:
                    fl = 0
                else:
                    ans *= abs(i)
                    ans %= mod 
            ans *= max(a[k:])
            print(ans % mod)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from sys import exit
# import copy
# import numpy as np
# from collections import deque

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


A = sorted(A, key=abs)

A.extend([float("inf"), 0])

ans = 1
if N == K:
    for n in A[:-2]:
        ans *= n
        if abs(ans) >= 1e9+7:
            ans %= 1e9+7
    ans %= 1e9+7
    print(int(ans))
    exit()
elif K % 2 == 1 and max(A[:-2]) < 0:
    for i in range(K):
        ans *= A[i]
        if abs(ans) >= 1e9+7:
            ans %= 1e9+7
    ans %= 1e9+7
    print(int(ans))
    exit()
else:
    # que = []
    min_minu = -2
    min_plus = -2
    for i in range(N-K, N):
        # que.append(A[i])
        ans *= A[i]
        if abs(ans) >= 1e9+7:
            ans %= 1e9+7
        if A[min_minu] == float("inf") and A[i] < 0:
            min_minu = i
        if A[min_plus] == float("inf") and A[i] > 0:
            min_plus = i

    if ans >= 0:
        print(int(ans))
        exit()
    else:
        max_minu = -1
        max_plus = -1
        for i in range(N-K-1, -1, -1):
            if A[max_minu] == 0 and A[i] < 0:
                max_minu = i
            if A[max_plus] == 0 and A[i] > 0:
                max_plus = i
            if max_minu != 0 and max_plus != 0:
                break

        if abs(A[max_minu] / A[min_plus]) >= abs(A[max_plus] / A[min_minu]):
            # que.remove(min_plus)
            # que.append(max_minu)
            ans = 1
            A[min_plus] = A[max_minu]
            for i in range(N-K, N):
                ans *= A[i]
                if abs(ans) >= 1e9+7:
                    ans %= 1e9+7
            ans %= 1e9+7
            print(int(ans))
            exit()
        else:
            # que.remove(min_minu)
            # que.append(max_plus)
            ans = 1
            A[min_minu] = A[max_plus]
            for i in range(N-K, N):
                ans *= A[i]
                if abs(ans) >= 1e9+7:
                    ans %= 1e9+7
            ans %= 1e9+7
            print(int(ans))
            exit()

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))
a=[]
b=[]
mod=10**9+7
ans=1
for i in range(N):
  if A[i]<0:
    b.append(A[i])
  else:
    a.append(A[i])
flag=False
if 0<len(a):
  if N==K:
    flag=(len(b)%2==0)
  else:
    flag=True
else:
  flag=(K%2==0)
if not flag:
  for i in range(N):
    ans*=A[i]
    ans%=mod
else:
  b=b[::-1]
  if K%2==1:
    ans*=a.pop()
  p=[]
  while len(a)>=2:
    p.append(a.pop()*a.pop())
  while len(b)>=2:
    p.append(b.pop()*b.pop())
  p.sort(reverse=True)
  for i in range(K//2):
    ans*=p[i]
    ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
import bisect
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,K = LI()
AS=LI()
AS.sort(reverse=True)
res = 1
if AS[0] >= 0 and AS[N-1] >= 0:
    for i in range(K):
        res *= AS[i]
        res %= DVSR
elif AS[0] > 0:
    if N != K:
        PS = []
        NS = []
        for i in AS:
            if i >= 0:
                PS.append(i)
            else:
                NS.append(-i)
        PS.sort(reverse=True)
        NS.sort(reverse=True)
        i = 0
        j = 0

        for k in range(K):
            if i < len(PS) and j < len(NS):
                if PS[i] > NS[j]:
                    res *= PS[i]
                    i += 1
                else:
                    res *= NS[j]
                    j += 1
            else:
                if i < len(PS):
                    res *= PS[i]
                    i += 1
                else:
                    res *= NS[j]
                    j += 1
            res %= DVSR
            # print(res)
        # print("i:{} j:{}".format(i, j))
        if j % 2:
            if j < len(NS) and i < len(PS) and i > 0 and j > 0:
                if NS[j]*NS[j-1] > PS[i-1]*PS[i]:
                    res *= INV(PS[i-1])
                    res %= DVSR
                    res *= NS[j]
                    j += 1
                else:
                    res *= INV(NS[j-1])
                    res %= DVSR
                    res *= PS[i]
                    i += 1
            else:
                if j < len(NS) and i > 0:
                    res *= INV(PS[i-1])
                    res %= DVSR
                    res *= NS[j]
                    j += 1
                else:
                    res *= INV(NS[j-1])
                    res %= DVSR
                    res *= PS[i]
                    i += 1
            res %= DVSR
            print(res)
    else:
        for i in range(N):
            res *= AS[i]
            res %= DVSR
else: # AS[0] <= 0
    if K % 2:
        v1 = 1
        v2 = 1
        for i in range(K):
            v1 *= AS[i]
            v1 %= DVSR
        res = v1
    else:
        res = 1
        for i in range(N-K, N):
            res *= AS[i]
            res %= DVSR

print(res%DVSR)

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

n_minus = 0
for a in A:
    if a < 0:
        n_minus += 1

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

elif n_minus == N and K % 2 == 1:
    A = sorted(A, key=lambda x: 10 ** 9 if x == 0 else abs(x))

    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD

    print(ans)

else:
    A = sorted(A, key=lambda x: abs(x), reverse=True)
    plus = deque()
    minus = deque()
    buf_m = deque()

    for a in A:
        if a >= 0:
            plus.append(a)
        else:
            buf_m.append(a)

            if len(buf_m) == 2:
                minus.append(buf_m.popleft() * buf_m.popleft())

    ans = 1
    rest = K
    while rest > 0:
        if (len(minus) == 0) or (rest < 2) or (len(plus) > 0 and plus[0] >= minus[0]):
            ans *= plus.popleft()
            ans %= MOD
            rest -= 1
        else:
            ans *= minus.popleft()
            ans %= MOD
            rest -= 2

    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 % 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) * max(a[k:])
            print(ans % mod)
            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%mod, 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:
import sys
import math
import heapq
import bisect
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,K = LI()
AS=LI()
AS.sort(reverse=True)
res = 1
if AS[0] >= 0 and AS[N-1] >= 0:
    for i in range(K):
        res *= AS[i]
        res %= DVSR
elif AS[0] > 0:
    if N != K:
        PS = []
        NS = []
        for i in AS:
            if i >= 0:
                PS.append(i)
            else:
                NS.append(-i)
        PS.sort(reverse=True)
        NS.sort(reverse=True)
        i = 0
        j = 0

        for k in range(K):
            if i < len(PS) and j < len(NS):
                if PS[i] > NS[j]:
                    res *= PS[i]
                    i += 1
                else:
                    res *= NS[j]
                    j += 1
            else:
                if i < len(PS):
                    res *= PS[i]
                    i += 1
                else:
                    res *= NS[j]
                    j += 1
            res %= DVSR
            # print(res)
        if j % 2:
            if j < len(NS) and i < len(PS):
                if NS[j]*NS[j-1] > PS[i-1]*PS[i]:
                    res *= INV(PS[i-1])
                    res %= DVSR
                    res *= NS[j]
                    j += 1
                else:
                    res *= INV(NS[j-1])
                    res %= DVSR
                    res *= PS[i]
                    i += 1
            else:
                if j < len(NS):
                    res *= INV(PS[i-1])
                    res %= DVSR
                    res *= NS[j]
                    j += 1
                else:
                    res *= INV(NS[j-1])
                    res %= DVSR
                    res *= PS[i]
                    i += 1
            res %= DVSR
            # print(res)
    else:
        for i in range(N):
            res *= AS[i]
            res %= DVSR
else: # AS[0] <= 0
    if K % 2:
        v1 = 1
        v2 = 1
        for i in range(K):
            v1 *= AS[i]
            v1 %= DVSR
        res = v1
    else:
        res = 1
        for i in range(N-K, N):
            res *= AS[i]
            res %= DVSR

print(res%DVSR)

Submission status: Wrong Answer

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

ans=1
mod=10**9+7

a.sort()
if a[0]>=0:
    for i in range(n-1,n-k,-1):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()
if a[-1]<=0:
    if k%2:
        for i in range(n-1,n-k-1,-1):
            ans*=a[i]
            ans%=mod
    else:
        for i in range(k):
            ans*=a[i]
            ans%=mod
    print(ans)
    exit()
l=0;r=n-1
while k:
    if k>=2:
        if a[l]*a[l+1]>a[r]*a[r-1]:
            ans*=a[l]*a[l+1]
            l+=2
        else:
            ans*=a[r]*a[r-1]
            r-=2
        k-=2
        ans%=mod
    else:
        if a[l]>a[r]:
            ans*=a[l]
        else:
            ans*=a[r]
        k-=1
print(ans)

Submission status: Wrong Answer

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

ans=1
mod=10**9+7

a.sort()
if a[0]>=0 or a[-1]<=0:
    for i in range(n-1,n-k,-1):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()

l=0;r=n-1
while k:
    if k>=2:
        if a[l]*a[l+1]<=a[r]*a[r-1]:
            ans*=a[l]*a[l+1]
            l+=2
        else:
            ans*=a[r]*a[r-1]
            r-=2
        k-=2
        ans%=mod
    else:
        if a[l]>a[r]:
            ans*=a[l]
        else:
            ans*=a[r]
        k-=1
print(ans)

Submission status: Wrong Answer

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

ans=1
mod=10**9+7

a.sort()
if a[0]>=0:
    for i in range(n-1,n-k,-1):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()
if a[-1]<0:
    for i in range(n-1,n-k-1,-1):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()
l=0;r=n-1
while k:
    if k>=2:
        if a[l]*a[l+1]>a[r]*a[r-1]:
            ans*=a[l]*a[l+1]
            l+=2
        else:
            ans*=a[r]*a[r-1]
            r-=2
        k-=2
        ans%=mod
    else:
        if a[l]>a[r]:
            ans*=a[l]
        else:
            ans*=a[r]
        k-=1
print(ans)