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:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

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

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,K = IL()
A = IL()
IS_P = False

for a in A:
  if a>=0:
    IS_P = True

A = sorted(A,key= lambda x:-abs(x))
S = [a//abs(a) if abs(a)!=0 else 0 for a in A]

if not IS_P and K%2==1:
  ans = 1
  for i in range(K):
    ans *= A[N-1-i]
    ans %= MOD
  print(ans)
  exit()

count_M = 0
last_M = None
last_P = None
for i in range(K):
  if S[i] == -1:
    last_M = i
    count_M += 1
  if S[i] == 1:
    last_P = i

if count_M%2 == 0:
  ans = 1
  for i in range(K):
    ans *= A[i]
    ans %= MOD
  print(ans)
  exit()

else:
  ANS1 = -INF
  ANS2 = -INF
  if last_M!=None:
    for i in range(K,N):
      if S[i] == 1:
        ans = 1
        for ii in range(K):
          if ii != last_M:
            ans *= A[ii]
            ans %= MOD
        ans *= A[i]
        ans %= MOD
        ANS1 = ans
        break
  if last_P!=None:
    for i in range(K,N):
      if S[i] == -1:
        ans = 1
        for ii in range(K):
          if ii != last_P:
            ans *= A[ii]
            ans %= MOD
        ans *= A[i]
        ans %= MOD
        ANS2 = ans
        break
  print(max(ANS1,ANS2))

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))
mod = 10**9+7
nega = 0
posi = 0
zero = 0
for i in range(n):
    if a[i] > 0:
        posi += 1
    elif a[i] == 0:
        zero += 1
    else:
        nega += 1

if n == k:
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod
    if nega%2 == 1:
        ans *= -1

elif posi == 0:

    if k % 2 == 0:
        ans = 1
        for i in range(k):
            ans *= abs(a[i])
            ans %= mod

    else:
        if zero > 0:
            ans = 0
        else:
            a.reverse()
            ans = 1
            for i in range(k):
                ans *= abs(a[i])
                ans %= mod

            ans *= -1


else:
    posi = 0
    nega = 0
    zero = 0
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod

    for i in range(k):
        if a[i] > 0:
            posi += 1
        elif a[i] < 0:
            nega += 1
        else:
            zero += 1

    if zero > 0:
        ans = 0

    elif nega % 2 != 0:
        minposi = 0
        minnega = 0
        for i in range(k-1, -1, -1):
            if a[i] > 0:
                if minposi == 0:
                    minposi = a[i]
            else:
                if minnega == 0:
                    minnega = a[i]

        maxposi = 0
        maxnega = 0
        for i in range(k, n):
            if a[i] > 0:
                if maxposi == 0:
                    maxposi = a[i]
            else:
                if maxnega == 0:
                    maxnega = a[i]


        if abs(minposi*maxposi) <= abs(minnega*maxnega):
            ans *= pow(abs(minposi), mod-2, mod)
            ans *= abs(maxnega)

        else:
            ans *= pow(abs(minnega), mod-2, mod)
            ans *= abs(maxposi)



print(ans % mod)

Submission status: Wrong Answer

Solution code:
from collections import deque
import math

def Next(): return input()
def NextInt(): return int(Next())
def NextInts(): return map(int,input().split())
def Nexts(): return map(str,input().split())
def NextIntList(): return list(map(int,input().split()))
def RowInts(n): return [input() for i in range(n)]

