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

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
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:
    ans = 1
    for k in range(K):
        ans *= -nums[k][0]
        ans %= mod
    print(ans)
    import sys
    sys.exit()
ans = 1
pl = []
ml = []
for k in range(K):
    x, b = nums.pop()
    if b:
        ans *= x
        ans %= mod
        pl.append(x)
    else:
        ans *= -x
        ans %= mod
        ml.append(x)
if len(ml) % 2 != 0:
    while nums:
        x, b = nums.pop()
        if b:
            if ml:
                ans *= x
                ans //= -ml[-1]
                ans %= mod
                break
        else:
            if pl:
                ans *= -x
                ans //= pl[-1]
                ans %= mod
                break
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
from collections import deque

mod = 10 ** 9 + 7
n, k = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
n_minus = bisect_left(A, 0)
n_zero = bisect_right(A, 0) - n_minus
n_plus = n - n_minus - n_zero

possible_max = min(k, n_minus)
possible_min = max(k - (n_plus + n_zero), 0)
ans = 1
if possible_max == possible_min and possible_min % 2 == 1:
    if k - (possible_min) > 0 and n_zero > 0:
        print(0)
        exit()
    A_plus = A[n - (n_plus) :]
    A_minus = A[:n_minus]
    A_minus.sort(reverse=True)
    # 負の数は奇数個小さい方から選ぶ
    for i in range(possible_min):
        ans *= A_minus[i]
        ans %= mod
    for i in range(k - possible_min):
        ans *= A_plus[i]
        ans %= mod
