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:
# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# ------------------- fast io --------------------
from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y


for _ in range(int(input()) if not True else 1):
    n, k = map(int, input().split())
    #a, b = map(int, input().split())
    #c, d = map(int, input().split())
    a = list(map(int, input().split()))
    di = {}
    x = []
    for i in a:
        ab = abs(i)
        x += [ab]
        if ab not in di:
            di[ab] = []
        di[ab] += [1 if i>=0 else -1]

    x = sorted(x, reverse=True)
    signs = []
    for each in x:
        signs += [di[each].pop()]

    cursign = 1
    ans = 1
    firstpos = -1
    firstneg = 0
    nextpos = None
    nextneg = None
    for i in range(k):
        ans = (ans * x[i]) % (10**9+7)
        cursign *= signs[i]
        if signs[i] == 1:
            firstpos = i
        if signs[i] == -1:
            firstneg = i

    if cursign == 1:
        print(ans)
        quit()

    for i in range(k, len(x)):
        if signs[i] == 1 and nextpos is None:
            nextpos = i
        if signs[i] == -1 and nextneg is None:
            nextneg = i
    ansdex = [i for i in range(k)]
    from math import inf
    ans = ans*-1
    #print(ans)
    #print(nextpos)
    ans1, ans2 = -10**18, -10**18
    if nextpos is not None:
        ansd = [i for i in range(k)]
        ans22 = 1
        ansd[firstneg] = nextpos
        for each in ansd:
            ans22 = (ans22 * x[each]) % (10**9+7)
        ans2 = ans22

    if nextneg is not None and firstpos != -1:
        ansd = [i for i in range(k)]
        ans22 = 1
        ansd[firstpos] = nextneg
        for each in ansd:
            ans22 = (ans22 * x[each]) % (10 ** 9 + 7)
        ans1 = ans22
    if ans1 != -10**18 or ans2 != -10**18:
        print(max(ans1, ans2))
        quit()

    a = sorted(a, reverse=True)
    ans=1
    for i in range(k):ans=(ans*(a[i])) % (10**9+7)
    print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=sorted(list(map(int,input().split())) , key=abs , reverse=1)
# print(A)
# import numpy as np
# G=np.prod(A[:k])
def seki(A,mod=10**9+7):
    now=1
    for i in A:
        now*=i %mod
        now%=mod
    return now


G=seki(A[:k])

mod=10**9+7
if G==0 or sum([i<0 for i in A[:k]])%2==0 : print(G%mod) ; exit()
if sum([A[i]>0 for i in range(n)])==0 and k%2==1:
  print(seki(A[n-k:])) ; exit()
  
  
  
done=0 ; done2=0
ch=-73267983297 ; ch2=-9263498381621

for i in range(k-1,-1,-1):
    if A[i]<0 and done==0:
        for j in range(i+1,n):
            if A[j]>=0: 
                ch=G*A[j]//A[i]
                done=1
                break
    if A[i]>0 and done2==0:
        for j in range(i+1,n):
            if A[j]>=0: 
                ch2=G*A[j]//A[i]
                done2=1
                break
    if done==1 and done2==1 : break

print(max(ch,ch2))

Submission status: Wrong Answer

Solution code:
def solve():
  N, K = map(int, input().split())
  A = list(map(int, input().split()))
  mod = 10**9+7
  ans = 1
  if K==N:
    for i in range(N):
      ans *= A[i]
      ans %= mod
    return ans
  minus = len([a for a in A if a<0])
  if minus==N:
    if K%2==0:
      A.sort(reverse=True)
    else:
      A.sort(reverse=True)
    for i in range(K):
      ans *= A[i]
      ans %= mod
    return ans
  if K==1:
    return max(A)
  A.sort(key=lambda x:-abs(x))
  for i in range(K-2):
    ans *= A[i]
    ans %= mod
  minus = len([a for a in A[:K] if a<0])
  if minus%2==1:
    for i in range(K,N):
      if A[K-1]*A[i]<=0:
        ans *= max(A[K-2]*A[i],A[K-1]*A[K])
        break
    else:
      ans *= A[K-1]*A[K]
  else:
    ans *= A[K-2]*A[K-1]
  ans %= mod
  return ans