def solve():
    n, k = NextInts()
    da = NextIntList()
    ans = 1
    MOD = 10**9+7
    
    if n == k:
        for i in range(n):
            ans = ans*da[i]%MOD
        return ans
    
    neg = []
    pos = []
    for i in range(n):
        if da[i] < 0:
            neg.append(da[i])
        else:
            pos.append(da[i])
    neg.sort()
    pos.sort()

    neg.reverse()
    if len(pos) == 0 and k%2 == 1:
        for i in range(k):
            ans = ans * da[i] % MOD
        return ans
    
    pos.reverse()
    li = []
    po, ne = 0, 0
    if k%2 == 1:
        po = 1
        ans = pos[0]
    while po+1 < len(pos):
        li.append(pos[po]*pos[po+1])
        po += 2
    while ne+1 < len(neg):
        li.append(neg[ne]*neg[ne+1])
        ne += 2
    li.sort()
    li.reverse()
    for i in range(k//2):
        ans = li[i] * ans % MOD
    return ans

if __name__ == "__main__":
    print(solve())

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    a = LI()
    a.sort(key = lambda x:-abs(x))
    p = 0
    m = 0
    for i in a:
        if i >= 0:
            p += 1
        else:
            m += 1
    f = 1
    for x in range(min(p,k)+1):
        y = k-x
        if y < 0 or y > m:
            continue
        if not y&1:
            f = 0
            break
    if f:
        a.sort(key = lambda x:abs(x))
        ans = 1
        for i in a[:k]:
            ans *= i
            ans %= mod
        print(ans)
        return
    minus = []
    a.sort()
    s = 1
    s2 = 1
    k1 = 0
    k2 = 0
    ans = 1
    if k&1:
        ans *= a[-1]
        a = a[:-1]
        k -= 1
    for i in a:
        if i < 0:
            k1 ^= 1
            s *= -i
            if not k1:
                minus.append(s)
                s = 1
        else:
            k2 ^= 1
            s2 *= i
            if not k2:
                minus.append(s2)
                s2 = 1
    x = k>>1
    minus.sort(reverse = True)
    for m in minus[:x]:
        ans *= m
        ans %= mod
    print(ans%mod)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

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

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,K = IL()
A = IL()
IS_P = False

for a in A:
  if a>0:
    IS_P = True

A = sorted(A,key= lambda x:-abs(x))
S = [a//abs(a) if abs(a)!=0 else 0 for a in A]

if not IS_P and K%2==1:
  ans = 1
  for i in range(K):
    ans *= A[N-1-i]
    ans %= MOD
  print(ans)
  exit()

count_M = 0
last_M = None
last_P = None
for i in range(K):
  if S[i] == -1:
    last_M = i
    count_M += 1
  if S[i] == 1:
    last_P = i

if count_M%2 == 0:
  ans = 1
  for i in range(K):
    ans *= A[i]
    ans %= MOD
  print(ans)
  exit()

else:
  ANS1 = -INF
  ANS2 = -INF
  if last_M!=None:
    for i in range(K,N):
      if S[i] == 1:
        ans = 1
        for ii in range(K):
          if ii != last_M:
            ans *= A[ii]
            ans %= MOD
        ans *= A[i]
        ans %= MOD
        ANS1 = ans
        break
  if last_P!=None:
    for i in range(K,N):
      if S[i] == -1:
        ans = 1
        for ii in range(K):
          if ii != last_P:
            ans *= A[ii]
            ans %= MOD
        ans *= A[i]
        ans %= MOD
        ANS2 = ans
        break
  print(max(ANS1,ANS2))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left,bisect_right
p=10**9+7
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
pi=1
ni=0
ans=1
for _ in range(k//2):
  if a[ni]*a[ni+1]>a[-pi]*a[-pi-1]:
    ans=ans*a[ni]*a[ni+1]%p
    ni+=2
  else:
    ans=ans*a[-pi]*a[-pi-1]%p
    pi+=2
if k%2==1:
  ans=ans*a[-pi]%p
if a[-1]<0:
  ans=1
  for i in a[n-k:]:
    ans=ans*i%p
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))
mod = 10**9+7
nega = 0
posi = 0
zero = 0
for i in range(n):
    if a[i] > 0:
        posi += 1
    elif a[i] == 0:
        zero += 1
    else:
        nega += 1

if n == k:
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod
    if nega%2 == 1:
        ans *= -1

elif posi == 0:

    if k % 2 == 0:
        ans = 1
        for i in range(k):
            ans *= abs(a[i])
            ans %= mod

    else:
        if zero > 0:
            ans = 0
        else:
            a.reverse()
            ans = 1
            for i in range(k):
                ans *= abs(a[i])
                ans %= mod

            ans *= -1


else:
    posi = 0
    nega = 0
    zero = 0
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod

    for i in range(k):
        if a[i] > 0:
            posi += 1
        elif a[i] < 0:
            nega += 1
        else:
            zero += 1

    if zero > 0:
        ans = 0

    elif nega % 2 != 0:
        minposi = 0
        minnega = 0
        for i in range(k-1, -1, -1):
            if a[i] > 0:
                if minposi == 0:
                    minposi = a[i]
            else:
                if minnega == 0:
                    minnega = a[i]

        maxposi = -10**18
        maxnega = -10**18
        for i in range(k, n):
            if a[i] > 0:
                if maxposi == -10**18:
                    maxposi = a[i]
            else:
                if maxnega == -10**18:
                    maxnega = a[i]


        if abs(minposi*maxposi) < abs(minnega*maxnega):
            ans *= pow(abs(minposi), mod-2, mod)
            ans *= abs(maxnega)

        else:
            ans *= pow(abs(minnega), mod-2, mod)
            ans *= abs(maxposi)



print(ans % mod)

Submission status: Wrong Answer

Solution code:
from collections import Counter, 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:
    def f(x):
        if x == 0:
            return 10 ** 9
        else:
            return abs(x)


    A = sorted(A, key=f)
    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()

    for i in range(K):
        if A[i] >= 0:
            plus.append(A[i])
        else:
            minus.append(A[i])

    if len(minus) % 2 == 1:
        tplus = deque()
        tminus = deque()
        if len(plus) == 0:
            for a in A[K:]:
                if a >= 0 and len(tplus) < 2:
                    tplus.append(a)
                if a < 0 and len(tminus) < 1:
                    tminus.append(a)
                if len(tplus) == 2 and len(tminus) == 1:
                    break
            if len(tplus) < 2:
                minus.append(tminus.popleft())
            elif len(tminus) < 1:
                minus.pop()
                plus = tplus
            elif minus[-1] * tminus[0] > tplus[0] * tplus[1]:
                minus.append(tminus.popleft())
            else:
                minus.pop()
                plus = tplus
        else:
            for a in A[K:]:
                if a >= 0 and len(tplus) < 1:
                    tplus.append(a)
                if a < 0 and len(tminus) < 1:
                    tminus.append(a)
                if len(tplus) == 1 and len(tminus) == 1:
                    break
            if len(tplus) < 1:
                minus.append(tminus.popleft())
            elif len(tminus) < 1:
                minus.pop()
                plus.append(tplus.popleft())
            elif minus[-1] * tminus[0] > plus[-1] * tplus[0]:
                plus.pop()
                minus.append(tminus.popleft())
            else:
                minus.pop()
                plus.append(tplus.popleft())

    ans = 1
    while plus:
        ans *= plus.popleft()
        ans %= MOD
    while minus:
        ans *= minus.popleft()
        ans %= MOD

    print(ans)

Submission status: Wrong Answer

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a=sorted(a)
    a2=[]
    minus=0
    for i in range(n):
        if a[i]<0:
            a2.append([abs(a[i]),1])
            minus+=1
        else:
            a2.append([abs(a[i]),0])
    a2=sorted(a2,reverse=True)
    nowm=0
    count=0
    ans=1
    if n==k or minus==n:
        a=sorted(a,reverse=True)
        for i in range(k):
            ans*=a[i]
            ans=ans%MOD
    else:
        for i in range(n):
            if nowm==0:
                if a2[i][1]==0:
                    ans*=a2[i][0]
                    ans=ans%MOD
                else:
                    if minus-nowm>=1 and count<k-1:
                        ans *= a2[i][0]
                        ans = ans % MOD
                    else:
                        continue
            else:
                if a2[i][1]==1:
                    ans *= a2[i][0]
                    ans = ans % MOD
                else:
                    if count < k - 1:
                        ans *= a2[i][0]
                        ans = ans % MOD
                    else:
                        continue
            if count>=k:
                break
    print(ans)




if __name__ == "__main__":

    main()

Submission status: Wrong Answer

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

p_list = []
n_list = []
z_count = 0

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

p_list.sort()
n_list.sort()

#print(p_list)
#print(n_list)

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

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,K=map(int,input().split())

A=list(map(int,input().split()))
mod=10**9+7
Am=[-i for i in A if i<0]
Ap=[i for i in A if i>=0]

Am.sort()
Ap.sort()
Am=deque(Am)
Ap=deque(Ap)



if N==K:
    c=1
    for a in A:
        c*=a
        c%=mod

elif len(Ap)==0 and K%2:
    c=1
    while K :
        c*=Am.popleft()

        K-=1

        c%=mod
    c=-c
    c%=mod
    #print("unko")

else:
    exit()
    #print(unko)
    c=1
    h=0
    a="unko"
    b="unko"
    while K and (Am or Ap) :
        if Am and Ap:
            if Am[-1]>Ap[-1]:

                a=Am.pop()
                c*=a
                h+=1
            else:

                b=Ap.pop()
                c*=b

        elif Am:
            a=Am.pop()
            c*=a
            h+=1
        elif Ap:
            b=Ap.pop()
            c*=b
        K-=1
        c%=mod

    if h%2:
        if Am and Ap and a!="unko" and b!="unko":
            if Am[-1]*a>Ap[-1]*b:
                a=Am.pop()
                c*=a
                c*=pow(b,mod-2,mod)
            else:
                b=Ap.pop()
                c*=b
                c*=pow(a,mod-2,mod)
        if Am:
            a=Am.pop()
            c*=a
            c*=pow(b,mod-2,mod)
        else:
            b=Ap.pop()
            c*=b
            c*=pow(a,mod-2,mod)


print(c%mod)

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))
ans=1
#因数のうちの最も絶対の小さい正と負の数
plus1=-1
minus1=-1
for i in range(k):
    ans*=a[i]
    if a[i]>=0:
        plus1=i
    else:
        minus1=i
