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()
A = sorted(A,key= lambda x:-abs(x))
S = [a//abs(a) if abs(a)!=0 else 0 for a in A]

count_M = 0
last_M = None
last_P = None
for i in range(K):
  if S[i] == 0:
    print(0)
    exit()
  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:
  if last_M:
    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
        print(ans)
        exit()
  if last_P:
    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
        print(ans)
        exit()
  if A[-1] == 0:
    print(0)
    exit()
  else:
    ans = 1
    for i in range(K):
      ans *= A[N-1-i]
      ans %= MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N,K=[int(i) for i in input().split(" ")]
A=[int(i) for i in input().split(" ")]

plus=[]
minus=[]
for a in A:
    if a>0:
        plus.append(a)
    elif a<0:
        minus.append(a)

if len(plus)+len(minus)<K:
    print(0)
    sys.exit(0)

if len(plus)==0:
    minus=sorted(minus,reverse=True)
    retval=1
    for i in minus[:K]:
        retval*=i
    print(retval%(10**9+7))
    sys.exit(0)


plus=sorted(plus,reverse=True)
minus=sorted(minus)

use_minus=min(K, (len(minus)//2)*2)
use_plus=K-use_minus

mul=1
for i in minus[:use_minus]:
    mul*=i
for i in plus[:use_plus]:
    mul*=i
retval=mul
while use_plus<=len(plus)-2 and use_minus>=2:
    use_minus-=2
    mul=mul//minus[use_minus]
    mul=mul//minus[use_minus+1]
    mul*=plus[use_plus]
    mul*=plus[use_plus+1]
    use_plus+=2

print(retval%(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()))
a.sort(key=abs, reverse=True)
s = 0
ps = 0
for i in range(k):
    if a[i] < 0:
        s ^= 1
    else:
        ps = 1
b = a[:k]
b.sort(key=abs)
if s:
    p = -MOD
    for i in range(k, n):
        if a[i] >= 0:
            p = a[i]
            break
    q = MOD
    if ps:
        for i in range(k, n):
            if a[i] <= 0:
                q = a[i]
                break
    x = 0
    for j in range(k):
        if b[j] < 0:
            x = b[j]
            xi = j
            break
    y = 0
    for j in range(k):
        if b[j] > 0:
            y = b[j]
            yi = j
            break
    flg = 1
    if y == 0:
        if p >= 0:
            b[xi] = p
            flg = 0
    else:
        if p * y > q * x:
            b[xi] = p
        else:
            b[yi] = q
        flg = 0
    if flg:
        b = a[-k:]
res = 1
for i in range(k):
    res = res * b[i] % MOD
print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

mod = 10**9+7
N, K = map(int, input().split())
A = list(map(int, input().split()))

Mi = []
for a in A:
    if a != 0:
        Mi.append((abs(a), a//abs(a)))

Mi.sort(reverse=True)

if len(Mi) < K:
    ans = 0
else:
    ans = 1
    seg = 1
    lastinv = -1
    lastpu = -1
    for i in range(K):
        a, iv = Mi[i]
        seg *= iv
        if iv == -1:
            lastinv = a
        else:
            lastpu = a
        ans = ans * a % mod

    if seg == -1:
        fpu = -1
        fmi = -1
        ind = K
        while ind < len(Mi):
            a, iv = Mi[ind]
            ind += 1
            if iv == -1:
                if fmi == -1:
                    fmi = a
                continue
            if fpu == -1:
                fpu = a
        
        if lastpu == -1:
            if fpu != -1:
                ans = ans * fpu * pow(lastinv, mod-2, mod) % mod
            elif 0 in A:
                ans = 0
            else:
                ans = -1
                for i in range(K):
                    ans = ans * Mi[-i-1][0] % mod
        elif fpu == -1 or fmi == -1:
            if fpu == -1 and fmi == -1:
                ans = 0
            elif fpu == -1:
                ans = ans * fmi * pow(lastpu, mod-2, mod) % mod
            else:
                ans = ans * fpu * pow(lastinv, mod-2, mod) % mod
        elif lastpu * fpu > lastinv * fmi:
            ans = ans * fpu * pow(lastinv, mod-2, mod) % mod
        else:
            ans = ans * fmi * pow(lastpu, mod-2, mod) % mod
    
    print(ans % mod)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
A.sort(key=lambda x:-abs(x))
mod=10**9+7

"""
pl=[]
mi=[]
ze=0
for num in A:
    if num>0:
        pl.append(num)
        break
    elif num<0:
        mi.append(num)
        break
    else:
        ze+=1

pl.sort()
mi.sort()

ans=0
if len(pl)+len(mi)<k:
    ans=0
    print(ans)

tab=[]
"""

ans=1
flg=1
for i in range(k-1):
    now=A[i]
    if now <0:
        flg*=-1
    ans=ans*abs(now)%mod

#print(ans,flg)
for i in range(k-1,n):
    now=A[i]
    if now >=0:
        lasflg=1
    else:
        lasflg=-1
    if flg*lasflg==1:
        print(ans*abs(now)%mod)
        break
else:
    ans=1
    for i in range(k):
        ans=ans*A[n-1-i]%mod
    print(ans,"!")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


mod = 10 ** 9 + 7

n, k = LI()
A = LI()
A = [[abs(a), a] for a in A]
ret = 1
flg = 0
fflg = 0
z_flg = 0
A.sort(reverse=True)
for i in range(n):
    if A[i][1] >= 0:
        flg = 1
    if A[i][1] == 0:
        z_flg = 1

if flg == 0:
    A.reverse()


ret = 1
abs_max_minus = INF
minus_flg1 = 0
plus_flg1 = 0
minus_flg2 = 0
plus_flg2 = 0
for i in range(k):
    ret = ret * A[i][0] % mod
    if A[i][1] < 0:
        fflg ^= 1
        abs_max_minus = min(abs_max_minus, A[i][0])
        minus_flg1 = 1
    if A[i][1] > 0:
        plus_flg1 = 1


abs_max_plus_remain = 0
for j in range(k, n):
    if A[j][1] > 0:
        abs_max_plus_remain = max(abs_max_plus_remain, A[j][1])
        plus_flg2 = 1
    elif A[j][1] < 0:
        minus_flg2 = 1


if n == k:
    print(ret)
    exit()

if fflg:
    if (plus_flg1 and minus_flg2) or (minus_flg1 and plus_flg2):
        ret //= abs_max_minus
        ret *= abs_max_plus_remain
        fflg ^= 1

if fflg and z_flg:
    print(0)
else:
    if fflg:
        ret = -ret
    print(ret % mod)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)



@mt
def slv(N, K, A):
    pa = [a for a in A if a > 0]
    na = [-a for a in A if a < 0]
    if len(pa) + len(na) < K:
        return 0

    M = 10**9+7

    if K - len(pa) <= 0 or (K - len(pa)) % 2 == 0:
        # positive
        pa.sort()
        na.sort()
        ans = 1
        if K % 2 == 1:
            ans *= pa.pop()
            K -= 1
        for _ in range(K//2):
            if len(pa) >= 2 and len(na) >= 2:
                if pa[-1] * pa[-2] > na[-1] * na[-2]:
                    ans *= pa[-1] * pa[-2]
                    pa.pop()
                    pa.pop()
                else:
                    ans *= na[-1] * na[-2]
                    na.pop()
                    na.pop()
            elif len(pa) >= 2:
                ans *= pa[-1] * pa[-2]
                pa.pop()
                pa.pop()
            else:
                ans *= na[-1] * na[-2]
                na.pop()
                na.pop()
            ans %= M

    else:
        # negative
        pa.sort(reverse=True)
        na.sort(reverse=True)
        ans = 1
        for _ in range(K):
            if pa and na:
                if pa < na:
                    ans *= pa[-1]
                    pa.pop()
                else:
                    ans *= -na[-1]
                    na.pop()
            elif pa:
                ans *= pa[-1]
                pa.pop()
            else:
                ans *= -na[-1]
                na.pop()
            ans %= M

    return ans


def main():
    N, K = read_int_n()
    A = read_int_n()
    print(slv(N, K, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

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

    A.sort(key=lambda a: abs(a), reverse=True)
    A_pos = []
    A_neg = []
    for a in A:
        if a >= 0:
            A_pos.append(a)
        else:
            A_neg.append(-a)
    A_pos.sort(reverse=True)
    A_neg.sort(reverse=True)

    if len(A_pos) == 0 and K&1:
        ans = 1
        A_neg.reverse()
        for i in range(K):
            ans = (ans * A_neg[i])%mod
        print((-ans)%mod)
        exit()

    if len(A_pos) < K:
        A_pos.extend([0] * (K - len(A_pos)))
    ii = 0
    for i in range(len(A_neg) // 2):
        if i == K//2:
            break
        if A_pos[-i*2-1] * A_pos[-i*2-2] > A_neg[i*2] * A_neg[i*2+1]:
            break
        ii = (i+1) * 2

    ans = 1
    cnt = 0
    for i in range(ii):
        ans = (ans * A_neg[i])%mod
        cnt += 1
    if cnt < K:
        for i in range(len(A_pos)):
            ans = (ans * A_pos[i])%mod
            cnt += 1
            if cnt == K:
                break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations
import numpy as np

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

n_c = list(combinations(a,k))
p = np.prod(n_c,axis=1)

print(max(p) % (10**9+7))

Submission status: Wrong Answer

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

mod = 10**9 + 7

A.sort(key = lambda x:abs(x),reverse = True)
ans = 1
last = -1
lastp = -1
cnt = 0
for a in A:
    if a >= 0:break
else:
    if k&1:
        for i in range(k):
            ans *= A[n-i-1]
            ans %= mod
    else:
        for i in range(k):
            ans *= A[i]
            ans %= mod
    print(ans)
    exit()
for i in range(k):
    ans *= A[i]
    ans %= mod
    if A[i] < 0:
        last = i
        cnt += 1
    if A[i] > 0:
        lastp = i
if n == k:
    print(ans%mod)
    exit()
if cnt&1:
    first = 0
    firstp = 0
    for a in A[k:]:
        if a > 0 and firstp == 0:
            firstp = a
        if a < 0 and first == 0:
            first = a
    if first == 0 and firstp == 0:
        ans = 0
    elif first == 0 or lastp == -1:
        ans *= pow(A[last],mod-2,mod)*firstp%mod
        ans %= mod
    elif firstp == 0:
        ans *= pow(A[lastp],mod-2,mod)*first%mod
    else:
        if A[lastp]*firstp <= A[last]*first:
            ans *= pow(A[lastp],mod-2,mod)*first%mod
            ans %= mod
        else:
            ans *= pow(A[last],mod-2,mod)*last%mod
            ans %= mod
print(ans%mod)

Submission status: Wrong Answer

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

P = []
M = []
for i in A:
  if i < 0:
    M.append(abs(i))
  if i > 0:
    P.append(i)

if len(M) + len(P) < K:
  print(0)
  exit()
elif len(M) + len(P) == K:
  ans = 1
  for i in M:
    ans = ans * i % MOD
  for i in P:
    ans = ans * i % MOD
  if len(M) % 2 == 1:
    ans *= -1
    ans += MOD
  print(ans)
  exit()

M.sort(reverse = True)
P.sort(reverse = True)

if len(P) == 0:
  ans = 1
  if K % 2 == 0:
    for i in range(K):
      ans = ans * M[i] % MOD
  else:
    for i in range(K):
      ans = ans * M[-1 -i] % MOD
    ans *= -1
    while ans < 0:
      ans += MOD
  print(ans)
else:
  ans = 1
  pn = 0
  mn = 0
  if K % 2 == 1:
    K -= 1
    ans *= P[0]
    pn = 1
  for i in range(K // 2):
    if pn + 2 > len(P):
      ans = ans * M[mn] * M[mn + 1] % MOD
      mn += 2
    elif mn + 2 > len(M):
      ans = ans * P[pn] * P[pn + 1] % MOD
      pn += 2
    else:
      p = P[pn] * P[pn + 1]
      m = M[mn] * M[mn + 1]
      if p > m:
        ans = ans * p % MOD
        pn += 2
      else:
        ans = ans * m % MOD
        mn += 2
  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft



def main():
    n, k = map(int, input().split())
    a = sorted([(abs(i), (1 if i > 0 else -1)) for i in map(int, input().split())], reverse=True)
    if n == k:
        s = 1
        for x in a:
            s = s * x[0] * x[1] % mod
        print(s)
        return
    if len([i for i in a if i[1] == -1]) == n:
        if k % 2 == 0:
            s = 1
            for i in a[:k]:
                s = (s * i[0]) % mod
            print(s)
        else:
            s = 1
            for i in a[-k:]:
                s = (s * i[0]) % mod
            print((-s) % mod)
        return
    s = 1
    c = 1
    for i in range(k):
        s = s * a[i][0] % mod
        c *= a[i][1]
    if c == 1:
        print(s)
        return
    j = 0
    for i in range(k):
        if a[i][1] == -1:
            j = i
    s = (s * inverse(a[j][0])) % mod
    for i in range(k, n):
        if a[i][1] == 1:
            print(s * a[i][0] % mod)
            return

main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
pos = []
neg = []
for v in A:
	if v >= 0: pos.append(v)
	else: neg.append(-v)

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

MOD = 10 ** 9 + 7
ppos = [1] * (len(pos)+1)
pneg = [1] * (len(neg)+1)

for i, v in enumerate(pos):
	ppos[i+1] = ppos[i] * v % MOD
for i, v in enumerate(neg):
	pneg[i+1] = pneg[i] * v % MOD

i = j = 0

while i + j < K:
	if i == len(pos): j += 1
	elif j == len(neg) or pos[i] >= neg[j]: i += 1
	else: j += 1

if j % 2 == 1:
	v = (-1, -1, -1)
	if i and j < len(neg):
		v = (pos[i-1] * neg[j], i-1, j+1)

	if i < len(pos) and j:
		v = max(v, (pos[i] * neg[j-1], i+1, j-1))

	if v[0] == -1:
		X = pos + neg
		X.sort()
		r = 1
		for v in X[:K]: r = r * v % MOD
		print(-r % MOD)
		raise SystemExit

	i, j = v[1:]

r = 1
for x in pos[:i]: r = r * x % MOD
for x in neg[:j]: r = r * x % MOD
print(r)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

mod = 10**9+7
n,k = na()
a = na()
a.sort()

ans = 1

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

s = 0
e = -1

while k > 0:
    if k == 1:
        if a[s] > a[e]:
            ans = ans*a[s]%mod
        else:
            ans = ans*a[e]%mod
        break
    p = a[s]*a[s+1]
    q = a[e]*a[e-1]
    if p > q:
        ans = p%mod*ans%mod
        s+=2
    else:
        ans = q%mod*ans%mod
        e-=2
    k-=2

print(ans)

Submission status: Wrong Answer

Solution code:
from functools import reduce
import operator
def prod(iterable):
    return reduce(operator.mul, iterable, 1)
N,K = map(int,input().split())
LIST = list(map(int, input().split()))
LIST = sorted(LIST)
Sec = prod(LIST[-K:])
print(Sec%((10**9)+7))

Submission status: Wrong Answer

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

if N==K:
    ans=1
    for i in range(N):
        ans=(ans*A[i])%mod
    print(ans)
else:
    neg=[]
    posi=[]
    zero=0
    for i in range(N):
        if A[i]>0:
            posi.append(A[i])
        elif A[i]<0:
            neg.append(-A[i])
        else:
            zero+=1
    if K>N-zero:
        print(0)
    elif len(neg)==N and K%2==1:
        neg.sort()
        ans=1
        for i in range(K):
            ans=(-ans*neg[i])%mod
        print(ans)
    else:
        A.sort(key=lambda x:-abs(x))
        temp=A[:K]
        rest=A[K:]
        check=0
        for i in range(K):
            if temp[i]<0:
                check+=1
        if check%2==0:
            ans=1
            for i in range(K):
                ans=(ans*temp[i])%mod
            print(ans)
        else:
            rest.sort()
            temp.sort()
            #neg->posi
            val1=-1
            val2=-1
            for i in range(K-1):
                if temp[i]<0 and temp[i+1]>0:
                    val1=temp[i]
                    val2=temp[i+1]
                    break
            (abs(val1),rest[-1])
            #posi->neg
            (abs(val2),abs(rest[0]))
            if abs(rest[-1])*abs(val2)>abs(rest[0])*abs(val1):
                ans=1
                for i in range(K):
                    ans=(ans*temp[i])%mod
                ans=(ans*rest[-1])%mod
                ans=(ans*pow(val1,mod-2,mod))%mod
                print(ans)
            else:
                ans=1
                for i in range(K):
                    ans=(ans*temp[i])%mod
                ans=(ans*rest[0])%mod
                ans=(ans*pow(val2,mod-2,mod))%mod
                print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
mn = []
zr = 0
pl = []
t = []
for x in a:
  if x < 0:
    mn.append(-x)
    t.append((-x, 0))
  elif x == 0: zr += 1
  else:
    pl.append(x)
    t.append((x, 1))

if N - zr < K:
  print(0)
  exit(0)

t.sort(reverse = True)
#print(t)
c = 0
res = 1
lpl = -1
for x, cc in t[: K]:
  res *= x
  res %= mod
  c ^= (cc == 0)
  if cc: lpl = x
if c == 0:
  print(res)
  exit(0)
for x, cc in t[K: ]:
  if lpl == -1: break
  if cc == 0:
    res *= pow(lpl, mod - 2, mod)
    res %= mod
    res *= x
    res %= mod
    print(res)
    exit(0)
if zr:
  print(0)
  exit(0)
res = 1
t.reverse()
for x, _ in t[: K]:
  res *= x
  res %= mod
print(-res % mod)

Submission status: Wrong Answer

Solution code:
N, K=map(int,input().split())
A = sorted([int(i) for i in input().split()])
def prod(list):
  a=1
  for i in list:
    a*=i
  return(a)
print(max(prod(A[-K:-1]),prod(A[0:K]))%(10**9+7))

Submission status: Wrong Answer

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

mod = 10**9 + 7

A.sort(key = lambda x:abs(x),reverse = True)
ans = 1
last = -1
lastp = -1
cnt = 0
for a in A:
    if a >= 0:break
else:
    for i in range(k):
        ans *= A[n-i-1]
        ans %= mod
    print(ans)
    exit()
for i in range(k):
    ans *= A[i]
    ans %= mod
    if A[i] < 0:
        last = i
        cnt += 1
    if A[i] > 0:
        lastp = i
if cnt&1:
    first = 0
    firstp = 0
    for a in A[k:]:
        if a > 0 and firstp == 0:
            firstp = a
        if a < 0 and first == 0:
            first = a
    if first == 0 and firstp == 0:
        ans = 0
    elif first == 0 or lastp == -1:
        ans *= pow(A[last],mod-2,mod)*firstp%mod
        ans %= mod
    elif firstp == 0:
        ans *= pow(A[lastp],mod-2,mod)*first%mod
    else:
        if A[lastp]*firstp <= A[last]*first:
            ans *= pow(A[lastp],mod-2,mod)*first%mod
            ans %= mod
        else:
            ans *= pow(A[last],mod-2,mod)*last%mod
            ans %= mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

def main():
    INF = 999999999999999999999999
    MOD = 10**9+7

    n,k,*A = get_all_int()
    A = list(A)

    # 答えが負である条件
    # ・Aが全て負で、Kが奇数
    # ・Aの負数が奇数個かつ0が存在せず、K=N

    # 答えが0である条件
    # ・N-(Aの0の個数) < K

    positives = 0
    zeros = 0
    negatives = 0

    for a in A:
        if a > 0:
            positives += 1
        elif a == 0:
            zeros += 1
        else:
            negatives += 1
    
    if (n-zeros) < k:
        # 答えが負
        print(0)
        exit()
    
    elif (k==n and negatives%2==1  or  n==negatives and k%2==1):
        # 答えが負
        # 絶対値小さい順にK個掛ける
        A.sort(key=lambda a: abs(a))
        ans = 1
        for i in range(k):
            ans =  (ans * A[i]) % MOD
        print(ans)
        exit()

    else:
        # 答えが正
        # 絶対値大きい順にK個掛ける
        A.sort(reverse=True, key=lambda a: abs(a))
        ans = 1
        n_count = 0
        last_n = 0
        for i in range(k):
            ans =  (ans * A[i]) % MOD
            if A[i] < 0:
                n_count += 1
                last_n = a

        # log(ans, n_count, last_n)
        
        # 負数を奇数個選んでいる場合は調整する
        if n_count%2 == 1:
            for i in range(k, n):
                a = A[i]
                if a < 0:
                    ans *= inv(last_n, MOD)
                    ans *= ans
                    break
        print(ans%MOD)
        exit()

main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

    Z = sum(1 if a == 0 else 0 for a in A)
    if Z + K > N:
        print(0)
        return
    P = []
    M = []
    for a in A:
        if a > 0:
            P.append((a,1))
        else:
            M.append(a)
    
    if len(P) == 0:
        M.sort(reverse = True)
        ans = 1
        for i in range(K):
            ans *= M[i]
            ans %= MOD
        print(ans)
        return
        
    M.sort()
    for i in range(0,len(M) - 1,2):
        P.append((M[i]*M[i + 1],2))
    
    P.sort(reverse = True)
    cnt = 0
    i = 0
    ans = 1
    while i < len(P):
        if cnt + P[i][1] <= K:
            cnt += P[i][1]
            ans *= P[i][0]
            ans %= MOD
        i += 1
    
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
mod = 10**9+7

n, k = map(int, input().split())
A = list(map(int, input().split()))
B = []
C = []
s = 0
t = 0
for a in A:
  if a < 0:
    B.append(-a)
    s += 1
  elif a > 0:
    C.append(a)
    t += 1
if s + t < k:
  print(0)
  exit()
if s + t == k:
  if k == n:
    ans = 1
    for a in A:
      ans *= a
      ans %= mod
    print(ans)
  else:
    if s%2:
      print(0)
    else:
      ans = 1
      for a in A:
        ans *= a
        ans %= mod
      print(ans)
  exit()
B.sort(reverse=True)
C.sort(reverse=True)
ans = 1
nb = 0
nc = 0
if t == 0:
  if k%2:
    for b in B[-k:]:
      ans *= b
      ans %= mod
    ans *= -1
    ans %= mod
    print(ans)
  else:
    for b in B[:k]:
      ans *= b
      ans %= mod
    ans %= mod
    print(ans)
  exit()
for _ in range(k):
  if nb >= s:
    ans *= C[nc]
    ans %= mod
  elif nc >= t:
    ans *= B[nb]
    nb += 1
  else:
    if B[nb] > C[nc]:
      ans *= B[nb]
      nb += 1
    else:
      ans *= C[nc]
      nc += 1
    ans %= mod
if nb%2:
  if nb == s:
    ans *= pow(B[-1], mod-2, mod)
    ans %= mod
    ans *= C[nc]
    ans %= mod
    print(ans)
  elif nc == t:
    ans *= B[nb]
    ans %= mod
    ans *= pow(C[-1], mod-2, mod)
    ans %= mod
    print(ans)
  else:
    if nc == 0:
      ans *= pow(B[nb-1], mod-2, mod)
      ans %= mod
      ans *= C[0]
      ans %= mod
      print(ans)
    else:
      if C[nc-1]*C[nc] >= B[nb-1]*B[nb]:
        ans *= pow(B[nb-1], mod-2, mod)
        ans %= mod
        ans *= C[nc]
        ans %= mod
        print(ans)
      else:
        ans *= pow(C[nc-1], mod-2, mod)
        ans %= mod
        ans *= B[nb]
        ans %= mod
        print(ans)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations as comb
n,k=map(int, input().split())
a=list(map(int, input().split()))
p=comb(a,k)
q=0
for i in p :
  t=1
  for j in i :
    t*=j
  if t>q :
    q=t
print(q%10**9+7)