print(solve())

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=sorted(list(map(int,input().split())) , key=abs , reverse=1)
# print(A)
# import numpy as np
# G=np.prod(A[:k])
def seki(A,mod=10**9+7):
    now=1
    for i in A:
        now*=i %mod
        now%=mod
    return now


G=seki(A[:k])

mod=10**9+7
if G>=0 : print(G%mod) ; exit()
if sum([A[i]>0 for i in range(n)])==0 and k%2==1:
  print(np.prod(A[n-k:])%mod) ; exit()
  
  
  
done=0 ; done2=0
ch=-73267983297 ; ch2=-9263498381621

for i in range(k-1,-1,-1):
    if A[i]<0 and done==0:
        for j in range(i+1,n):
            if A[j]>=0: 
                ch=G*A[j]//A[i]
                done=1
                break
    if A[i]>0 and done2==0:
        for j in range(i+1,n):
            if A[j]>=0: 
                ch2=G*A[j]//A[i]
                done2=1
                break
    if done==1 and done2==1 : break

print(max(ch,ch2))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=sorted(list(map(int,input().split())) , key=abs , reverse=1)
# print(A)
import numpy as np
G=np.prod(A[:k])

mod=10**9+7
if G>=0 : print(G%mod) ; exit()
if sum([A[i]>0 for i in range(n)])==0 and k%2==1:
  print(np.prod(A[n-k:])%mod) ; exit()
  
  
  
done=0 ; done2=0
ch=-73267983297 ; ch2=-9263498381621

for i in range(k-1,-1,-1):
    if A[i]<0 and done==0:
        for j in range(i+1,n):
            if A[j]>=0: 
                ch=G*A[j]//A[i]
                done=1
                break
    if A[i]>0 and done2==0:
        for j in range(i+1,n):
            if A[j]>=0: 
                ch2=G*A[j]//A[i]
                done2=1
                break
    if done==1 and done2==1 : break

print(max(ch,ch2))

Submission status: Wrong Answer

Solution code:
def solve():
  N, K = map(int, input().split())
  A = list(map(int, input().split()))
  mod = 10**9+7
  ans = 1
  if K==N:
    for i in range(N):
      ans *= A[i]
      ans %= mod
    return ans
  minus = len([a for a in A if a<0])
  if minus==N:
    if K%2==0:
      A.sort()
    else:
      A.sort(reverse=True)
    for i in range(K):
      ans *= A[i]
      ans %= mod
    return ans
  A.sort(key=lambda x:-abs(x))
  for i in range(K-1):
    ans *= A[i]
    ans %= mod
  minus = len([a for a in A[:K] if a<0])
  if minus%2==1:
    for i in range(K,N):
      if A[K-1]*A[i]<=0:
        ans *= A[i]
        break
  else:
    ans *= A[K-1]
  ans %= mod
  return ans
print(solve())

Submission status: Wrong Answer

Solution code:
def solve():
  N, K = map(int, input().split())
  A = list(map(int, input().split()))
  mod = 10**9+7
  ans = 1
  if K==N:
    for i in range(N):
      ans *= A[i]
      ans %= mod
    return ans
  minus = len([a for a in A if a<0])
  if minus==N:
    A.sort(reverse=True)
    for i in range(K):
      ans *= A[i]
      ans %= mod
    return ans
  A.sort(key=lambda x:-abs(x))
  for i in range(K-1):
    ans *= A[i]
    ans %= mod
  minus = len([a for a in A[:K] if a<0])
  if minus%2==1:
    for i in range(K,N):
      if A[K-1]*A[i]<=0:
        ans *= A[i]
        break
  else:
    ans *= A[K-1]
  ans %= mod
  return ans
print(solve())

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = pow(10, 9) + 7
neg = 0
zero = 0
for i in range(n):
    if a[i] >= 0:
        if a[i] == 0:
            zero += 1
        a[i] = [a[i], 1]
    else:
        a[i] = [-a[i], 0]
        neg += 1
a.sort(reverse = True)
ans = 1
if k % 2 == 1 and (neg == n or neg + zero == n):
    for i in range(1, k + 1):
        ans *= -a[-i][0]
        ans %= mod
