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:
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

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

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

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

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


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


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

def ri():
    return int(input())

def rl():
    return list(map(int, input().split()))


def solve():
    n, k = rl()
    A = rl()

    mod = 10**9 + 7
    pos = []
    neg = []
    z = 0

    for a in A:
        if a == 0:
            z += 1
        elif a > 0:
            pos.append(a)
        else:
            neg.append(a)

    if z >= n - k + 1:
        return 0

    pos.sort(reverse=True)
    neg.sort()
    if len(pos) == 0:
        if k % 2 == 0:
            ans = 1
            for i in range(k):
                ans *= neg[i]
            return ans
        else:
            if z > 0:
                return 0
            else:
                ans = 1
                taken = 0
                for i in range(len(neg) - 1, -1, -1):
                    # print ('taking', neg[i])
                    taken += 1
                    ans *= neg[i]
                    if taken == k:
                        break
                return ans

    ans = 1

    taken  = 0
    i, j = 0, 0
    while taken < k and i < len(pos) and j < len(neg):
        taken += 1
        if abs(pos[i]) >= abs(neg[j]):
            ans *= pos[i]
            i += 1
        else:
            ans *= neg[j]
            j += 1

    if taken < k:
        while i < len(pos) and taken < k:
            ans *= pos[i]
            i += 1
        while j < len(neg) and taken < k:
            ans *= neg[j]
            j += 1

    if ans > 0:
        return (ans)
        return

    if i < len(pos) and j < len(neg):
        a1 = ans * neg[j+1] // pos[i]
        a2 = ans * pos[i+1] // neg[j]
        return (max(a1, a2))

    elif i < len(pos):
        return (ans * pos[i+1] // neg[j])

    elif j < len(neg):
        return (ans * neg[j+1] // pos[i])

    elif z > 0:
        return (0)

    else:
        return (ans) # k == n





mode = 's'

if mode == 'T':
    t = ri()
    for i in range(t):
        print (solve() % (10**9 + 7))
else:
    print (solve() % (10**9 + 7))

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
import math
A = list(map(int,input().split()))
flag = 0
if 0 in A:
    flag = 1
A.sort()
plus = list(filter(lambda x:x>0, A))[::-1]
plus = list(map(lambda x:math.log(x,1000000),plus ))
from itertools import accumulate
acc_plu = [0] +  list(accumulate(plus))
minu = filter(lambda x:x<0, A)
minu = list(map(lambda x:math.log(-x,1000000),minu))
acc_min = [0] +  list(accumulate(minu))


if K % 2 == 0 : num = K // 2 + 1
else: num = (K + 1) // 2 
cand = []
x = K
y = 0
MOD = 10**9 +7
for i in range(num):
    try:
        cand.append((acc_plu[x] +  acc_min[y],x ,y ))
    except: pass
    x -= 2 
    y += 2

ans = 1
if cand == []:
    if flag:
        print(0)
        exit()
    cnt = 0
    minu = list(filter(lambda x:x<0, A))
    for x in minu[::-1]:
        if cnt == K:break
        ans *= x
        ans %= MOD
        cnt += 1
    print(ans)
else:
    cand = sorted(cand)
    plus = list(filter(lambda x:x>0, A))[::-1]
    minu = list(filter(lambda x:x<0, A))
    c = cand[0]
    ans = 1
    for i in range(c[1]):
        ans *= plus[i]
        ans %= MOD
    for i in range(c[2]):
        ans *= minu[i]
        ans %= MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

def rl():
    return list(map(int, input().split()))


def solve():
    n, k = rl()
    A = rl()

    mod = 10**9 + 7
    pos = []
    neg = []
    z = 0

    for a in A:
        if a == 0:
            z += 1
        elif a > 0:
            pos.append(a)
        else:
            neg.append(a)

    if z >= n - k + 1:
        return 0

    pos.sort(reverse=True)
    neg.sort()
    if len(pos) == 0:
        if k % 2 == 0:
            ans = 1
            for i in range(k):
                ans *= neg[i]
            return ans
        else:
            if z > 0:
                return 0
            else:
                ans = 1
                taken = 0
                for i in range(len(neg) - 1, -1, -1):
                    # print ('taking', neg[i])
                    taken += 1
                    ans *= neg[i]
                    if taken == k:
                        break
                return ans

    ans = 1

    taken  = 0
    i, j = 0, 0
    while taken < k and i < len(pos) and j < len(neg):
        taken += 1
        if abs(pos[i]) >= abs(neg[j]):
            ans *= pos[i]
            i += 1
        else:
            ans *= neg[j]
            j += 1

    if taken < k:
        while i < len(pos) and taken < k:
            ans *= pos[i]
            i += 1
        while j < len(neg) and taken < k:
            ans *= neg[j]
            j += 1

    if ans > 0:
        return (ans)
        return

    if i < len(pos) and j < len(neg):
        a1 = ans * neg[j+1] // pos[i]
        a2 = ans * pos[i+1] // neg[j]
        return (max(a1, a2))

    elif i < len(pos):
        return (ans * pos[i+1] // neg[j])

    elif j < len(neg):
        return (ans * neg[j+1] // pos[i])

    elif z > 0:
        return (0)

    else:
        return (ans) # k == n





mode = 's'

if mode == 'T':
    t = ri()
    for i in range(t):
        print (solve() % (10**9 + 7))
else:
    print (solve() % (10**9 + 7))

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N,K = LI()
    A = LI()

    ans = 1
    ma = max(A)
    if ma <= 0 and K % 2:
        # 最大値が0以下でKが奇数の場合
        x = sorted(A,reverse=True)
        # 大きいほうからK個の積
        for i in range(K):
            ans = (ans * A[i]) % MOD
        print(ans)
        return

    # 絶対値でソート
    x = sorted(A, key=lambda x: abs(x), reverse=True)
    m = 0
    # 絶対値が大きいほうからK個の積
    for i in range(K):
        ans = (ans * x[i]) % MOD
        if x[i] < 0 :m += 1

    # K==Nか、マイナスが偶数ならそのままリターン
    if K == N or m % 2 == 0:
        print(ans)
        return
    # K+1個目が0なら、0でリターン
    if x[K] == 0:
        print(0)
        return

    # K個目まですべてマイナスなら
    if m == K:
        # K番目とK+1以降の最大値とを入れ替え
        ans = (ans * pow(x[K-1],MOD-2,MOD) * max(x[K:])) % MOD

    else:
        K1 = -1
        for i in range(K+1,N):
            if x[K] * x[i] < 0:
                K1 = i
                break

        f1 = 0.0
        f2 = 0.0
        i0 = -1
        i1 = -1
        for i in range(K-1,-1,-1):
            if x[i] * x[K] < 0:
                i0 = i
                f1 = x[K] / x[i]
                break

        if K1 >= 0:
            for i in range(K-1,-1,-1):
                if x[i] * x[K1] < 0:
                    i1 = i
                    f2 = x[K1] / x[i]
                    break

        if abs(f1) >= abs(f2):
            ans = (ans * pow(x[i0],MOD-2,MOD) * x[K]) % MOD
        else:
            ans = (ans * pow(x[i1],MOD-2,MOD) * x[K1]) % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
cnt_plus=0
cnt_zero=0
cnt_minus=0
arr_plus=[]
arr_minus=[]
for i in range(n):
  if arr[i]>0:
    cnt_plus+=1
    arr_plus.append(arr[i])
  elif arr[i]<0:
    cnt_minus+=1
    arr_minus.append(-arr[i])
  else:
    cnt_zero+=1
if cnt_plus+cnt_minus<k:
  print(0)
  exit()
if k==n:
  if cnt_zero!=0:
    print(0)
  else:
    ans=1
    for i in range(cnt_plus):
      ans*=arr_plus[i]
      ans%=mod
    for i in range(cnt_minus):
      ans*=arr_minus[i]
      ans%=mod
    if cnt_minus%2==0:
      print(ans)
    else:
      print((-ans)%mod)
  exit()
if cnt_plus==0 and k%2==1:
  if cnt_zero!=0:
    print(0)
  else:
    arr_minus=sorted(arr_minus)
    tmp=1
    for i in range(k):
      tmp*=arr_minus[i]
      tmp%=mod
    print((-tmp)%mod)
  exit()
else:
  arr_plus=sorted(arr_plus,reverse=True)
  arr_minus=sorted(arr_minus,reverse=True)
  acum_plus=[1]
  for i in range(cnt_plus):
    acum_plus.append((acum_plus[-1]*arr_plus[i])%mod)
  acum_minus=[1]  
  for i in range(cnt_minus):
    acum_minus.append((acum_minus[-1]*arr_minus[i])%mod)  
  if k%2==0:
    ans=0
    for i in range(0,min(k,cnt_plus)+1,2):
      j=k-i
      if cnt_minus<j:
        continue
      ans=max(ans,(acum_plus[i]*acum_minus[j])%mod)
    print(ans)
  else:
    ans=0
    for i in range(1,min(k,cnt_plus)+1,2):
      j=k-i
      if cnt_minus<j:
        continue
      ans=max(ans,(acum_plus[i]*acum_minus[j])%mod)
    print(ans)
  exit()

Submission status: Wrong Answer

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

B=[]
for i in range(n):
    num=A[i]
    B.append([abs(num),num])
B.sort(reverse=True)

C=[]
ans,flag=1,1
for i in range(k):
    num=B[i][1]
    ans *=num
    ans %=mod
    if num<0:flag *=-1
    C.append(num)

if flag==1:print(ans);exit()

plus,negative=0,0
for i in range(k,n):
    num=B[i][1]
    if num>0:
        plus=num
        break
for i in range(k,n):
    num=B[i][1]
    if num<0:
        negative=num
        break

if plus!=0:
    if negative!=0:
        index_x,index_y=-1,-1
        for i in range(k):
            num=C[i]
            if num<0:index_y=i
        for i in range(k):
            num=C[i]
            if num>0:index_x=i
        D,E=copy.deepcopy(C),copy.deepcopy(C)
        ans_1,ans_2=1,1
        if index_y!=-1:
            D[index_y]=plus
            ans_1=1
            for i in range(k):
                ans_1 *=D[i]
                ans_1 %=mod
        if index_x!=-1:
            E[index_x]=negative
            ans_2=1
            for i in range(k):
                ans_2 *=E[i]
                ans_2 %=mod
        print(max(ans_1,ans_2))
    else:
        index=0
        for i in range(k):
            num=C[i]
            if num<0:index=i
        C[index]=plus
        ans=1
        for i in range(k):
            ans *=C[i]
            ans %=mod
        print(ans)
else:
    if negative!=0:
        ans=1
        B.sort()
        for i in range(k):
            ans *=B[i][1]
            ans %=mod
        print(ans)
    else: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()
flg = 1 if max(A) < 0 and k % 2 else 0
X = sorted(A, key=lambda x:abs(x), reverse=False if flg else True)
ans = 1
fflg = 0
t1 = INF
t2 = 0
t_minus = 0
t_plus = 0
for i in range(k):
    ans = ans * abs(X[i]) % mod
    if X[i] < 0:
        fflg ^= 1
        t2 = min(t2, X[i])
        t_minus = 1
    elif X[i] > 0:
        t1 = min(t1, X[i])
        t_plus = 1

if t1 == INF:
    t1 = 1

rem = []
r1 = 1
r2 = 1
rem_minus = 0
rem_plus = 0
for ii in range(k, n):
    if X[ii] > 0:
        rem_plus = 1
        r1 = max(X[ii], r1)
    elif X[ii] < 0:
        rem_minus = 1
        r2 = min(X[ii], r2)

f_ans = -INF
if fflg:
    if rem_minus and t_plus:
        fflg = 0
        f_ans = max(f_ans, -ans * pow(t1, mod - 2, mod) * r2)
    if rem_plus and t_minus:
        fflg = 0
        f_ans = max(f_ans, -ans * pow(t2, mod - 2, mod) * r1)
else:
    f_ans = ans

if fflg:
    f_ans = -ans
print(f_ans % mod)

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()
flg = 1 if max(A) < 0 and k % 2 else 0
X = sorted(A, key=lambda x:abs(x), reverse=False if flg else True)
ans = 1
fflg = 0
t1 = INF
t2 = 0
t_minus = 0
t_plus = 0
for i in range(k):
    ans = ans * abs(X[i]) % mod
    if X[i] < 0:
        fflg ^= 1
        t2 = min(t2, X[i])
        t_minus = 1
    elif X[i] > 0:
        t1 = min(t2, X[i])
        t_plus = 1

if t1 == INF:
    t1 = 1

rem = []
r1 = 1
r2 = 1
rem_minus = 0
rem_plus = 0
for ii in range(k, n):
    if X[ii] > 0:
        rem_plus = 1
        r1 = max(X[ii], r1)
    elif X[ii] < 0:
        rem_minus = 1
        r2 = min(X[ii], r2)

f_ans = -INF
if fflg:
    if rem_minus and t_plus:
        fflg = 0
        f_ans = max(f_ans, -ans * pow(t1, mod - 2, mod) * r2)
    if rem_plus and t_minus:
        fflg = 0
        f_ans = max(f_ans, -ans * pow(t2, mod - 2, mod) * r1)
else:
    f_ans = ans

if fflg:
    f_ans = -ans
print(f_ans % mod)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

readline = sys.stdin.buffer.readline

N, K = map(int, readline().split())
A = np.array(list(map(int, readline().split())), dtype=np.int64)
MOD = 10 ** 9 + 7

B = np.zeros(N, dtype=np.int64)
B[A > 0] = 1
B[A < 0] = -1

# 全部負かつKが奇数のときは場合分け
if len(B[A > 0]) == 0 and K % 2 == 1:
    f = 1
else:
    f = 0

C = np.zeros([2, N], dtype=np.int64)
C[0] = np.abs(A)
C[1] = B

C = C[:, np.argsort(C[0])[::-1]]

ans = 1

# 選んだ中から一番小さい正の数と負の数を記憶
minus_m = 10 ** 9
plus_m = 10 ** 9

if f == 0:
    for i in range(K):
        ans *= C[0, i] * C[1, i]
        ans %= MOD

        if C[1, i] == 1:
            if plus_m > C[0, i]:
                plus_m = C[0, i]

        elif C[1, i] == -1:
            if minus_m > C[0, i]:
                minus_m = C[0, i]

    if ans < 0:
        mm = 0
        MM = 0
        q = C[:, K:]
        p = [q[1] == 1]
        pp = q[p]
        MM = np.max(pp)

        q = C[:, K:]
        p = [q[1] == -1]
        pp = q[p]
        mm = np.max(pp)

        if plus_m * MM > minus_m * mm:
            ans = ans // plus_m
            ans *= MM
        else:
            ans = ans // minus_m
            ans *= mm

else:
    C = C[0][::-1]
    for i in range(K):
        ans *= C[i]

    ans = -ans


print(ans % MOD)

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()
flg = 1 if max(A) < 0 and k % 2 else 0
X = sorted(A, key=lambda x:abs(x), reverse=False if flg else True)
ans = 1
fflg = 0
t1 = INF
t2 = 0
t_minus = 0
t_plus = 0
for i in range(k):
    ans = ans * abs(X[i]) % mod
    if X[i] < 0:
        fflg ^= 1
        t2 = min(t2, X[i])
        t_minus = 1
    elif X[i] > 0:
        t1 = min(t2, X[i])
        t_plus = 1

if t1 == INF:
    t1 = 1

rem = []
r1 = 1
r2 = 1
rem_minus = 0
rem_plus = 0
for ii in range(k, n):
    if X[ii] > 0:
        rem_plus = 1
        r1 = max(X[ii], r1)
    elif X[ii] < 0:
        rem_minus = 1
        r2 = min(X[ii], r2)

f_ans = -INF
if fflg:
    if rem_minus and t_plus:
        fflg = 0
        f_ans = max(f_ans, -ans * pow(t1, mod - 2, mod) * r2)
    if rem_plus and t_minus:
        fflg = 0
        f_ans = max(f_ans, -ans * pow(t2, mod - 2, mod) * r1)

if fflg:
    f_ans = -ans
print(f_ans % mod)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
import math
A = list(map(int,input().split()))
flag = 0
if 0 in A:
    flag = 1
A.sort()
plus = list(filter(lambda x:x>0, A))[::-1]
plus = list(map(lambda x:math.log(x),plus ))
from itertools import accumulate
acc_plu = [0] +  list(accumulate(plus))
minu = filter(lambda x:x<0, A)
minu = list(map(lambda x:math.log(-x),minu))
acc_min = [0] +  list(accumulate(minu))


if K % 2 == 0 : num = K // 2 + 1
else: num = (K + 1) // 2 
cand = []
x = K
y = 0
MOD = 10**9 +7
for i in range(num):
    try:
        cand.append((acc_plu[x] +  acc_min[y],x ,y ))
    except: pass
    x -= 2 
    y += 2


ans = 1
if cand == []:
    if flag:
        print(0)
        exit()
    cnt = 0
    minu = list(filter(lambda x:x<0, A))
    for x in minu[::-1]:
        if cnt == K:break
        ans *= x
        ans %= MOD
        cnt += 1
    print(ans)
else:
    cand = sorted(cand)[::-1]
    plus = list(filter(lambda x:x>0, A))[::-1]
    minu = list(filter(lambda x:x<0, A))
    c = cand[0]
    for i in range(c[1]):
        ans *= plus[i]
        ans %= MOD
    for i in range(c[2]):
        ans *= minu[i]
        ans %= MOD
    if flag:
        print(max(ans,0))
    else:
        print(ans)

Submission status: Wrong Answer

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

B=[]
for i in range(n):
    num=A[i]
    B.append([abs(num),num])
B.sort(reverse=True)

C=[]
ans,flag=1,1
for i in range(k):
    num=B[i][1]
    ans *=num
    ans %=mod
    if num<0:flag *=-1
    C.append(num)
if flag==1:print(ans);exit()

plus,negative=0,0
for i in range(k,n):
    num=B[i][1]
    if num>0:
        plus=num
        break
for i in range(k,n):
    num=B[i][1]
    if num<0:
        negative=num
        break

if plus!=0:
    if negative!=0:
        index_x,index_y=0,0
        for i in range(k):
            num=C[i]
            if num<0:index_y=i
        for i in range(k):
            num=C[i]
            if num>0:index_x=i
        D,E=copy.deepcopy(C),copy.deepcopy(C)
        D[index_y]=plus
        E[index_x]=negative
        ans_1=1
        for i in range(k):
            ans_1 *=D[i]
            ans_1 %=mod
        ans_2=1
        for i in range(k):
            ans_2 *=E[i]
            ans_2 %=mod
        print(max(ans_1,ans_2))
    else:
        index=0
        for i in range(k):
            num=C[i]
            if num<0:index=i
        C[index]=plus
        ans=1
        for i in range(k):
            ans *=C[i]
            ans %=mod
        print(ans)
else:
    if negative!=0:
        ans=1
        B.sort()
        for i in range(k):
            ans *=B[i][1]
            ans %=mod
        print(ans)
    else: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()
flg = 1 if max(A) < 0 and k % 2 else 0
X = sorted(A, key=lambda x:abs(x), reverse=False if flg else True)
ans = 1
fflg = 0
t1 = INF
t2 = 1
t_minus = 0
t_plus = 0
for i in range(k):
    ans = ans * abs(X[i]) % mod
    if X[i] < 0:
        fflg ^= 1
        t2 = min(t2, X[i])
        t_minus = 1
    elif X[i] > 0:
        t1 = min(t2, X[i])
        t_plus = 1

if t1 == INF:
    t1 = 1

rem = []
r1 = 1
r2 = 1
rem_minus = 0
rem_plus = 0
for ii in range(k, n):
    if X[ii] > 0:
        rem_plus = 1
        r1 = max(X[ii], r1)
    elif X[ii] < 0:
        rem_minus = 1
        r2 = min(X[ii], r2)


if fflg and ((rem_minus and t_plus) or (rem_plus and t_minus)):
    fflg ^= 1
    if r1 / t2 > r2 / t1:
        ans = ans * pow(t2, mod - 2, mod) * r1
    else:
        ans = ans * pow(t1, mod - 2, mod) * r2

if fflg:
    ans = -ans
print(ans % mod)

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()
flg = 1 if max(A) < 0 and k % 2 else 0
X = sorted(A, key=lambda x:abs(x), reverse=False if flg else True)
ans = 1
fflg = 0
t1 = INF
t2 = 1
t_minus = 0
t_plus = 0
for i in range(k):
    ans = ans * abs(X[i]) % mod
    if X[i] < 0:
        fflg ^= 1
        t2 = min(t2, X[i])
        t_minus = 1
    elif X[i] > 0:
        t1 = min(t2, X[i])
        t_plus = 1

if t1 == INF:
    t1 = 1

rem = []
r1 = 1
r2 = 1
rem_minus = 0
rem_plus = 0
for ii in range(k, n):
    if X[ii] > 0:
        rem_plus = 1
        r1 = max(X[ii], r1)
    elif X[ii] < 0:
        rem_minus = 1
        r2 = min(X[ii], r2)


if fflg and ((rem_minus and t_plus) or (rem_plus and t_minus)):
    fflg ^= 1
    if r1 / t2 > r2 / t1:
        ans = ans * pow(t1, mod - 2, mod) * r2
    else:
        ans = ans * pow(t2, mod - 2, mod) * r1

if fflg:
    ans = -ans
print(ans % mod)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

readline = sys.stdin.buffer.readline

N, K = map(int, readline().split())
A = np.array(list(map(int, readline().split())), dtype=np.int64)
MOD = 10 ** 9 + 7

B = np.zeros(N, dtype=np.int64)
B[A > 0] = 1
B[A < 0] = -1

if len(B[A > 0]) == 0 and K % 2 == 1:
    f = 1
else:
    f = 0

C = np.zeros([2, N], dtype=np.int64)
C[0] = np.abs(A)
C[1] = B

C = C[:, np.argsort(C[0])[::-1]]

ans = 1

# 選んだ中から一番小さい正の数と負の数を記憶
minus_m = 10 ** 9
plus_m = 10 ** 9

if f == 0:
    for i in range(K):
        ans *= C[0, i] * C[1, i]
        ans %= MOD

        if C[1, i] == 1:
            if plus_m > C[0, i]:
                plus_m = C[0, i]

        else:
            if minus_m > C[0, i]:
                minus_m = C[0, i]

    if ans < 0:
        mm = 0
        MM = 0
        q = C[:, K:]
        p = q[1] == 1
        pp = q[p]
        MM = np.max(pp)

        q = C[:, K:]
        p = q[1] == -1
        pp = q[p]
        mm = np.max(pp)

        if plus_m * MM > minus_m * mm:
            ans = ans // plus_m
            ans *= MM
        else:
            ans = ans // minus_m
            ans *= mm
else:
    C = C[0][::-1]
    for i in range(K):
        ans *= C[i]

    ans = -ans


print(ans % MOD)

Submission status: Wrong Answer

Solution code:
# Contest No.: ABC173
# Problem No.: E
# Solver:      JEMINI
# Date:        20200705

import sys
import heapq

def main():
    modVal = 10 ** 9 + 7
    n, k = map(int, sys.stdin.readline().split())
    nums = list(map(int, sys.stdin.readline().split()))
    
    if n == k:
        ans = 1
        for i in nums:
            ans *= i % modVal
            ans %= modVal
        print(ans)
        return

    if max(nums) < 0:
        nums.sort()
        ans = 1
        if k % 2:
            for i in range(k):
                ans *= nums[-i - 1] % modVal
                ans %= modVal
        else:
            for i in range(k):
                ans *= nums[i] % modVal
                ans %= modVal
        print(ans)
        return
    
    absNums = []
    zeroCnt = 0
    for i in nums:
        if i == 0:
            zeroCnt += 1
        else:
            absNums.append([abs(i), i])
    absNums.sort()
    
    if len(absNums) < k:
        print(0)
        return

    posOverK = []
    posLessK = []
    negOverK = []
    negLessK = []
    for i in range(k):
        temp = absNums.pop()
        if temp[1] > 0:
            posOverK.append(temp[0])
        else:
            negOverK.append(temp[0])
    while absNums:
        temp = absNums.pop()
        if temp[1] > 0:
            posLessK.append(temp[0])
        else:
            negLessK.append(temp[0])
    
    # all values are abs val
    posOverK.sort()
    posLessK.sort()
    negOverK.sort()
    negLessK.sort()
    ans = 1

    # odd negative numbers
    if len(negOverK) % 2:
        minNeg = None
        minPos = None
        if posOverK:
            minPos = posOverK[0]
        if negOverK:
            minNeg = negOverK[0]

        maxNeg = None
        maxPos = None
        if posLessK:
            maxPos = posLessK[-1]
        if negLessK:
            maxNeg = negLessK[-1]
        
        if (minNeg and maxPos) and (minPos and maxNeg):
            if maxPos / minNeg > maxNeg / minPos:
                negOverK[0] = maxPos
            else:
                posOverK[0] = maxNeg
        elif (not minNeg or not maxPos) and (minPos and maxNeg):
            posOverK[0] = maxNeg
        elif (minNeg and maxPos) and (not minPos or not maxNeg):
            negOverK[0] = maxPos
        elif zeroCnt:
            print(0)
            return
    
    for i in posOverK:
        ans *= i % modVal
        ans = ans % modVal
    for i in negOverK:
        ans *= i % modVal
        ans = ans % modVal
    
    print(ans)
    return

if __name__ == "__main__":
    main()