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: Runtime Error

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

MOD = 10**9+7

from collections import deque
m_count = 0
ans = 1
tmp = []
for a in A:
    if a < 0:
        m_count += 1
        
if m_count == N:
    count = 0
    if K % 2 == 0:
        A.sort()
        for a in A:
            ans *= a
            ans %= MOD
            count += 1
            if count >= K:
                break
    else:
        A.sort(reverse = True)
        for a in A:
            ans *= a
            ans %= MOD
            count += 1
            if count >= K:
                break
else:
    A.sort()
    A = deque(A)
    k = 0
    m_in_count = 0
    while k < K:
        if abs(A[0]) >= abs(A[-1]):
            m_in_count += 1
            tmp.append(A[0])
            A.popleft()
        else:
            tmp.append(A[-1])
            A.pop()
        k += 1
    if m_in_count % 2 == 0:
        for i in tmp:
            ans *= i
    else:
        if N == K:
            for i in tmp:
                ans *= i
                ans %= MOD
        else:
            for i in tmp:
                ans *= i
                ans %= MOD
            ans1 = ans*min(A)%MOD
            ans2 = ans*max(A)%MOD
            ans = 0
            for i in tmp:
                ans = max(ans,ans1//i,ans2//i)
            ans %= MOD
            
print(ans)

Submission status: Runtime Error

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

mod = 10 ** 9 + 7
plus = []
zero = []
minus = []
ans = 1

for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
  elif A[k] < 0:
    minus.append(-1 * A[k])
  else:
    zero.append(A[k])
plus.sort(reverse = True)
minus.sort(reverse = True)
lp = len(plus)
lm = len(minus)

if lp == 0 and K % 2 == 1:
  for k in range(K):
    ans = ans * minus[- k - 1] % mod
  ans = -1 * ans % mod  
  print(ans)
  exit()
if lp == 0 and K % 2 == 0:
  for k in range(K):
    ans = ans * minus[k] % mod
  print(ans)
  exit()
if lm == 0:
  for k in range(K):
    ans = ans * plus[k] % mod
  print(ans)
  exit()
if len(zero) + K > N:
  print(0)
  exit()

p = 0
m = 0
for k in range(K):
  if plus[p] >= minus[m]:
    p += 1
    if p == lp:
      m = K - p  
      break
  else:
    m += 1
    if m == lm:
      p = K - m
      break

def main(mp, mm, plus, minus, mod, K):
  p = 0
  m = 0
  ans = 1
  for k in range(K):
    if plus[p] >= minus[m]:
      ans = ans * plus[p] % mod
      p += 1
      if p == mp:
        for j in range(K - p - m):
          ans = ans * minus[m + j] % mod
        break
    else:
      ans = ans * minus[m] % mod
      m += 1
      if m == mm:
        for j in range(K - p - m):
          ans = ans * plus[p + j] % mod
        break  
  print(ans)
  exit()

if m%2 == 0:
  main(lp, lm, plus, minus, mod, K)
else:
  if p == lp:
    if m != lm:
      main(lp-1, lm, plus, minus, mod, K)
    else:
      if len(zero) > 0:
        print(0)
        exit()
      else:
        main(lp, lm, plus, minus, mod, K)
  elif m == lm:
    main(lp, lm-1, plus, minus, mod, K)
  elif p == 0:
    main(lp, lm-1, plus, minus, mod, K)
  else:
    if plus[p] * plus[p-1] > minus[m-1] * minus[m]:
      main(lp, lm-1, plus, minus, mod, K)
    else:
      main(lp-1, lm, plus, minus, mod, K)

Submission status: Runtime Error

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

mod = 10**9 + 7
plus = []
zero = []
minus = []
ans = 1

for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
  elif A[k] < 0:
    minus.append(-1 * A[k])
  else:
    zero.append(A[k])
plus.sort(reverse = True)
minus.sort(reverse = True)

p = 0
m = 0
for k in range(K):
  if plus[p] >= minus[m]:
    p += 1
    if p == len(plus):
      m = K - p  
      break
  else:
    m += 1
    if m == len(minus):
      p = K - m
      break

def main(mp, mm, plus, minus, mod, K):
  p = 0
  m = 0
  ans = 1
  for k in range(K):
    if plus[p] >= minus[m]:
      ans = ans * plus[p] % mod
      p += 1
      if p == mp:
        for j in range(K - p - m):
          ans = ans * minus[m + j] % mod
        m = K - p  
        break
    else:
      ans = ans * minus[m] % mod
      m += 1
      if m == mm:
        for j in range(K - p - m):
          ans = ans * plus[p + j] % mod
        p = K - m
        break  
  print(ans)



if len(zero) + K > N:
  print(0)
  #print('l23')
  exit()

if len(plus) == 0 and K % 2 == 1:
  for k in range(K):
    ans = ans * minus[-k-1] % mod
  ans = -1 * ans % mod  
  print(ans)
  #print('l31')
  exit()

if len(plus) == 0 and K % 2 == 0:
  for k in range(K):
    ans = ans * minus[k] % mod
  print(ans)
  #print('l38')
  exit()

if len(minus) == 0:
  for k in range(K):
    ans = ans * plus[k] % mod
  print(ans)
  #print('l45')
  exit()



if m%2 == 0:
  main(len(plus), len(minus), plus, minus, mod, K)
  #print('l93')
else:
  if p == len(plus) and m != len(minus):
    main(len(plus)-1, len(minus), plus, minus, mod, K)
    #print('l97')
    exit()
  elif p == len(plus) and m == len(minus):
    if len(zero) > 0:
      print(0)
      #print('l102')
    else:
      main(len(plus), len(minus), plus, minus, mod, K)
      #print('l105')
    exit()
  elif p != len(plus) and m == len(minus):
    main(len(plus), len(minus)-1, plus, minus, mod, K)
    #print('l109')
    exit()
  elif p == 0:
    main(len(plus), len(minus)-1, plus, minus, mod, K)
    #print('l113')
    exit()
  else:
    if plus[p] * plus[p-1] > minus[m-1] * minus[m]:
      main(len(plus), len(minus)-1, plus, minus, mod, K)
      #print('l118')
      exit()
    else:
      main(len(plus)-1, len(minus), plus, minus, mod, K)
      #print('l122')
      exit()

Submission status: Runtime Error

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

mod = 10**9 + 7
plus = []
zero = []
minus = []


for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
  elif A[k] < 0:
    minus.append(-1 * A[k])
  else:
    zero.append(A[k])
plus.sort(reverse = True)
minus.sort(reverse = True)

p = 0
m = 0
for k in range(K):
  if plus[p] >= minus[m]:
    p += 1
    if p == len(plus):
      m = K - p  
      break
  else:
    m += 1
    if m == len(minus):
      p = K - m
      break

def main(mp, mm, plus, minus, mod, K):
  p = 0
  m = 0
  ans = 1
  for k in range(K):
    if plus[p] >= minus[m]:
      ans = ans * plus[p] % mod
      p += 1
      if p == mp:
        for j in range(K - p - m):
          ans = ans * minus[m + j] % mod
        m = K - p  
        break
    else:
      ans = ans * minus[m] % mod
      m += 1
      if m == mm:
        for j in range(K - p - m):
          ans = ans * plus[p + j] % mod
        p = K - m
        break  
  print(ans)



if len(zero) + K > N:
  print(0)
  #print('l23')
  exit()

if len(plus) == 0 and K % 2 == 1:
  for k in range(K):
    ans = ans * minus[-k-1] % mod
  ans = -1 * ans % mod  
  print(ans)
  #print('l31')
  exit()

if len(plus) == 0 and K % 2 == 0:
  for k in range(K):
    ans = ans * minus[k] % mod
  print(ans)
  #print('l38')
  exit()

if len(minus) == 0:
  for k in range(K):
    ans = ans * plus[k] % mod
  print(ans)
  #print('l45')
  exit()



if m%2 == 0:
  main(len(plus), len(minus), plus, minus, mod, K)
  #print('l93')
else:
  if p == len(plus) and m != len(minus):
    main(len(plus)-1, len(minus), plus, minus, mod, K)
    #print('l97')
    exit()
  elif p == len(plus) and m == len(minus):
    if len(zero) > 0:
      print(0)
      #print('l102')
    else:
      main(len(plus), len(minus), plus, minus, mod, K)
      #print('l105')
    exit()
  elif p != len(plus) and m == len(minus):
    main(len(plus), len(minus)-1, plus, minus, mod, K)
    #print('l109')
    exit()
  elif p == 0:
    main(len(plus), len(minus)-1, plus, minus, mod, K)
    #print('l113')
    exit()
  else:
    if plus[p] * plus[p-1] > minus[m-1] * minus[m]:
      main(len(plus), len(minus)-1, plus, minus, mod, K)
      #print('l118')
      exit()
    else:
      main(len(plus)-1, len(minus), plus, minus, mod, K)
      #print('l122')
      exit()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N, K = MI()
    A = LI()
    MOD = 1000000007
    
    B = []
    plus = np.array([])
    minus = np.array([])
    zero = 0
    for a in A:
        if a > 0:
            plus = np.append(plus, a)
        elif a < 0:
            minus = np.append(minus, a)
        else:
            zero += 1
        B.append((abs(a), a))

    # 正にできるかどうか
    def can_plus():
        if len(plus) > 0:
            if N == K:
                if len(minus) % 2 == 0:
                    return True
                else:
                    return False
            else:
                return True
        else:
            if K % 2 == 0:
                return True
            else:
                return False

    if can_plus():
        plus = deque(sorted(plus, reverse=True))
        minus = deque(sorted(minus))

        if K % 2 == 1:
            ans = plus.popleft()
        else:
            ans = 1

        double = []
        while len(plus) >= 2:
            double.append(int(plus.popleft() * plus.popleft()))
        while len(minus) >= 2:
            double.append(int(minus.popleft() * minus.popleft()))

        double = sorted(double, reverse=True)
        # print(double)
        for i in range(K//2):
            ans = ans * double[i] % MOD

        print(int(ans))

    else:
        # 絶対値が小さい順に選ぶ
        B = sorted(B, key=lambda x: x[0])
        ans = 1
        for i in range(K):
            ans = ans * B[i][1]
        print(ans % MOD)
        return





if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
#関数リスト
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

n, k = MI()
mylist = LI()
zero = False
if 0 in mylist:
    zero = True
    while 0 in mylist:
        mylist.remove(0)
        k -= 1

temp1 = sorted(mylist, reverse = True)
temp2 = sorted(mylist)
mod = int(1.0e9 + 7)
start = 1
for i in range(k):
    start *= temp1[i]
temp = start
for i in range(k):
    s = temp1[k-1-i]
    r = temp2[i]
    temp = temp * r / s
    start = max(start, temp)

if len(mylist) == k and zero:
    start = 0
elif zero:
    start = max(start, 0)

print(int(start % mod))

Submission status: Runtime Error

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

import sys
m_count = 0
ans = 1
tmp = []
for a in A:
    if a < 0:
        m_count += 1
        
if m_count == N:
    if K % 2 == 0:
        A.sort(reverse = True)
        for a in A:
            ans *= -a
    else:
        A,sort()
        for a in A:
            ans *= -a
else:
    A.sort()
    k = 0
    m_in_count = 0
    while k < K:
        if abs(A[0]) >= abs(A[-1]):
            m_in_count += 1
            tmp.append(A[0])
            A.pop(0)
        else:
            tmp.append(A[-1])
            A.pop(-1)
        k += 1
    if m_in_count % 2 == 0:
        for i in tmp:
            ans *= i
    else:
        for i in tmp:
            ans *= i
        A.sort()
        ans1 = ans*A[0]
        ans2 = ans*A[-1]
        ans = 0
        for i in tmp:
            ans = max(ans,ans1//i,ans2//i)
            
print(ans)

Submission status: Runtime Error

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

mod = 10**9 + 7
plus = []
zero = []
minus = []
ans = 1

for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
  elif A[k] < 0:
    minus.append(-1 * A[k])
  else:
    zero.append(A[k])
plus.sort(reverse = True)
minus.sort(reverse = True)


if len(zero) + K > N:
  print(0)
  exit()

if len(plus) == 0 and K % 2 == 1:
  for k in range(K):
    ans = ans * minus[-k-1] % mod
  ans = -1 * ans % mod  
  print(ans)
  exit()

if len(plus) == 0 and K % 2 == 0:
  for k in range(K):
    ans = ans * minus[k] % mod
  print(ans)
  exit()

if len(minus) == 0:
  for k in range(K):
    ans = ans * plus[k] % mod
  print(ans)
  exit()

p = 0
m = 0
for k in range(K):
  if plus[p] >= minus[m]:
    ans = ans * plus[p] % mod
    p += 1
    if p = len(plus):
      for j in range(K - p - m):
        ans = ans * minus[m + j] % mod
      m = K - p  
      break
  else:
    ans = ans * minus[m] % mod
    m += 1
    if m = len(minus):
      for j in range(K - p - m):
        ans = ans * plus[p + j] % mod
      p = K - m
      break  

if m%2 == 0:
  print(ans)
else:
  if p == len(plus) and m != len(minus):
    ans = ans / plus[p-1] % mod
    ans = ans * minus[m] % mod
    print(ans)
    exit()
  elif p == len(plus) and m == len(minus):
    if len(zero) > 0:
      print(0)
    else:
      print(ans)
    exit()
  elif p != len(plus) and m == len(minus):
    ans = ans / minus[m - 1] % mod
    ans = ans * plus[p] % mod
    print(ans)
    exit()
  elif p == 0:
    ans = ans / minus[m-1] % mod
    ans = ans * plus[p] % mod
    print(ans)
    exit()
  else:
    if plus[p] * plus[p-1] > minus[m-1] * minus[m]:
      ans = ans / minus[m-1] % mod
      ans = ans * plus[p] % mod
      print(ans)
      exit()
    else:
      ans = ans / plus[p-1] % mod
      ans = ans * minus[m] % mod
      print(ans)
      exit()

Submission status: Runtime Error

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

mod = 10**9 + 7
plus = []
zero = []
minus = []
ans = 1

for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
  elif A[k] < 0:
    minus.append(-1 * A[k])
  else:
    zero.append(A[k])
plus.sort(reverse = True)
minus.sort(reverse = True)


if len(zero) + K > N:
  print(0)
  exit()

if len(plus) == 0 and K % 2 == 1:
  for k in range(K):
    ans = ans * minus[-k-1] % mod
  ans = -1 * ans % mod  
  print(ans)
  exit()

if len(plus) == 0 and K % 2 == 0:
  for k in range(K):
    ans = ans * minus[k] % mod
  print(ans)
  exit()

if len(minus) == 0:
  for k in range(K):
    ans = ans * plus[k] % mod
  print(ans)
  exit()

p = 0
m = 0
for k in range(K):
  if plus[p] >= minus[m] and p + 1  <= len(plus):
    ans = ans * plus[p] % mod
    p += 1
    if p >= len(plus):
      for j in range(K - p - m):
        ans = ans * minus[m+j] % mod
      m = K - p  
      break
  else:
    ans = ans * minus[m] % mod
    m += 1
    if m >= len(minus):
      for j in range(K - p - m):
        ans = ans * plus[p+j] % mod
      p = K - m
      break  

if m%2 == 0:
  print(ans)
else:
  if p == len(plus) and m != len(minus):
    ans = ans / plus[p-1] % mod
    ans = ans * minus[m] % mod
    print(ans)
    exit()
  elif p == len(plus) and m == len(minus):
    if len(zero) > 0:
      print(0)
    else:
      print(ans)
    exit()
  elif p != len(plus) and m == len(minus):
    ans = ans / minus[m-1] % mod
    ans = ans * plus[p] % mod
    print(ans)
    exit()
  elif p == 0:
    ans = ans / minus[m-1] % mod
    ans = ans * plus[p] % mod
    print(ans)
    exit()
  else:
    if plus[p] * minus[p-1] > plus[m-1] * minus[m]:
      ans = ans / minus[m-1] % mod
      ans = ans * plus[p] % mod
      print(ans)
      exit()
    else:
      ans = ans / plus[p-1] % mod
      ans = ans * minus[m] % mod
      print(ans)
      exit()

Submission status: Runtime Error

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

if n == 1:exit(print(a[0]%mod))

import bisect, heapq

def est(x,R):
  ans = 1
  for i in range(1, k+1):
    ans *= x[-i]
  return ans

def cr(x,z):
  ans = 1
  if z <= 1:
    #x = x[-(k+1):]
    for i in range(1,k+1):
      ans *= x[-i]
    return est(x, k)
  elif z == n:
    #for i in range(1,k+1):
    if k%2 == 0:
      for i in range(k):
        ans *= x[i]
    else:
      ans =  est(x, k)
    return ans
  else:
    if k*2 < n :x = x[:k+1] + x[-(k+1):]
    cnt = 0
    thr = x[-k]
    while cnt < min(z,k)//2*2:
      f = heapq.heappop(x)
      s = heapq.heappop(x)
      p = f*s
      if p > thr:
        heapq.heappush(x, f*s)
        cnt += 2
        thr = x[-k+cnt//2]
      else:break
    x.sort()
    K = k - cnt//2
    #for i in range(1,K+1):
    #  ans *= x[-i]
    return est(x,K)

a.sort()
z = bisect.bisect(a,0)

print(cr(a,z)%mod)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a=sorted(a,reverse=True)
mod=10**9+7
x=1
y=0
z=n-1
if k%2 == 1:
  q = k//2
  a0 = a[0]
  L = a[x]*a[x+1]
  R = a[z]*a[z-1]
  if L>R:
    for i in range(q):
      a0 *= L
      x += 2
      print(a0%mod)
  else:
    for i in range(q):
      a0 *= R
      z -= 2
      print(a0%mod)
      
else:
  q = k/2
  one = 1
  L = a[y]*a[y+1]
  R = a[z]*a[z-1]
  if L>R:
    for i in range(q):
      one *= L
      y += 2
      print(one%mod)
  else:
    for i in range(q):
      one *= R
      z -=2
      print(one%mod)

Submission status: Runtime Error

Solution code:
import itertools
import heapq
import sys
import functools
import operator
input = sys.stdin.readline
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
comb = itertools.combinations(a,k)  
l = [list(_) for _ in comb]
cmb = cmb(n-1,k)
A = [functools.reduce(operator.mul,l[_]) for _ in range(cmb)] 
l_max = max(A)
waru = 10**9 + 7
print(l_max % waru)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())

numbers = list(map(int, input().split()))
numbers.sort(key=abs, reverse=True)

plus_list = [n for n in numbers if n >= 0]
plus_list.sort(reverse=True)

minus_list = [n for n in numbers if n < 0]
minus_list.sort(reverse=True)

max_mul = 1
if not plus_list and K % 2 != 0:
    for num in minus_list[:K]:
        max_mul *= num
else:
    for num in numbers[:K]:
        max_mul *= num
    if max_mul < 0:
        remain_max_val = max(numbers[K:])
        remain_min_val = min(numbers[K:])
        selected_minus_list = [n for n in numbers[:K] if n < 0]
        if remain_min_val >= 0:
            max_mul = int(max_mul / max(selected_minus_list)) * remain_max_val
        else:
            selected_plus_list = [n for n in numbers[:K] if n >= 0]
            tmp1 = 0
            if selected_plus_list:
                tmp1 = int(max_mul / min(selected_plus_list)) * remain_min_val
            tmp2 = int(max_mul / max(selected_minus_list)) * remain_max_val
            max_mul = max(tmp1, tmp2)
print(max_mul % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
# import sys
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# N, M = map(int, input().split())
# As = list(map(int, input().split()))
# queries = (input() for _ in range(N))

from bisect import bisect_left


def solve():
    N, K = map(int, input().split())

    As = list(map(int, input().split()))

    As.sort()
    index = bisect_left(As, 0)

    # neg = As[:index]
    # pos = As[index:]
    # pos = pos[bisect_left(pos, 1):]
    # pos.sort(reverse=True)
    # print(pos, neg)

    pos = sorted(As, reverse=True)
    ans = 1
    mod = 10 ** 9 + 7

    if N == K:
        for p in pos:
            ans *= p
            ans %= mod
        return ans

    if index == N and K % 2:
        for p in pos[:K]:
            ans *= p
            ans %= mod
        return ans

    pl = 0
    pr = N - 1
    
    if K % 2:
        ans *= pos[pr]
	    pr -= 1

    for i in range(K//2):
        left = pos[pl] * pos[pl+1]
        right = pos[pr] * pos[pr-1]

        if left > right:
            ans *= left
            ans %= mod
            pl += 2
        else:
            ans *= right
            ans %= mod
            pr -= 2

    return ans


def main():
    print(solve())


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

if n == 1:exit(print(a[0]%mod))

import bisect, heapq

def est(x,R):
  ans = 1
  for i in R:
    ans *= x[-i]
  return ans

def cr(x,z):
  ans = 1
  if z <= 1:
    #for i in range(1,k+1):
    #  ans *= x[-i]
    return est(x, range(1,k+1))
  elif z == n:
    for i in range(1,k+1):
      if k%2 == 0:
        ans *= x[i-1]
      else:
        ans *= x[-i]
    return ans
  else:
    if k*2 < n :x = x[:k] + x[-k:]
    cnt = 0
    thr = x[-k]
    while cnt < min(z,k)//2*2:
      f = heapq.heappop(x)
      s = heapq.heappop(x)
      p = f*s
      if p > thr:
        heapq.heappush(x, f*s)
        cnt += 2
        thr = x[-k+cnt//2]
      else:break
    x.sort()
    K = k - cnt//2
    #for i in range(1,K+1):
    #  ans *= x[-i]
    return est(x, range(1,k+1))

a.sort()
z = bisect.bisect(a,0)

print(cr(a,z)%mod)

Submission status: Runtime Error

Solution code:
from functools import reduce
import numpy as np

mod=10**9+7

def mat(list):
    return reduce(lambda a,b: a*b%mod, list)

# def get_position_pn(np_array, K):
#     last_negative = -1
#     last_positive = -1
#     next_negative = -1
#     next_negative = -1
#     for i, tp in enumerate(A[:K]):
#         if tp:
#             last_negative = i
#         elif !tp:
#             last_positive = i
#     for i, tp in enumerate(A[K:]):
#         if tp




N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
A = np.array(sorted(A, key=abs, reverse=True))
A_pn = A < 0
if N == np.count_nonzero(A_pn):
    if K % 2 == 0:
        print(mat(A[:K]))
    else:
        print(mat(A[-K:]))
elif np.count_nonzero(A_pn[:K]) % 2 == 0:
    print(mat(A[:K]))
else:
    negative_all = np.where(A_pn)[0]
    negative_rest = np.count_nonzero(negative_all>=K)
    if negative_rest == 0:
        # 負の数が残っていない
        A[negative_all[-1]] = A[K]
        print(mat(A[:K]))
    elif negative_rest == N-K:
        # 正の数が残っていない
        last_positive = np.where(A_pn[:K]==False)[0][-1]
        A[last_positive] = A[K]
        print(mat(A[:K]))
    elif len(negative_all)-negative_rest==K:
        # 負の数しか選択されていない
        last_negative = negative_all[negative_all<K][-1]
        # last_negative = np.where(negative_all<K)[0][-1]
        next_positive = np.where(A_pn==False)[0][0]
        A[last_negative] = A[next_positive]
        print(mat(A[:K]))
    else:
        last_negative = negative_all[negative_all<K][-1]
        next_negative = negative_all[negative_all>=K][0]
        positive_all = np.where(A_pn==False)[0]
        last_positive = positive_all[positive_all<K][-1]
        next_positive = positive_all[positive_all>=K][0]
        if A[last_negative]*A[next_negative] > A[last_positive]*A[next_positive]:
            A[last_positive] = A[next_negative]
        else:
            A[last_negative] = A[next_positive]
        print(mat(A[:K]))

Submission status: Runtime Error

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

if n == 1:exit(print(a[0]%mod))

import bisect, heapq

def est(x,R):
  ans = 1
  for i in R:
    ans *= x[-i]
  return ans

def cr(x,z):
  ans = 1
  if z <= 1:
    #for i in range(1,k+1):
    #  ans *= x[-i]
    return est(x, range(1,k+1))
  elif z == n:
    for i in range(1,k+1):
      if k%2 == 0:
        ans *= x[i-1]
      else:
        ans *= x[-i]
    return ans
  else:
    cnt = 0
    thr = x[-k]
    while cnt < min(z,k)//2*2:
      f = heapq.heappop(x)
      s = heapq.heappop(x)
      p = f*s
      if p > thr:
        heapq.heappush(x, f*s)
        cnt += 2
        thr = x[-k+cnt//2]
      else:break
    x.sort()
    K = k - cnt//2
    #for i in range(1,K+1):
    #  ans *= x[-i]
    return est(x, range(1,k+1))

a.sort()
z = bisect.bisect(a,0)

print(cr(a,z)%mod)

Submission status: Runtime Error

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

if n == 1:exit(print(a[0]%mod))

import bisect, heapq

def cr(x,z):
  ans = 1
  if z <= 1:
    for i in range(1,k+1):
      ans *= x[-i]
    return ans
  elif z == n:
    for i in range(1,k+1):
      if k%2 == 0:
        ans *= x[i-1]
      else:
        ans *= x[-i]
    return ans
  else:
    cnt = 0
    while cnt < min(z,k)//2*2:
      f = heapq.heappop(x)
      s = heapq.heappop(x)
      p = bisect.bisect(x, f*s)
      if p >= (n-k+cnt//2):
        heapq.heappush(x, f*s)
        cnt += 2
      else:break
    x.sort()
    K = k - cnt//2
    for i in range(1,K+1):
      ans *= x[-i]
    return ans

a.sort()
z = bisect.bisect(a,0)

print(cr(a,z)%mod)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n,k=map(int,input().split())
alist=list(map(int,input().split()))
plalist,mailist=[],[]
p=10**9+7
for i in alist:
  if i>0:
    plalist.append(i)
  else:
    mailist.append(i)
#大きい順
dplalist=sorted(plalist,reverse=True)
#絶対値が大きい順
dmailist=sorted(mailist)
total=1
cnt,i,j=0,0,0
if dplalist==[]:
  for i in range(k):
    i+=1
    val=dmailist[n-i]
    total*=val
    if not i%2==0:
      total=int(total%p)
elif len(dmailist)==1 or len(dmailist)==0:
  for i in range(k):
    i+=1
    val=dplalist[n-i]
    total*=val
    total=int(total%p)
else:
  while cnt<k:
    if len(dplalist)==1:
      dplalist.append(1)
    x=dplalist[i]*dplalist[i+1]
    y=dmailist[2*j]*dmailist[2*j+1]
    if x>y or cnt==k-1:
      total*=dplalist[2*i]
      total=int(total%p)
      cnt+=1
      i+=1
    else:
      total*=y
      total=int(total%p)
      cnt+=2
      j+=1
      dmailist.append(1)
print(int(total%p))

Submission status: Runtime Error

Solution code:
import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 1
if max(a)==0:
  print(0)
  exit()
elif max(a)<0 and k%2==1:
  a = sorted(a)[::-1]
  for i in range(k):
    ans *= a[i] % (10**9+7)
    ans %= (10**9+7)
  ans %= (10**9+7)
  print(abs(ans))
  exit()

a_abs = [[a_, abs(a_)] for a_ in a]
a_abs = sorted(a_abs, key=lambda x: -x[-1])

cnt = 0
for i in range(k):
  if a_abs[i][0]<0:
    cnt += 1

if cnt%2==0:
  for i in range(k):
    ans *= a_abs[i][0] % (10**9+7)
    ans %= (10**9+7)
  print(ans)
  exit()
  
p1 = -1
p2 = -1
for i in range(k,-1,-1):
  if p1==-1 and a_abs[i][0] > 0:
    p1 = i
  elif p2==-1 and a_abs[i][0] < 0:
    p2 = i
  elif p1!=-1 and p2!=-1:
    break

p3 = -1
p4 = -1
for i in range(k+1, n):
  if p3==-1 and a_abs[i][0] < 0:
    p3 = i
  elif p4==-1 and a_abs[i][0] > 0:
    p4 = i
  elif p3!=-1 and p4!=-1:
    break

if p3==-1 or p2==-1:
  t1 = -1
else:
  t1 = a_abs[p3][1]*a_abs[p2][1]
if p4==-1 or p1==-1:
  t2 = -1
else:
  t2 = a_abs[p4][1]*a_abs[p1][1]

if t1>t2:
  for i in range(k-1):
    if i==p1:
      continue
    ans *= a_abs[i][0] % (10**9+7)
    ans %= (10**9+7)
  ans *= a_abs[p3][0]
  ans %= (10**9+7)
else:
  for i in range(k-1):
    if i==p2:
      continue
    ans *= a_abs[i][0] % (10**9+7)
    ans %= (10**9+7)
  ans *= a_abs[p4][0]
  ans %= (10**9+7)

print(ans)

Submission status: Runtime Error

Solution code:
import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 1
if max(a)==0:
  print(0)
  exit()
elif max(a)<0 and k%2==1:
  a = sorted(a)[::-1]
  for i in range(k):
    ans *= a[i] % (10**9+7)
    ans %= (10**9+7)
  ans %= (10**9+7)
  print(abs(ans))
  exit()

a_abs = [[a_, abs(a_)] for a_ in a]
a_abs = sorted(a_abs, key=lambda x: -x[-1])

cnt = 0
for i in range(k):
  if a_abs[i][0]<0:
    cnt += 1

if cnt%2==0:
  for i in range(k):
    ans *= a_abs[i][0] % (10**9+7)
    ans %= (10**9+7)
  print(ans)
  exit()
  
p1 = -1
p2 = -1
for i in range(k,-1,-1):
  if p1==-1 and a_abs[i][0] > 0:
    p1 = i
  elif p2==-1 and a_abs[i][0] < 0:
    p2 = i
  elif p1!=-1 and p2!=-1:
    break

p3 = -1
p4 = -1
for i in range(k+1, n):
  if p3==-1 and a_abs[i][0] < 0:
    p3 = i
  elif p4==-1 and a_abs[i][0] > 0:
    p4 = i
  elif p3!=-1 and p4!=-1:
    break

if a_abs[p3][1]*a_abs[p2][1]>a_abs[p4][1]*a_abs[p1][1]:
  for i in range(k-1):
    if i==p1:
      continue
    ans *= a_abs[i][0] % (10**9+7)
    ans %= (10**9+7)
  ans *= a_abs[p3][0]
  ans %= (10**9+7)
else:
  for i in range(k-1):
    if i==p2:
      continue
    ans *= a_abs[i][0] % (10**9+7)
    ans %= (10**9+7)
  ans *= a_abs[p4][0]
  ans %= (10**9+7)

print(ans)

Submission status: Runtime Error

Solution code:
from functools import reduce
import numpy as np

mod=10**9+7

def mat(list):
    return reduce(lambda a,b: a*b%mod, list)


N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
A = np.array(sorted(A, key=abs, reverse=True))
A_pn = A < 0
# print(A_pn)
if N == np.count_nonzero(A_pn):
    if K % 2 == 0:
        print(mat(A[:K]))
    else:
        print(mat(A[-K:]))
elif np.count_nonzero(A_pn[:K]) % 2 == 0:
    print(mat(A[:K]))
else:
    for a in A[K:]:
        if a >= 0:
            last = a
    print(mat(A[:K-1])*last)

Submission status: Runtime Error

Solution code:
from functools import reduce
import numpy as np

mod=10**9+7

def mat(list):
    return reduce(lambda a,b: a*b%mod, list)


N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
A = np.array(sorted(A, key=abs, reverse=True))
A_pn = A < 0
print(A_pn)
if N == np.count_nonzero(A_pn):
    if K % 2 == 0:
        print(mat(A[:K]))
    else:
        print(mat(A[-K:]))
elif np.count_nonzero(A_pn[:K]) % 2 == 0:
    print(mat(A[:K]))
else:
    for a in A[K:]:
        if a >= 0:
            last = a
    print(mat(A[:K-1])*last)