else:
    pos, neg = 0, 0
    lastpos, lastneg = mod, mod
    for i in range(k):
        ans *= a[i][0]
        ans %= mod
        if a[i][1]:
            pos += 1
            lastpos = a[i][0]
        else:
            neg += 1
            lastneg = a[i][0]
    if neg % 2 == 1:
        firstpos, firstneg = mod, mod
        for i in range(k, n):
            if not firstpos == mod and not firstneg == mod:
                break
            if firstpos == mod and a[i][1]:
                firstpos = a[i][0]
            elif firstneg == mod and not a[i][1]:
                firstneg = a[i][0]
        if not mod in [lastpos, lastneg, firstpos, firstneg]:
            if firstpos / lastneg >= firstneg / lastpos:
                ans = ans * pow(lastneg, mod - 2, mod) * firstpos % mod
            else:
                ans = ans * pow(lastpos, mod - 2, mod) * firstneg % mod
        elif not mod in [lastpos, firstneg]:
            ans = ans * pow(lastpos, mod - 2, mod) * firstneg % mod
        elif not mod in [lastneg, firstpos]:
            ans = ans * pow(lastneg, mod - 2, mod) * firstpos % mod
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = pow(10, 9) + 7
neg = 0
zero = 0
for i in range(n):
    if a[i] >= 0:
        if a[i] == 0:
            zero += 1
        a[i] = [a[i], 1]
    else:
        a[i] = [-a[i], 0]
        neg += 1
a.sort(reverse = True)
ans = 1
if k % 2 == 1 and (neg == n or neg + zero == n):
    for i in range(1, k + 1):
        ans *= -a[-i][0]
        ans %= mod
else:
    pos, neg = 0, 0
    lastpos, lastneg = mod, mod
    for i in range(k):
        ans *= a[i][0]
        ans %= mod
        if a[i][1]:
            pos += 1
            lastpos = a[i][0]
        else:
            neg += 1
            lastneg = a[i][0]
    if neg % 2 == 1:
        firstpos, firstneg = mod, mod
        for i in range(k, n):
            if not (firstpos == mod and firstneg == mod):
                break
            if firstpos == mod and a[i][1]:
                firstpos = a[i][0]
            elif firstneg == mod and not a[i][1]:
                firstneg = a[i][0]
        if not mod in [lastpos, lastneg, firstpos, firstneg]:
            if firstpos / lastneg >= firstneg / lastpos:
                ans = ans * pow(lastneg, mod - 2, mod) * firstpos % mod
            else:
                ans = ans * pow(lastpos, mod - 2, mod) * firstneg % mod
        elif not mod in [lastpos, firstneg]:
            ans = ans * pow(lastpos, mod - 2, mod) * firstneg % mod
        elif not mod in [lastneg, firstpos]:
            ans = ans * pow(lastneg, mod - 2, mod) * firstpos % mod
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = pow(10, 9) + 7
neg = 0
for i in range(n):
    if a[i] >= 0:
        a[i] = [a[i], 1]
    else:
        a[i] = [-a[i], 0]
        neg += 1
a.sort(reverse = True)
ans = 1
if k % 2 == 1 and neg == n:
    for i in range(1, k + 1):
        ans *= -a[-i][0]
        ans %= mod
else:
    pos, neg = 0, 0
    lastpos, lastneg = mod, mod
    for i in range(k):
        ans *= a[i][0]
        ans %= mod
        if a[i][1]:
            pos += 1
            lastpos = a[i][0]
        else:
            neg += 1
            lastneg = a[i][0]
    if neg % 2 == 1:
        firstpos, firstneg = mod, mod
        for i in range(k, n):
            if not (firstpos == mod and firstneg == mod):
                break
            if firstpos == mod and a[i][1]:
                firstpos = a[i][0]
            elif firstneg == mod and not a[i][1]:
                firstneg = a[i][0]
        if not mod in [lastpos, lastneg, firstpos, firstneg]:
            if firstpos / lastneg >= firstneg / lastpos:
                ans = ans * pow(lastneg, mod - 2, mod) * firstpos % mod
            else:
                ans = ans * pow(lastpos, mod - 2, mod) * firstneg % mod
        elif not mod in [lastpos, firstneg]:
            ans = ans * pow(lastpos, mod - 2, mod) * firstneg % mod
        elif not mod in [lastneg, firstpos]:
            ans = ans * pow(lastneg, mod - 2, mod) * firstpos % mod
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = pow(10, 9) + 7
neg = 0
for i in range(n):
    if a[i] >= 0:
        a[i] = [a[i], 1]
    else:
        a[i] = [-a[i], 0]
        neg += 1