#因数に含まれなっかた数のうち最も絶対値の大きい正と負に数
plus2=-1
for i in range(k,n):
    if a[i]>=0:
        plus2=i
        break
minus2=-1
for i in range(k,n):
    if a[i]<0:
        minus2=i
        break
if ans>=0:
    print(ans)
#負の場合
else:
    if (plus2>0 and minus1>0) or (minus2>0 and plus1>0):
        ans1=-1
        ans2=-1
        if plus2>0 and minus1>0:
            ans1=ans*a[plus2]//a[minus1]
        if minus2>0 and plus1>0:
            ans2=ans*a[minus2]//a[plus1]
        print(max(ans1,ans2))
    else:
        ans=1
        for i in range(0,k):
            ans*=a[-1-i]
        print(ans%(10**9+7))

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))
mod = 10**9+7
nega = 0
posi = 0
zero = 0
for i in range(n):
    if a[i] > 0:
        posi += 1
    elif a[i] == 0:
        zero += 1
    else:
        nega += 1

if n == k:
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod
    if nega%2 == 1:
        ans *= -1

elif posi == 0:

    if k % 2 == 0:
        ans = 1
        for i in range(k):
            ans *= abs(a[i])
            ans %= mod

    else:
        if zero > 0:
            ans = 0
        else:
            a.reverse()
            ans = 1
            for i in range(k):
                ans *= abs(a[i])
                ans %= mod

            ans *= -1


else:
    posi = 0
    nega = 0
    zero = 0
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod

    for i in range(k):
        if a[i] > 0:
            posi += 1
        elif a[i] < 0:
            nega += 1
        else:
            zero += 1

    if zero > 0:
        ans = 0

    elif nega % 2 != 0:
        minposi = 0
        minnega = 0
        for i in range(k-1, -1, -1):
            if a[i] > 0:
                if minposi == 0:
                    minposi = a[i]
            else:
                if minnega == 0:
                    minnega = a[i]

        maxposi = 0
        maxnega = 0
        for i in range(k, n):
            if a[i] > 0:
                if maxposi == 0:
                    maxposi = a[i]
            else:
                if maxnega == 0:
                    maxnega = a[i]


        if abs(minposi*maxposi) < abs(minnega*maxnega):
            ans *= pow(abs(minposi), mod-2, mod)
            ans *= abs(maxnega)
        elif abs(minposi*maxposi) == abs(minnega*maxnega):
            pp
        else:
            ans *= pow(abs(minnega), mod-2, mod)
            ans *= abs(maxposi)



print(ans % mod)