else:
    A_plus = A[n - (n_plus) :]
    A_plus.sort(reverse=True)
    AP = deque(A_plus)
    A_minus = A[:n_minus]
    AM = deque(A_minus)
    minus_num_max = min(n_minus // 2, k // 2)
    select = k - 2 * minus_num_max  # 選ばざるを得ない数
    if n_plus < select:
        print(0)
        exit()
    kouho = []
    while k > 0:
        if n_plus >= 2:
            kouho1 = AP.popleft()
            kouho2 = AP.popleft()
            plus_kouho = kouho1 * kouho2
        elif n_plus == 1:
            kouho1 = AP.popleft()
            kouho2 = 0
            plus_kouho = kouho1
        else:
            kouho1, kouho2 = 0, 0
            plus_kouho = 0

        if n_minus >= 2:
            kouho3 = AM.popleft()
            kouho4 = AM.popleft()
            minus_kouho = kouho3 * kouho4
        else:
            kouho3 = 0
            kouho4 = 0
            minus_kouho = -1
        if plus_kouho > minus_kouho:
            n_plus -= 1
            k -= 1
            ans *= kouho1
            if kouho2 > 0:
                AP.appendleft(kouho2)
            ans %= mod
            if minus_kouho > 0:
                AM.appendleft(kouho4)
                AM.appendleft(kouho3)
        else:
            k -= 2
            n_minus -= 2
            ans *= minus_kouho
            ans %= mod
            if kouho2 > 0:
                AP.appendleft(kouho2)
            if kouho1 > 0:
                AP.appendleft(kouho1)
            if plus_kouho > 0:
                if kouho2 > 0:
                    AP.appendleft(kouho2)
                if kouho1 > 0:
                    AP.appendleft(kouho1)


print(ans % mod)

Submission status: Wrong Answer

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import *

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

for Ai in A:
    if Ai>=0:
        p.append(Ai)
    else:
        n.append(Ai)

if len(p)==0 and K%2==1:
    if 0 in A:
        print(0)
    else:
        n.sort(reverse=True)
        ans = 1
        
        for ni in n[:K]:
            ans *= ni
            ans %= MOD
        
        print(ans)
    exit()
    
if K==N:
    ans = 1
    
    for Ai in A:
        ans *= Ai
        ans %= MOD
    
    print(ans)
    exit()

p.sort(reverse=True)
n.sort()

if K%2==0:
    l = []
    
    for i in range(len(p)//2):
        l.append(p[2*i]*p[2*i+1])
    
    for i in range(len(n)//2):
        l.append(n[2*i]*n[2*i+1])

    l.sort(key=lambda x: abs(x), reverse=True)
    ans = 1
    
    for i in range(K//2):
        ans *= l[i]
        ans %= MOD
else:
    ans = p[0]
    l = []
    
    for i in range(len(p)//2):
        l.append(p[2*i]*p[2*i+1])
    
    for i in range(len(n)//2):
        l.append(n[2*i]*n[2*i+1])
    
    l.sort(key=lambda x: abs(x), reverse=True)
    
    for i in range((K-1)//2):
        ans *= l[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:
    ans = 1
    for k in range(K):
        ans *= -nums[k][0]
        ans %= mod
    print(ans)
    import sys
    sys.exit()
ans = 1
pl = []
ml = []
for k in range(K):
    x, b = nums.pop()
    if b:
        ans *= x
        ans %= mod
        pl.append(x)
    else:
        ans *= -x
        ans %= mod
        ml.append(x)
if len(ml) % 2 != 0:
    while nums:
        x, b = nums.pop()
        if b:
            if ml:
                ans //= -ml[-1]
                ans %= mod
                ans *= x
                ans %= mod
                break
        else:
            if pl:
                ans //= pl[-1]
                ans %= mod
                ans *= -x
                ans %= mod
                break
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

import heapq
import collections

class HeapQueue:

    def __init__(self, xs, mode):
        if   mode == "min": self.xs = [+x for x in xs]
        elif mode == "max": self.xs = [-x for x in xs]
        else              : raise NotImplementedError("HeapQueue.__init__: mode should be 'min' or 'max'")
        heapq.heapify(xs)
        self.mode = mode

    def __len__(self):
        return len(self.xs)

    def pop(self):
        if   self.mode == "min": return heapq.heappop(self.xs)
        elif self.mode == "max": return heapq.heappop(self.xs) * (-1)

    def push(self, x):
        if   self.mode == "min": return heapq.heappush(self.xs,  x)
        elif self.mode == "max": return heapq.heappush(self.xs, -x)

    # @staticmethod
    # def __test01__():
    #     xs = HeapQueue([-3, 2, 9, -4], "min")
    #     x0 = xs.pop()
    #     x1 = xs.pop()
    #     x2 = xs.pop()
    #     x3 = xs.pop()
    #     return (x0 == -4 and x1 == -3 and x2 == 2 and x3 == 9)


N, K = tuple(map(int, input().strip().split()))
As = list(map(int, input().strip().split()))

D = int(1E9 + 7)
r = 1

if N == K:

    for a in As:
        r = (r * a) % D

elif all(a >= 0 for a in As):

    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * a) % D

elif K % 2 == 1 and all(a < 0 for a in As):

    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * a) % D

elif K % 2 == 0 and all(a < 0 for a in As):

    As = sorted(As)
    for a in As[:K]:
        r = (r * a) % D

else:

    As = sorted(As, key = lambda a: abs(a), reverse=True)

    used = As[:K]
    rest = As[K:]
    num_negative_sign = sum([1 if x < 0 else 0 for x in used])

    if num_negative_sign % 2 != 0:

        used_min_pos = None
        used_min_neg = None
        for k in range(K-1, -1, -1):
            if   used_min_pos is None and used[k] >= 0: used_min_pos = k
            elif used_min_neg is None and used[k] <  0: used_min_neg = k
            if used_min_pos and used_min_neg:
                break

        rest_min_pos = None
        rest_min_neg = None
        for k in range(N-K-1, -1, -1):
            if   rest_min_pos is None and rest[k] >= 0: rest_min_pos = k
            elif rest_min_neg is None and rest[k] <  0: rest_min_neg = k
            if rest_min_pos and rest_min_neg:
                break

        if used_min_pos is None or rest_min_neg is None:
            used[used_min_neg] = rest_min_pos
        elif used_min_neg is None or rest_min_pos is None:
            used[used_min_pos] = rest_min_neg
        else:
            v1 = abs(used[used_min_pos] * rest[rest_min_neg])
            v2 = abs(used[used_min_neg] * rest[rest_min_pos])
            if v1 < v2:
                used[used_min_pos] = rest_min_neg
            else:
                used[used_min_neg] = rest_min_pos

    for a in used:
        r = (r * a) % D

print(r)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker

Submission status: Wrong Answer

Solution code:
import sys

from numpy.lib.function_base import kaiser
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

import numpy as np
import math


N, K = map(int, readline().rstrip().split())
AB = np.array(readline().rstrip().split(), np.int32)
p = 10 ** 9 + 7

A = AB[AB >= 0]
B = AB[AB < 0]

ans = 1
f = 1
if K == N:
    for a in A.tolist():
        ans *= a
        ans %= p
    for b in B.tolist():
        ans *= b
        ans %= p
else:
    A = np.sort(A)
    B = np.sort(B)
    if A.size == 0:
        if K % 2 == 0:
            for i in range(K):
                ans *= B[i]
                ans %= p
        else:
            for i in range(K):
                ans *= B[-i - 1]
                ans %= p

    else:
        AB = np.concatenate([A, B])
        AB = np.array(list(sorted(AB, key=lambda x: abs(x))))
        maxAB = max(AB)
        minAB = min(AB)
        AB = AB[-K:]
        for n in AB.tolist():
            ans *= n
            ans %= p
        
        if ans < 0:
            ans = ans / maxAB * minAB
            ans %= p


print(ans)

Submission status: Wrong Answer

Solution code:

def resolve():
  N, K = map(int, input().split(" "))
  A = [int(x) for x in input().split(" ")]
  abs_sorted_A = sorted(A, key=abs, reverse=True)

  if len([i for i in abs_sorted_A if i > 0]) == 0 and K%2==1:
    if 0 in abs_sorted_A:
      print(0)
      return True
    else:
      result = 1
      abs_sorted_A.reverse()
      for temp_abs_a in abs_sorted_A[:K]:
        result *= temp_abs_a
      print(result%10**9+7)
      return True

  temp_abs_A = abs_sorted_A[:K]
  # print(abs_sorted_A[:K])
  # print(abs_sorted_A[K:])
  result = 1
  if len([i for i in temp_abs_A if i < 0])%2 == 0:
    for temp_abs_a in temp_abs_A:
      result *= temp_abs_a
    print(result%(10**9+7))
    return True
  # else:
  #   if len([i for i in abs_sorted_A[K:] if i < 0]) == 0:

  print(result%(10**9+7))

if __name__ == "__main__":
  resolve()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
from collections import deque

mod = 10 ** 9 + 7
n, k = map(int, input().split())
A = list(map(int, input().split()))
# dp = [[[0] * (2) for _ in range(k+1)]for _ in range(n+1)]
# # dp[桁][数][負数の数=1,0]

A.sort()
n_minus = bisect_left(A, 0)
n_zero = bisect_right(A, 0) - n_minus
n_plus = n - n_minus - n_zero

possible_max = min(k, n_minus)
possible_min = max(k - (n_plus + n_zero), 0)
ans = 1
if possible_max == possible_min and possible_min % 2 == 1:
    if k - (possible_min) > 0 and n_zero > 0:
        print(0)
        exit()
    A_plus = A[n - (n_plus) :]
    A_minus = A[:n_minus]
    A_minus.sort(reverse=True)
    # 負の数は奇数個小さい方から選ぶ
    for i in range(possible_min):
        ans *= A_minus[i]
        ans %= mod
    for i in range(k - possible_min):
        ans *= A_plus[i]
        ans %= mod
else:
    A_plus = A[n - (n_plus) :]
    A_plus.sort(reverse=True)
    AP = deque(A_plus)
    A_minus = A[:n_minus]
    AM = deque(A_minus)
    minus_num_max = min(n_minus // 2, k // 2)
    select = k - 2 * minus_num_max  # 選ばざるを得ない数
    if n_plus < select:
        print(0)
        exit()
    kouho = []
    while k > 0:
        if n_plus >= 2:
            kouho1 = AP.popleft()
            kouho2 = AP.popleft()
            plus_kouho = kouho1 * kouho2
        elif n_plus == 1:
            kouho1 = AP.popleft()
            kouho2 = 0
            plus_kouho = kouho1
        else:
            kouho1, kouho2 = 0, 0
            plus_kouho = 0

        if n_minus >= 2:
            kouho3 = AM.popleft()
            kouho4 = AM.popleft()
            minus_kouho = kouho3 * kouho4
        else:
            kouho3 = 0
            kouho4 = 0
            minus_kouho = -1
        if plus_kouho > minus_kouho:
            n_plus -= 1
            k -= 1
            ans *= kouho1
            if kouho2 > 0:
                AP.appendleft(kouho2)
            ans %= mod
            if minus_kouho > 0:
                AM.appendleft(kouho4)
                AM.appendleft(kouho3)
        else:
            k -= 2
            n_minus -= 2
            ans *= minus_kouho
            ans %= mod
            if kouho2 > 0:
                AP.appendleft(kouho2)
            if kouho1 > 0:
                AP.appendleft(kouho1)


print(ans % mod)

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
index_change = 0
ans = 1
for i in range(n-1):
    if a[i] <= 0 and a[i+1] > 0:
        index_change = i+1
        break
else:
    for i in range(1, k+1):
        ans *= a[-i]
        ans %= mod
    print(ans)
    exit()
l = 0
r = n-1
while k > 0:
    if k == 1:
        if r >= index_change:
            ans *= a[r]
            ans %= mod
            break
        else:
            ans *= a[l]*a[l+1]
            ans %= mod
            ans *= pow(a[r+1], mod-2, mod)
            ans %= mod
            break
    else:
        left = a[l]*a[l+1]
        right = a[r]*a[r-1]
        if left >= right:
            ans *= left
            ans %= mod
            l += 2
            k -= 2
        else:
            ans *= a[r]
            ans %= mod
            r -= 1
            k -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
  N, K = map(int, input().split(" "))
  A = [int(x) for x in input().split(" ")]
  abs_sorted_A = sorted(A, key=abs, reverse=True)

  if len([i for i in abs_sorted_A if i > 0]) == 0 and K%2==1:
    if 0 in abs_sorted_A:
      print(0)
      return True
    else:
      result = 1
      abs_sorted_A.reverse()
      for temp_abs_a in abs_sorted_A[:K]:
        result *= temp_abs_a
      print(result%10**9+7)
      return True

  temp_abs_A = abs_sorted_A[:K]
  # print(abs_sorted_A[:K])
  # print(abs_sorted_A[K:])
  result = 1
  if len([i for i in temp_abs_A if i < 0])%2 == 0:
    for temp_abs_a in temp_abs_A:
      result *= temp_abs_a
    print(result%(10**9+7))
    return True
  # else:
  #   if len([i for i in abs_sorted_A[K:] if i < 0]) == 0:

  print(result%(10**9+7))

if __name__ == "__main__":
  resolve()

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
a =list(map(int, input().split()))
ans =1

if n == k:
   for i in a:
       ans *= i
       if abs(ans) >10**9+7:
           ans = ans%(10**9+7)

elif all(i <= 0 for i in a) and k%2 ==1:
    a.sort(reverse = True)
    for i in range(k):
        ans *= a[i]
        if abs(ans) > 10 ** 9 + 7:
            ans = ans % (10 ** 9 + 7)

else:
    am =[]
    ap =[]

    a.sort(key = abs,reverse = True)
    amax = a[:k]
    amin = a[k:]
    c=1
    if 0 in amax:
        ans = 0
    else:
        for i in amax:
            if i<0:
                am.append(i)
                c *=-1
            elif i>0:
                ap.append(i)
        if c ==1:
            for i in amax:
                ans *= i
                if abs(ans) > 10 ** 9 + 7:
                    ans = ans % (10 ** 9 + 7)
        else:
            if ap == []:
                amax.remove(max(am))
                amax.append(max(amin))

            elif max(am)*min(amin) > min(ap)*max(amin):
                amax.remove(max(am))
                amax.append(max(amin))
            else:
                amax.remove(min(ap))
                amax.append(min(amin))
            for i in amax:
                ans *= i
                if abs(ans) > 10 ** 9 + 7:
                    ans = ans % (10 ** 9 + 7)

print(ans % (10 ** 9 + 7))

Submission status: Wrong Answer

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

if n==k:
  ans=1
  for i in range(k):ans=ans*a[i]%MOD
  print(ans)
  exit()

p=[]
m=[]
for q in a:
  if q>=0:p+=q,
  else:m+=q,

if p==[] and k%2==1:
  m.sort(reverse=True)
  ans=1
  for i in range(k):ans=ans*m[i]%MOD
  print(ans)
  exit()

a.sort(key=lambda x:abs(x),reverse=True)

s=[]
flg=1
for i in range(k):
  s.append(a[i])
  if a[i]<0:
    flg*=-1
if flg==-1:
  tmp=s.pop()
  if -tmp in s:
    s.append(a[k])
  else:
    for i in range(k,n):
      if a[i]*tmp<=0:
        s.append(a[i])
        break
ans=1
for i in s:
  ans=ans*abs(i)%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
mod = 10**9 + 7
nums = []
for i in list(map(int, input().split())):
    if i >= 0:
        nums.append((i, True))
    else:
        nums.append((-i, False))
rev_nums = sorted(nums, reverse=True)
nums.sort()
ans = 1
pl = []
ml = []
for k in range(K):
    x, b = nums.pop()
    if b:
        ans *= x
        ans %= mod
        pl.append(x)
    else:
        ans *= -x
        ans %= mod
        ml.append(x)
if len(ml) % 2 != 0:
    while nums:
        x, b = nums.pop()
        if b:
            if ml:
                ans //= -ml[-1]
                ans %= mod
                ans *= x
                ans %= mod
                break
        else:
            if pl:
                ans //= pl[-1]
                ans %= mod
                ans *= -x
                ans %= mod
                break
    else:
        ans = -1
        for k in range(K):
            x, b = rev_nums.pop()
            if b:
                ans *= x
                ans %= mod
            else:
                ans *= -x
                ans %= mod
print(ans)

Submission status: Wrong Answer

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

if n==k:
  ans=1
  for i in range(k):ans=ans*a[i]%MOD
  print(ans)
  exit()

p=[]
m=[]
for q in a:
  if q>=0:p+=q,
  else:m+=q,

if p==[] and k%2==1:
  m.sort(reverse=True)
  ans=1
  for i in range(k):ans=ans*m[i]%MOD
  print(ans)
  exit()

a.sort(key=lambda x:abs(x),reverse=True)

s=[]
flg=1
for i in range(k):
  s.append(a[i])
  if a[i]<0:
    flg*=-1
if flg==-1:
  tmp=s.pop()
  if -tmp in s:
    s.append(a[k])
  else:
    for i in range(k,n):
      if a[i]*tmp<=0:
        s.append(a[i])
        break
ans=1
for i in s:
  ans=ans*i%MOD
print(ans)

Submission status: Wrong Answer

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

a.sort(reverse=True, key=lambda x:abs(x))
cnt = 0
im = -1
ip = -1
cp = 0
mod = 10 ** 9 + 7
nm = 0
np = 0

for i, ai in enumerate(a):
    if i < k:
        if ai < 0:
            im = i
            cnt += 1
        if ai > 0:
            ip = i
    else:
        if ai < 0 and nm == 0:
            nm = ai
        if ai > 0 and np == 0:
            np = ai
    if ai > 0:
        cp += 1

ans = 1
f = 0

# print(a)
if cnt % 2 and k < n:
    if cp == 0:
        a.sort(reverse=True)
        for i, ai in enumerate(a):
            if i == k:
                break
            ans *= ai
            ans %= mod
        print(ans) # ok
    else:
        ans = 1
        cnt = 0
        f1 = 0
        f2 = 0
        for i, ai in enumerate(a):
            if cnt == k - 2:
                break
            if i == im:
                f1 = 1
                continue
            if i == ip:
                f2 = 1
                continue
            if f1 and ai <= 0:
                continue
            if f2 and ai >= 0:
                continue
            ans *= ai
            ans %= mod
            # print(i, ai)
            cnt += 1
        ans *= max(a[ip] * np, a[im] * nm)
        ans %= mod
        print(ans)
else:
    for i, ai in enumerate(a):
        if i == k:
            break
        ans *= ai
        ans %= mod
    print(ans) # ok

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
mod = 10**9 + 7
nums = []
for i in list(map(int, input().split())):
    if i >= 0:
        nums.append((i, True))
    else:
        nums.append((-i, False))
rev_nums = sorted(nums, reverse=True)
nums.sort()
ans = 1
pl = []
ml = []
for k in range(K):
    x, b = nums.pop()
    if b:
        ans *= x
        ans %= mod
        pl.append(x)
    else:
        ans *= -x
        ans %= mod
        ml.append(x)
if len(ml) % 2 != 0:
    while nums:
        x, b = nums.pop()
        if b:
            if ml:
                ans //= -ml[-1]
                ans %= mod
                ans *= x
                ans %= mod
                break
        else:
            if pl:
                ans //= pl[-1]
                ans %= mod
                ans *= -x
                ans %= mod
                break
    else:
        ans = -1
        for k in range(K):
            x, b = rev_nums.pop()
            ans *= x
            ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
modulo = 10 ** 9 + 7
*arr, = map(int, input().split())
inverses = [pow(v, modulo - 2, modulo) for v in arr]
neg_cnt = 0
for v in arr:
    if v < 0:
        neg_cnt += 1

def min_pos(arr):
    pass


if k == n:
    res = 1
    for v in arr:
        res *= v
        res %= modulo
    print(res)
elif neg_cnt == n and k % 2 == 1:
    res = 1
    arr.sort(reverse=True)
    for i in range(k):
        res *= arr[i]
        res %= modulo
    print(res)
else:
    pos = []
    neg = []
    for i, v in enumerate(arr):
        if v < 0:
            neg.append(i)
        else:
            pos.append(i)

    neg.sort(key=lambda v: abs(arr[v]), reverse=True)
    pos.sort(key=lambda v: abs(arr[v]), reverse=True)

    res = 1
    i = 0
    j = 0
    while i + j < k and (i < len(pos) - 1 or j < len(neg) - 1):
        if j >= len(neg) - 1 or i < len(pos) - 1 and arr[pos[i]] * arr[pos[i + 1]] > arr[neg[j]] * arr[neg[j + 1]]:
            res *= arr[pos[i]]
            res *= arr[pos[i + 1]]
            i += 2
        else:
            res *= arr[neg[j]]
            res *= arr[neg[j + 1]]
            j += 2
        res %= modulo

    while i + j < k:
        res *= arr[pos[i]]
        i += 1
        res %= modulo

    print(res)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
mod = 10**9 + 7
nums = []
for i in list(map(int, input().split())):
    if i >= 0:
        nums.append((i, True))
    else:
        nums.append((-i, False))
rev_nums = sorted(nums, reverse=True)
nums.sort()
ans = 1
pl = []
ml = []
for k in range(K):
    x, b = nums.pop()
    ans *= x
    ans %= mod
    if b:
        pl.append(x)
    else:
        ml.append(x)
if len(ml) % 2 != 0:
    while nums:
        x, b = nums.pop()
        if b:
            if ml:
                ans //= ml[-1]
                ans %= mod
                ans *= x
                ans %= mod
                break
        else:
            if pl:
                ans //= pl[-1]
                ans %= mod
                ans *= x
                ans %= mod
                break
    else:
        ans = -1
        for k in range(K):
            x, b = rev_nums.pop()
            ans *= x
            ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
from math import *
ln,k=list(map(int,input().split()))
l=list(map(int,input().split()))
l.sort(reverse=True,key = lambda s: abs(s))
# print(l)
lul = 10**9 + 7

brainFucked = 0
temp = []
for i in range(ln):
	if l[i]<0:
		temp.append(-1*l[i])
		brainFucked+=1
ct = 0
p = -1; n = -1
ans = []
temp = temp[::-1]
for i in range(k):
	ans.append(i)
	if l[i]<0:
		ct+=1
		n = max(n,i)
	else:
		p = max(p,i)
# print(ct)
if ct%2!=0:
	for i in range(k,ln):
		if l[i]<0 and p!=-1:
			ans.remove(p)
			ans.append(i)
			ct+=1
			break
		elif l[i]>=0:
			ans.remove(n)
			ans.append(i)
			ct-=1
			break
# print(ct)
if ct%2!=0:
	v = 1
	if brainFucked==ln:
		for i in range(k):
			v = (v*temp[i])%lul
	else:
		for i in ans:
			v = (v*abs(l[i]))%lul
	v = ((lul-1)*v)%lul
else:
	v = 1
	# print(ans)
	# print(l)
	for i in ans:
		v = (v*abs(l[i]))%lul
print(v)

Submission status: Wrong Answer

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

a.sort(reverse=True, key=lambda x:abs(x))
cnt = 0
im = -1
ip = -1
cp = 0
mod = 10 ** 9 + 7
nm = 0
np = 0

for i, ai in enumerate(a):
    if i < k:
        if ai < 0:
            im = i
            cnt += 1
        if ai > 0:
            ip = i
    else:
        if ai < 0 and nm == 0:
            nm = ai
        if ai > 0 and np == 0:
            np = ai
    if ai > 0:
        cp += 1

ans = 1
f = 0

# print(a)
if cnt % 2 and k < n:
    if cp == 0:
        a.sort(reverse=True)
        for i, ai in enumerate(a):
            if i == k:
                break
            ans *= ai
            ans %= mod
        print(ans) # ok
    else:
        ans = 1
        cnt = 0
        f1 = 0
        f2 = 0
        for i, ai in enumerate(a):
            if cnt == k - 2:
                break
            if i == im:
                f1 = 1
                continue
            if i == ip:
                f2 = 1
                continue
            if f1 and ai <= 0:
                continue
            if f2 and ai >= 0:
                continue
            ans *= abs(ai)
            ans %= mod
            # print(i, ai)
            cnt += 1
        ans *= max(a[ip] * np, a[im] * nm)
        ans %= mod
        print(ans)
else:
    for i, ai in enumerate(a):
        if i == k:
            break
        ans *= ai
        ans %= mod
    print(ans) # ok