a.sort(reverse = True)
ans = 1
if k % 2 == 1 and neg == n:
    for i in range(1, k + 1):
        ans *= -a[-i][0]
        ans %= mod
else:
    pos, neg = 0, 0
    lastpos, lastneg = mod, mod
    for i in range(k):
        ans *= a[i][0]
        ans %= mod
        if a[i][1]:
            pos += 1
            lastpos = a[i][0]
        else:
            neg += 1
            lastneg = a[i][0]
    if neg % 2 == 1:
        firstpos, firstneg = mod, mod
        for i in range(k, n):
            if not (firstpos == mod and firstneg == mod):
                break
            if firstpos == mod and a[i][1]:
                firstpos = a[i][0]
            elif firstneg == mod and not a[i][1]:
                firstneg = a[i][1]
        if not mod in [lastpos, lastneg, firstpos, firstneg]:
            if firstpos / lastneg >= firstneg / lastpos:
                ans = ans * pow(lastneg, mod - 2, mod) * firstpos % mod
            else:
                ans = ans * pow(lastpos, mod - 2, mod) * firstneg % mod
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
M = 10**9 + 7
A_minus = [i for i in A if i < 0]
A_plus = [i for i in A if i >= 0]
is_minus = False
if len(A_plus) == 0:
    if K % 2 == 1:
        is_minus = True
elif K == N and len(A_minus) % 2 == 1:
    is_minus = True
if is_minus:
    A.sort(key=abs)
    result = 1
    for i in range(K):
        result =  result * A[i] % M
    print(result)
else:
    result = 1
    if K % 2 == 1:
        result = A_plus.pop(-1)
        K -= 1
    array = []
    A_minus.sort()
    i = 0
    while 2 * i + 1 <len(A_minus):
        array.append(A_minus[2 * i] * A_minus[2 * i + 1])
        i += 1
    A_plus.sort(reverse=1)
    i = 0
    while 2 * i + 1 <len(A_plus):
        array.append(A_plus[2 * i] * A_plus[2 * i + 1])
        i += 1
    array.sort(reverse = 1)
    i = 0
    while 2 * i != K:
        result = result * array.pop(0) % M
        i += 1
    print(result)

Submission status: Wrong Answer

Solution code:
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
M = 10**9 + 7
if N == K:
    result = 1
    for i in range(K):
        result = result * A[i] % M
    print(result)
    exit()
minus = [i for i in A if i <= 0]
l_minus = len(minus)
plus = [i for i in A if i > 0]
l_plus = len(plus)
plus.sort(reverse=1)
minus.sort()
if len(plus) == 0 and K % 2 == 1:
    result = 1
    for i in range(K):
        result = result * minus[-i-1] % M
    print(result)
    exit()

m_x = 0
p_x = 0
max_mm = -1
if (m_x+1) * 2 <= l_minus:
    max_mm = minus[m_x * 2] * minus[m_x * 2 + 1]
max_pp = -1
if (p_x+1) * 2 <= l_plus:
    max_pp = plus[p_x * 2] * plus[p_x * 2 + 1]
counter = 0
array = []
while counter * 2 + 1 < K:
    if max_pp > max_mm:
        array.append(plus[p_x * 2])
        array.append(plus[p_x * 2 + 1])
        p_x += 1
        if (p_x+1) * 2 <= l_plus:
            max_pp = plus[p_x * 2] * plus[p_x * 2 + 1]
        else:
            max_pp = -1

    else:
        array.append(minus[m_x * 2])
        array.append(minus[m_x * 2 + 1])
        m_x += 1
        if (m_x+1) * 2 <= l_minus:
            max_mm = minus[m_x * 2] * minus[m_x * 2 + 1]
        else:
            max_mm = -1
    counter += 1
if K%2 == 1:
    array.append(plus[p_x * 2])
result = 1
for each in array:
    result = result * each % M
print(result)

Submission status: Wrong Answer

Solution code:
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
M = 10**9 + 7
if N == K:
    result = 1
    for i in range(K):
        result = result * A[i] % M
    print(result)
    exit()
minus = [i for i in A if i < 0]
l_minus = len(minus)
plus = [i for i in A if i >= 0]
l_plus = len(plus)
plus.sort(reverse=1)
minus.sort()
if len(plus) == 0 and K % 2 == 1:
    result = 1
    for i in range(K):
        result = result * minus[-i-1] % M
    print(result)
    exit()

m_x = 0
p_x = 0
max_mm = -1
if (m_x+1) * 2 <= l_minus:
    max_mm = minus[m_x * 2] * minus[m_x * 2 + 1]
max_pp = -1
if (p_x+1) * 2 <= l_plus:
    max_pp = plus[p_x * 2] * plus[p_x * 2 + 1]
counter = 0
array = []
while counter * 2 + 1 < K:
    if max_pp > max_mm:
        array.append(plus[p_x * 2])
        array.append(plus[p_x * 2 + 1])
        p_x += 1
        if (p_x+1) * 2 <= l_plus:
            max_pp = plus[p_x * 2] * plus[p_x * 2 + 1]
        else:
            max_pp = -1

    else:
        array.append(minus[m_x * 2])
        array.append(minus[m_x * 2 + 1])
        m_x += 1
        if (m_x+1) * 2 <= l_minus:
            max_mm = minus[m_x * 2] * minus[m_x * 2 + 1]
        else:
            max_mm = -1
    counter += 1
if K%2 == 1:
    array.append(plus[p_x * 2])
result = 1
for each in array:
    result = result * each % M
print(result)

Submission status: Wrong Answer

Solution code:
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
M = 10**9 + 7
if N == K:
    result = 1
    for i in range(K):
        result = result * A[i] % M
    print(result)
    exit()
minus = [i for i in A if i <= 0]
l_minus = len(minus)
plus = [i for i in A if i > 0]
l_plus = len(plus)
plus.sort(reverse=1)
minus.sort()
if len(plus) == 0 and K % 2 == 1:
    result = 1
    for i in range(K):
        result = result * minus[-i-1] % M
    print(result)
    exit()

m_x = 0
p_x = 0
max_mm = -1
if (m_x+1) * 2 <= l_minus:
    max_mm = minus[m_x * 2] * minus[m_x * 2 + 1]
max_pp = -1
if (p_x+1) * 2 <= l_plus:
    max_pp = plus[p_x * 2] * plus[p_x * 2 + 1]
counter = 0
array = []
while counter * 2 + 1 != K:
    if max_pp > max_mm:
        array.append(plus[p_x * 2])
        array.append(plus[p_x * 2 + 1])
        p_x += 1
        if (p_x+1) * 2 <= l_plus:
            max_pp = plus[p_x * 2] * plus[p_x * 2 + 1]
        else:
            max_pp = -1
    elif max_pp == -1 and max_mm == -1:
        break
    else:
        array.append(minus[m_x * 2])
        array.append(minus[m_x * 2 + 1])
        m_x += 1
        if (m_x+1) * 2 <= l_minus:
            max_mm = minus[m_x * 2] * minus[m_x * 2 + 1]
        else:
            max_mm = -1
    counter += 1
if K%2 == 1:
    array.append(plus[p_x * 2])
result = 1
for each in array:
    result = result * each % M
print(result)

Submission status: Wrong Answer

Solution code:
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
M = 10**9 + 7
if N == K:
    result = 1
    for i in range(K):
        result = result * A[i] % M
    print(result)
    exit()
minus = [i for i in A if i <= 0]
l_minus = len(minus)
plus = [i for i in A if i > 0]
l_plus = len(plus)
plus.sort(reverse=1)
minus.sort()
if len(plus) == 0:
    result = 1
    for i in range(K):
        result = result * minus[-i-1] % M
    print(result)
    exit()

m_x = 0
p_x = 0
max_mm = -1
if (m_x+1) * 2 <= l_minus:
    max_mm = minus[m_x * 2] * minus[m_x * 2 + 1]
max_pp = -1
if (p_x+1) * 2 <= l_plus:
    max_pp = plus[p_x * 2] * plus[p_x * 2 + 1]
counter = 0
array = []
while counter * 2 + 1 != K:
    if max_pp > max_mm:
        array.append(plus[p_x * 2])
        array.append(plus[p_x * 2 + 1])
        p_x += 1
        if (p_x+1) * 2 <= l_plus:
            max_pp = plus[p_x * 2] * plus[p_x * 2 + 1]
        else:
            max_pp = -1
    elif max_pp == -1 and max_mm == -1:
        break
    else:
        array.append(minus[m_x * 2])
        array.append(minus[m_x * 2 + 1])
        m_x += 1
        if (m_x+1) * 2 <= l_minus:
            max_mm = minus[m_x * 2] * minus[m_x * 2 + 1]
        else:
            max_mm = -1
    counter += 1
if K%2 == 1:
    array.append(plus[p_x * 2])
result = 1
for each in array:
    result = result * each % M
print(result)

Submission status: Wrong Answer

Solution code:
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
M = 10**9 + 7
if N == K:
    result = 1
    for i in range(K):
        result = result * A[i] % M
    print(result)
    exit()
minus = [i for i in A if i <= 0]
l_minus = len(minus)
plus = [i for i in A if i > 0]
l_plus = len(plus)
plus.sort(reverse=1)
minus.sort()
if len(plus) == 0:
    result = 1
    for i in range(K):
        result = result * minus[-i-1] % M
    print(result)
    exit()

m_x = 0
p_x = 0
max_mm = -1
if (m_x+1) * 2 <= l_minus:
    max_mm = minus[m_x * 2] * minus[m_x * 2 + 1]
max_pp = -1
if (p_x+1) * 2 <= l_plus:
    max_pp = plus[p_x * 2] * plus[p_x * 2 + 1]
counter = 0
array = []
while counter * 2 + 1 < K:
    if max_pp > max_mm:
        array.append(plus[p_x * 2])
        array.append(plus[p_x * 2 + 1])
        p_x += 1
        if (p_x+1) * 2 <= l_plus:
            max_pp = plus[p_x * 2] * plus[p_x * 2 + 1]
        else:
            max_pp = -1
    elif max_pp == -1 and max_mm == -1:
        break
    else:
        array.append(minus[m_x * 2])
        array.append(minus[m_x * 2 + 1])
        m_x += 1
        if (m_x+1) * 2 <= l_minus:
            max_mm = minus[m_x * 2] * minus[m_x * 2 + 1]
        else:
            max_mm = -1
    counter += 1
if K%2 == 1:
    array.append(plus[p_x * 2])
result = 1
for each in array:
    result = result * each % M
print(result)

Submission status: Wrong Answer

Solution code:
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
M = 10**9 + 7
A = sorted(A, key=abs, reverse=1)
# 負の数になる場合
if max(A) < 0:
    result = 1
    for i in range(K):
        result = result * A[-i-1] % M
    print(result)
    exit()
if N == K:
    result = 1
    for i in range(K):
        result = result * A[i] % M
    print(result)
    exit()

minimum_minus_id = K
minimum_plus_id = K
minus_count = 0

for i in range(K):
    if A[i] < 0:
        minus_count += 1
        minimum_minus_id = i
    else:
        minimum_plus_id = i
result = 1

if minus_count%2 == 1:
    # 一番小さい負の数を正の数にするか、一番小さい正の数を負の数にするか
    second_minus_id = N
    second_plus_id = N

    for i in range(K, N):
        if A[i] >= 0:
            second_plus_id = i
            break
    for i in range(K, N):
        if A[i] < 0:
            second_minus_id = i
            break
    if second_minus_id == N or minimum_plus_id == K:
        A[minimum_minus_id] = A[second_plus_id]
    elif second_plus_id == N:
        A[minimum_plus_id] = A[second_minus_id]
    elif minimum_minus_id == K:
        pass
    else:
        if A[minimum_minus_id] * A[second_minus_id ] > A[minimum_plus_id] * A[second_plus_id]:
            A[minimum_plus_id] = A[second_minus_id]
        else:
            A[minimum_minus_id] = A[second_plus_id]

for i in range(K):
    result = result * A[i] % M
print(result)

Submission status: Wrong Answer

Solution code:
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
M = 10**9 + 7
A = sorted(A, key=abs, reverse=1)

minimum_minus_id = K
minus_count = 0

for i in range(K):
    if A[i] < 0:
        minus_count += 1
        minimum_minus_id = i
result = 1
if minus_count%2 ==1:
    for i in range(K, N):
        if A[i] > 0:
            A[minimum_minus_id] = A[i]
            break
    if A[minimum_minus_id] < 0:
        for i in range(K):
            result = result * A[-i-1] % M
    else:
        for i in range(K):
            result = result * A[i] % M 
else:
    for i in range(K):
        result = result * A[i] % M
print(result)

Submission status: Wrong Answer

Solution code:
# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# ------------------- fast io --------------------
from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y


for _ in range(int(input()) if not True else 1):
    n, k = map(int, input().split())
    #a, b = map(int, input().split())
    #c, d = map(int, input().split())
    a = list(map(int, input().split()))
    di = {}
    x = []
    for i in a:
        ab = abs(i)
        x += [ab]
        if ab not in di:
            di[ab] = []
        di[ab] += [1 if i>=0 else -1]

    x = sorted(x, reverse=True)
    signs = []
    for each in x:
        signs += [di[each].pop()]

    cursign = 1
    ans = 1
    firstpos = -1
    firstneg = 0
    nextpos = None
    nextneg = None
    for i in range(k):
        ans = (ans * x[i]) % (10**9+7)
        cursign *= signs[i]
        if signs[i] == 1:
            firstpos = i
        if signs[i] == -1:
            firstneg = i

    if cursign == 1:
        print(ans)
        quit()

    for i in range(k, len(x)):
        if signs[i] == 1 and nextpos is None:
            nextpos = i
        if signs[i] == -1 and nextneg is None:
            nextneg = i
    ansdex = [i for i in range(k)]
    from math import inf
    ans = ans*-1
    #print(ans)
    ans1, ans2 = -10**18, -10**18
    if nextpos is not None:
        ansd = [i for i in range(k)]
        ans22 = 1
        ansd[firstneg] = nextpos
        for each in ansd:
            ans22 = (ans22 * each) % (10**9+7)
        ans2 = ans22

    if nextneg is not None and firstpos != -1:
        ansd = [i for i in range(k)]
        ans22 = 1
        ansd[firstpos] = nextneg
        for each in ansd:
            ans22 = (ans22 * each) % (10 ** 9 + 7)
        ans1 = ans22

    if ans1 != -10**18 or ans2 != -10**18:
        print(max(ans1, ans2))
        quit()

    a = sorted(a, reverse=True)
    ans=1
    for i in range(k):ans=(ans*(a[i])) % (10**9+7)
    print(ans)

Submission status: Wrong Answer

Solution code:
def sgn(x):
    if x>0:
        return 1
    elif x<0:
        return -1
    else:
        return 0
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
mod=10**9+7
if K==N:
    ans=1
    for i in range(N):
        ans=ans*A[i]
        ans%=mod
    print(ans)
    exit()
if max(A)<0 and K%2==1:
    ans=1
    A.sort()
    for i in range(K):
        ans=ans*A[-i-1]
        ans%=mod
    print(ans)
    exit()
A.sort(key=lambda x:abs(x),reverse=True)
P=1
Pfugou=1
for i in range(K):
    P=P*A[i]
    P%=mod
    Pfugou=Pfugou*sgn(A[i])
if Pfugou!=-1:
    print(P)
    exit()
#xiを除いてyiを加える
#abs(x1/y1)が小さいほうが良い
#abs(yi)は大きいほうがいい
#abs(xi)は小さいほうがいい
x1=10**15
x2=10**15
y1=0
y2=0
for i in range(K):
    if A[i]<0:
        x2=abs(A[i])
    elif A[i]>0:
        x1=abs(A[i])
for i in range(N-1,K-1,-1):
    if A[i]<0:
        y1=abs(A[i])
    elif A[i]>0:
        y2=abs(A[i])
if y1==0 and y2==0:
    print(0)
elif abs(x2*y1)<=abs(x1*y2):
    #y2/x2のほうが大きい
    print((-P*pow(x2,mod-2,mod)*y2)%mod)
else:
    print((-P*pow(x1,mod-2,mod)*y1)%mod)