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:
mod = 1000000007

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

A_des = sorted(A, key=lambda x: abs(x), reverse=True)

res_d = 1
res_a = 1
neg_c = 0
neg = K

for i in range(K):
    if A_des[i] < 0:
        neg_c += 1
        neg = i

pos = neg

if neg_c % 2 == 1 and K < N:
    i = K
    while i < N:
        if A_des[i] >= 0:
            pos = i
            break
        i += 1

res = 1
for i in range(K):
    if i == neg:
        res *= A_des[pos]
    else:
        res *= A_des[i]
    res %= mod

res %= mod
print(res)

Submission status: Wrong Answer

Solution code:
###==================================================
### import
import bisect
#from collections import Counter, deque, defaultdict
#from copy import deepcopy
#from functools import reduce, lru_cache
#from heapq import heappush, heappop
#import itertools
#import math
#import string
import sys
### stdin
def input(): return sys.stdin.readline().rstrip()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip('\n') for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]
### stdout
def OutH(lst, deli=' '): print(deli.join(map(str, lst)))
def OutV(lst): print('\n'.join(map(str, lst)))
### setting
sys.setrecursionlimit(10 ** 6)
### utils
int1 = lambda x: int(x) - 1
### constants
INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)
###---------------------------------------------------

N, K = iInM()
A = iInLH()

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

if N == K:
    ans = 1
    for i in range(K):
        ans = ans * A[i] % MOD
    print(ans)
    exit()
elif len([x for x in A if x < 0]) == N:
    ans = 1
    for i in range(K):
        ans = ans * A[N-1-i] % MOD
    print(ans)
    exit()

ans = 1
n_minus = 0
min_plus = -1
min_minus = 1
for i in range(K):
    ans = ans * A[i] % MOD
    if A[i] > 0:
        min_plus = A[i]
    elif A[i] < 0:
        min_minus = A[i]
        n_minus += 1
    else:
        ans = 0
        print(0)
        exit()
if n_minus % 2 == 0:
    print(ans)
    exit()
else:
    ## K番目以降を探してプラスとマイナスのものを見つけにいく
    next_plus = -1
    next_minus = 1
    for i in range(K, N):
        if A[i] >= 0:
            next_plus = A[i]
            break
    for i in range(K, N):
        if A[i] <= 0:
            next_minus = A[i]
            break
    ## これから数の入れ替えを行う
    if min_plus == -1: ## 初めのK個にplusがない場合
        ans = ans * pow(min_minus, MOD-2, MOD) * next_plus % MOD
    elif min_minus == 1: ## 初めのK個にminusがない場合 ## てかこれそもそもありえない
        ans = ans * pow(min_plus, MOD-2, MOD) * next_minus % MOD
    else: ## 初めのK個にplusもminusもある場合
        ## ここまでで必ずmin_plus>0, min_minus<0, next_plus>=0, next_minus<=0
        if next_plus * min_plus >= next_minus * min_minus:
            ans = ans * pow(min_minus, MOD-2, MOD) * next_plus % MOD
        else:
            ans = ans * pow(min_plus, MOD-2, MOD) * next_minus % MOD
            ans = 1
    #print(min_plus, min_minus, next_plus, next_minus)
    print(ans)

Submission status: Wrong Answer

Solution code:

import sys
import numpy as np

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


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

    MOD = 10 ** 9 + 7

    pos = A[A >= 0]
    neg = A[A < 0]

    flag = False  # 積を正にできるか

    if N == K:
        ans = 1
        for a in A.tolist():
            ans = ans * a % MOD
        print(ans % MOD)
        exit()

    if len(pos) > 0:
        flag = True
    else:
        if K % 2 == 0:
            flag = True

    ans = 1
    if not flag:
        # 積を正にできないとき
        # 絶対値の小さい方からK個とる
        A = np.sort(np.abs(A))
        for i in range(K):
            ans = ans * A[i] % MOD
        ans *= -1
    else:
        # pos = np.sort(pos)
        # neg = neg[::-1]
        if K % 2 == 1:
            # Kが奇数の時
            # 一番大きい偶数を1つとる。
            ans *= pos[-1]
            pos = pos[:-1]

        # pos, neg sort -> 2個ずつペア -> 降順sort -> 上から K//2 個とる
        if len(pos) % 2 == 1:
            pos = pos[1:]
        if len(neg) % 2 == 1:
            neg = neg[:-1]
        newpos = pos[::-1][::2] * pos[::-1][1::2]
        newneg = neg[::2] * neg[1::2]
        pairs = np.concatenate([newpos, newneg])

        pairs = np.sort(pairs)[::-1]
        for i in range(K // 2):
            ans = ans * pairs[i] % MOD

    print(ans % MOD)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
import sys

input = sys.stdin.buffer.readline
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), key=lambda x: abs(x), reverse=True)
MOD = 10**9 + 7

# print(f'{A=}')

if N == K:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

if K % 2 == 1:
    if max(A) < 0:
        ans = 1
        for a in A[::-1][:K]:
            ans *= a
            ans %= MOD
        print(ans)
        exit()

P = 1
for a in A[:K]:
    if a >= 0:
        P *= 1
    else:
        P *= -1
# print(f'{P=}')

if P > 0:
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

# (1) 負の数を 1 つ取り除き、非負の数を 1 つ加える
patern_one = True
plus1, minus1 = 0, 0
for plus1 in A[K:]:
    if plus1 >= 0:
        break
else:
    patern_one = False
for minus1 in A[:K][::-1]:
    if minus1 < 0:
        break
else:
    patern_one = False
# print(f'{plus1=}, {minus1=}, {patern_one=}')

# (2) 正の数を 1 つ取り除き、負の数を 1 つ加える
patern_two = True
plus2, minus2 = 0, 0
for plus2 in A[:K][::-1]:
    if plus2 >= 0:
        break
else:
    patern_two = False
for minus2 in A[K:]:
    if minus2 < 0:
        break
else:
    patern_two = False
# print(f'{plus2=}, {minus2=}, {patern_two=}')


def f1():
    subset = deepcopy(A[:K])
    subset.remove(minus1)
    subset.append(plus1)
    # print(f'{subset=}')
    ans = 1
    for s in subset:
        ans *= s
        ans %= MOD
    return ans


def f2():
    subset = deepcopy(A[:K])
    subset.remove(plus2)
    subset.append(minus2)
    # print(f'{subset=}')
    ans = 1
    for s in subset:
        ans *= s
        ans %= MOD
    return ans


if patern_one and patern_two:
    if abs(plus2 * minus1) < abs(plus1 * minus2):
        # (1)
        ans = f1()
    else:
        # (2)
        ans = f2()
elif patern_one:
    ans = f1()
else:
    ans = f2()
print(ans)

Submission status: Wrong Answer

Solution code:

import sys
import numpy as np

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


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

    MOD = 10 ** 9 + 7

    pos = A[A >= 0]
    neg = A[A < 0]

    flag = False  # 積を正にできるか

    if N == K:
        ans = 1
        for a in A.tolist():
            ans = ans * a % MOD
        print(ans % MOD)
        exit()

    if len(pos) > 0:
        flag = True
    else:
        if K % 2 == 0:
            flag = True

    ans = 1
    if not flag:
        # 積を正にできないとき
        # 絶対値の小さい方からK個とる
        A = np.sort(np.abs(A))
        for i in range(K):
            ans = ans * A[i] % MOD
        ans *= -1
    else:
        # pos = np.sort(pos)
        # neg = neg[::-1]
        if K % 2 == 1:
            # Kが奇数の時
            # 一番大きい偶数を1つとる。
            ans *= pos[0]
            pos = pos[1:]

        # pos, neg sort -> 2個ずつペア -> 降順sort -> 上から K//2 個とる
        if len(pos) % 2 == 1:
            pos = pos[1:]
        if len(neg) % 2 == 1:
            neg = neg[:-1]
        newpos = pos[::-1][::2] * pos[::-1][1::2]
        newneg = neg[::2] * neg[1::2]
        pairs = np.concatenate([newpos, newneg])

        pairs = np.sort(pairs)[::-1]
        for i in range(K // 2):
            ans = ans * pairs[i] % MOD

    print(ans % MOD)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, k = [int(x) for x in input().split()]
l = [int(x) for x in input().split()]
p = list(filter(lambda x: x>=0, l))
n = list(filter(lambda x: x<0, l))
p.sort()
n.sort()
pIndex = len(p)-1
nIndex = len(n)-1
ans = 1

if pIndex>0:
    pp = p[pIndex]*p[pIndex-1]
else:
    pp=-1
    
if nIndex>0:
    np = n[nIndex]*n[nIndex-1]
else:
    np=-1

while(k>0):
    if k>1 and np!=-1:
        k-=2
        if np>pp:
            ans*=np%1000000007
            nIndex-=2
            if nIndex>0:
                np=n[nIndex]*n[nIndex-1]
        else:
            ans*=pp%1000000007
            pIndex-=2
            if pIndex>0:
                pp=p[pIndex]*p[pIndex-1]
    elif pIndex>-1:
        k-=1
        ans*=p[pIndex]%1000000007
        pIndex-=1
        if pIndex>0:
                pp=p[pIndex]*p[pIndex-1]
    else:
        k-=1
        ans*=n[nIndex]%1000000007
        nIndex-=1
        
print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
# WA
import sys
import numpy as np

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


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

    MOD = 10 ** 9 + 7

    pos = A[A >= 0]
    neg = A[A < 0]

    flag = False  # 積を正にできるか

    if N == K:
        ans = 1
        for a in A.tolist():
            ans = ans * a % MOD
        print(ans % MOD)
        exit()

    if len(pos) > 0:
        flag = True
    else:
        if K % 2 == 0:
            flag = True

    ans = 1
    if not flag:
        # 積を正にできないとき
        # 絶対値の小さい方からK個とる
        A = np.sort(np.abs(A))
        for i in range(K):
            ans = ans * A[i] % MOD
        ans *= -1
    else:
        # pos = np.sort(pos)
        neg = neg[::-1]
        if K % 2 == 1:
            # Kが奇数の時
            # 一番大きい偶数を1つとる。
            ans *= pos[0]
            pos = pos[1:]

        # pos, neg sort -> 2個ずつペア -> 降順sort -> 上から K//2 個とる
        if len(pos) % 2 == 1:
            pos = pos[1:]
        if len(neg) % 2 == 1:
            neg = neg[:-1]
        newpos = pos[::-1][::2] * pos[::-1][1::2]
        newneg = neg[::2] * neg[1::2]
        pairs = np.concatenate([newpos, newneg])

        pairs = np.sort(pairs)[::-1]
        for i in range(K // 2):
            ans = ans * pairs[i] % MOD

    print(ans % MOD)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

ze = []
pl,mi = [],[]
for i in range(n):
    if a[i] < 0:
        ze.append((-a[i],1))
        mi.append(a[i])
    else:
        ze.append((a[i],0))
        pl.append(a[i])
        
ze.sort(reverse = True)
pl.sort(reverse = True)
mi.sort()

one = 0
for i in range(k):
    one += ze[i][1]
    
ans = 1
zero = k-one

if one % 2 == 0:
    for i in range(k):
        ans = ans * ze[i][0] % MOD
    print(ans)
        
elif len(pl) == 0:
    for i in range(k):
        ans = ans * mi[n-1-i] % MOD
    print(ans)
        
else:
    if (zero == len(pl) and one == len(mi)) or len(pl) == 0 or len(mi) == 0:
        ak = [zero,one]
    elif (zero != len(pl) and one == len(mi)) or zero == 0:
        ak = [zero+1,one-1]
    elif zero == len(pl) and one != len(mi) or one == 0:
        ak = [zero-1,one+1]
    else:
        if abs(mi[one])/pl[zero-1] >= pl[zero]/abs(mi[one-1]):
            ak = [zero-1,one+1]
        else:
            ak = [zero+1,one-1]
            
    ans = 1
    for i in range(ak[0]):
        ans = ans * pl[i] % MOD
    for i in range(ak[1]):
        ans = ans * mi[i] % MOD
        
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


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

    MOD = 10 ** 9 + 7

    pos = A[A >= 0]
    neg = A[A < 0]

    flag = False  # 積を正にできるか

    if N == K:
        ans = 1
        for a in A.tolist():
            ans = ans * a % MOD
        print(ans % MOD)
        exit()

    if len(pos) > 0:
        flag = True
    else:
        if K % 2 == 0:
            flag = True

    ans = 1
    if not flag:
        # 積を正にできないとき
        # 絶対値の小さい方からK個とる
        A = np.sort(np.abs(A))
        for i in range(K):
            ans = ans * A[i] % MOD
        ans *= -1
    else:
        # pos = np.sort(pos)
        neg = neg[::-1]
        if K % 2 == 1:
            # Kが奇数の時
            # 一番大きい偶数を1つとる。
            ans *= pos[0]
            pos = pos[1:]

        # pos, neg sort -> 2個ずつペア -> 降順sort -> 上から K//2 個とる
        if len(pos) % 2 == 1:
            pos = pos[:-1]
        if len(neg) % 2 == 1:
            neg = neg[:-1]
        newpos = pos[::-1][::2] * pos[::-1][1::2]
        newneg = neg[::2] * neg[1::2]
        pairs = np.concatenate([newpos, newneg])

        pairs = np.sort(pairs)[::-1]
        for i in range(K // 2):
            ans = ans * pairs[i] % MOD

    print(ans % MOD)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq
mod = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a > 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0

if len(P)==0 and K%2 == 1:
    for i in range(len(M)-K,len(M)):
        ans2 = ans2 * M[i] % mod 

else:
    while i < K-1:
        i += 1
        if(len(P)>=2 and len(M)>=2):
            i +=1
            if(P[0]*P[1]<M[0]*M[1]):
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
            else:
                ans2 = ans2*(heapq.heappop(P)*heapq.heappop(P))%mod
        elif len(P)==0:
            if len(M)>=2:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 1
            else:
                ans2 =  ans2*M[-1]%mod
        elif len(M)==0:
            ans2 = -ans2*heapq.heappop(P)%mod
        elif len(M)==1 and len(P)==1:
            ans2 = -ans2*heapq.heappop(P)%mod
        elif len(P)==1:
            if(P[0]<M[0]*M[1]):
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i +=1
            else:
                ans2 = -ans2*heapq.heappop(P)%mod
        elif len(M)==1:
            ans2 = -ans2*heapq.heappop(P)%mod
    if i < K:
        if len(P)>=1:
            ans2 = -ans2*heapq.heappop(P)%mod
        else:
            ans2 = ans2*M[0]%mod


print(ans2)

Submission status: Wrong Answer

Solution code:

INF = 10 ** 9 + 7
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

if K == 1:
    print(a[0])
    exit()

if K == N:
    ans = 1
    for i in a:
        ans *= i
        ans %= INF
    print(ans)
    exit()

if a[0] < 0:
    ans = 1
    if K % 2 == 1:
        for i in range(K):
            ans *= a[i]
            ans %= INF
    else:
        for i in range(K):
            ans *= a[-i - 1]
            ans %= INF
    print(ans)
    exit()

sei = []
hu = []
for i in a:
    if i >= 0:
        sei.append(i)
    else:
        hu.append(i)

seis = []
hus = []
total = []
ans = 1
if K % 2 != 0:
    ans = sei[0] % INF
    for i in range(3, len(sei)):
        seis.append(sei[i] * sei[i - 1] % INF)
else:
    for i in range(1, len(sei)):
        seis.append(sei[i] * sei[i - 1] % INF)
for i in range(1, len(hu)):
    hus.append(hu[i] * hu[i - 1] % INF)

total = seis + hus
total.sort(reverse=True)

for i in range(K // 2):
    ans *= total[i]
    ans %= INF

print(ans)

Submission status: Wrong Answer

Solution code:
###==================================================
### import
import bisect
#from collections import Counter, deque, defaultdict
#from copy import deepcopy
#from functools import reduce, lru_cache
#from heapq import heappush, heappop
#import itertools
#import math
#import string
import sys
### stdin
def input(): return sys.stdin.readline().rstrip()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip('\n') for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]
### stdout
def OutH(lst, deli=' '): print(deli.join(map(str, lst)))
def OutV(lst): print('\n'.join(map(str, lst)))
### setting
sys.setrecursionlimit(10 ** 6)
### utils
int1 = lambda x: int(x) - 1
### constants
INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)
###---------------------------------------------------

N, K = iInM()
A = iInLH()

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

if N == K:
    ans = 1
    for i in range(K):
        ans = ans * A[i] % MOD
    print(ans % MOD)
    exit()
elif len([x for x in A if x < 0]) == N:
    ans = 1
    for i in range(K):
        ans = ans * A[N-1-i] % MOD
    print(ans % MOD)
    exit()

ans = 1
n_minus = 0
min_plus = -1
min_minus = 1
for i in range(K):
    ans = ans * A[i] % MOD
    if A[i] > 0:
        min_plus = A[i]
    elif A[i] < 0:
        min_minus = A[i]
        n_minus += 1
    else:
        ans = 0
        print(0)
        exit()
if n_minus % 2 == 0:
    print(ans % MOD)
    exit()
else:
    ## K番目以降を探してプラスとマイナスのものを見つけにいく
    next_plus = -1
    next_minus = 1
    for i in range(K, N):
        if A[i] >= 0:
            next_plus = A[i]
            break
    for i in range(K, N):
        if A[i] <= 0:
            next_minus = A[i]
            break
    ## これから数の入れ替えを行う
    if min_plus == -1: ## 初めのK個にplusがない場合
        ans = ans * pow(min_minus, MOD-2, MOD) * next_plus % MOD
    elif min_minus == 1: ## 初めのK個にminusがない場合 ## てかこれそもそもありえない
        ans = ans * pow(min_plus, MOD-2, MOD) * next_minus % MOD
    else: ## 初めのK個にplusもminusもある場合
        ## ここまでで必ずmin_plus>0, min_minus<0, next_plus>=0, next_minus<=0
        if next_plus * min_plus >= next_minus * min_minus:
            ans = ans * pow(min_minus, MOD-2, MOD) * next_plus % MOD
        else:
            ans = ans * pow(min_plus, MOD-2, MOD) * next_minus % MOD
    #print(min_plus, min_minus, next_plus, next_minus)
    print(ans % MOD)

Submission status: Wrong Answer

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

ze = []
pl,mi = [],[]
for i in range(n):
    if a[i] < 0:
        ze.append((-a[i],1))
        mi.append(a[i])
    else:
        ze.append((a[i],0))
        pl.append(a[i])
        
ze.sort(reverse = True)
pl.sort(reverse = True)
mi.sort()

one = 0
for i in range(k):
    one += ze[i][1]
    
ans = 1
zero = k-one

if one % 2 == 0:
    for i in range(k):
        ans = ans * ze[i][0] % MOD
    print(ans)
        
elif len(pl) == 0:
    for i in range(k):
        ans = ans * mi[n-1-i] % MOD
    print(ans)
        
else:
    if (zero == len(pl) and one == len(mi)) or one == 0 or zero == 0:
        ak = [zero,one]
    elif (zero != len(pl) and one == len(mi)):
        ak = [zero+1,one-1]
    elif zero == len(pl) and one != len(mi):
        ak = [zero-1,one+1]
    else:
        if abs(mi[one])/pl[zero-1] >= pl[zero]/abs(mi[one-1]):
            ak = [zero-1,one+1]
        else:
            ak = [zero+1,one-1]
            
    ans = 1
    for i in range(ak[0]):
        ans = ans * pl[i] % MOD
    for i in range(ak[1]):
        ans = ans * mi[i] % MOD
        
    print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
mod = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a > 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0

if len(P)==0 and K%2 == 1:
    for i in range(len(M)-K,len(M)):
        ans2 = ans2 * M[i] % mod 

else:
    while i < K-1:
        i += 1
        if(len(P)>=2 and len(M)>=2):
            i +=1
            if(P[0]*P[1]<M[0]*M[1]):
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
            else:
                ans2 = ans2*(heapq.heappop(P)*heapq.heappop(P))%mod
        elif len(P)==0:
                i += 1
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
        elif len(M)==0:
            ans2 = -ans2*heapq.heappop(P)%mod
        elif len(M)==1 and len(P)==1:
            ans2 = -ans2*heapq.heappop(P)%mod
    if i < K:
        if len(P)>=1:
            ans2 = -ans2*heapq.heappop(P)%mod
        else:
            ans2 = ans2*M[-1]%mod

print(ans2)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


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

    MOD = 10 ** 9 + 7

    pos = A[A >= 0]
    neg = A[A < 0]

    flag = False  # 積を正にできるか

    if N == K:
        ans = 1
        for a in A.tolist():
            ans = ans * a % MOD
        print(ans % MOD)
        exit()

    if len(pos) > 0:
        flag = True
    else:
        if K % 2 == 0:
            flag = True

    ans = 1
    if not flag:
        # 積を正にできないとき
        # 絶対値の小さい方からK個とる
        A = np.sort(np.abs(A))
        for i in range(K):
            ans = ans * A[i] % MOD
        ans *= -1
    else:
        # pos = np.sort(pos)
        neg = neg[::-1]
        if K % 2 == 1:
            # Kが奇数の時
            # 一番大きい偶数を1つとる。
            ans *= pos[-1]
            pos = pos[:-1]

        # pos, neg sort -> 2個ずつペア -> 降順sort -> 上から K//2 個とる
        if len(pos) % 2 == 1:
            pos = pos[:-1]
        if len(neg) % 2 == 1:
            neg = neg[:-1]
        newpos = pos[::-1][::2] * pos[::-1][1::2]
        newneg = neg[::2] * neg[1::2]
        pairs = np.concatenate([newpos, newneg])

        pairs = np.sort(pairs)[::-1]
        for i in range(K // 2):
            ans = ans * pairs[i] % MOD

    print(ans % MOD)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

AA = []
for a in A:
    AA.append((a, abs(a)))

AA.sort(key=lambda x: x[1], reverse=True)
ans = 1
if K == N:
    for a, _ in AA:
        ans *= a % M
    print(ans%M)
    exit(0)

if K&1 and all([0>x for x in A]):
    AAA = list(reversed(AA))
    for a in AAA[:K]:
        ans *= a[0] % M
    # print(ans)
    ans %= M
    print(ans)
    exit(0)

for x in range(K):
    ans *= (AA[x][0] % M)
ans %= M
if ans > 0:
    print(ans)
    exit(0)
else:
    #マイナスを抜いて、プラスを足すか、プラスを抜いて、マイナスを入れるか

    ## マイナス抜く
    mans = ans
    for ri in reversed(AA[:K]):
        if ri[0] < 0:
            mans /= ri[0]%M
            break
    for i, _ in AA[K:]:
        if i > 0:
            mans *= i %M
    
    pans = ans
    for ri in reversed(AA[:K]):
        if ri[0] > 0:
            pans /= ri[0]%M
            break

    for i, _ in AA[K:]:
        if i < 0:
            mans *= i %M
    
    if mans > pans:
        ans = mans
    else:
        ans = pans
    
    print(ans)
    exit(0)

Submission status: Wrong Answer

Solution code:
###==================================================
### import
import bisect
#from collections import Counter, deque, defaultdict
#from copy import deepcopy
#from functools import reduce, lru_cache
#from heapq import heappush, heappop
#import itertools
#import math
#import string
import sys
### stdin
def input(): return sys.stdin.readline().rstrip()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip('\n') for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]
### stdout
def OutH(lst, deli=' '): print(deli.join(map(str, lst)))
def OutV(lst): print('\n'.join(map(str, lst)))
### setting
sys.setrecursionlimit(10 ** 6)
### utils
int1 = lambda x: int(x) - 1
### constants
INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)
###---------------------------------------------------

N, K = iInM()
A = iInLH()

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

if N == K:
    ans = 1
    for i in range(K):
        ans = ans * A[i] % MOD
    print(ans)
    exit()
elif len([x for x in A if x < 0]) == N:
    ans = 1
    for i in range(K):
        ans = ans * A[N-1-i] % MOD
    print(ans)
    exit()

ans = 1
n_minus = 0
min_plus = -1
min_minus = 1
for i in range(K):
    ans = ans * A[i] % MOD
    if A[i] > 0:
        min_plus = A[i]
    elif A[i] < 0:
        min_minus = A[i]
        n_minus += 1
    else:
        ans = 0
        print(0)
        exit()
if n_minus % 2 == 0:
    print(ans)
    exit()
else:
    ## K番目以降を探してプラスとマイナスのものを見つけにいく
    next_plus = -1
    next_minus = 1
    for i in range(K, N):
        if A[i] >= 0:
            next_plus = A[i]
            break
    for i in range(K, N):
        if A[i] <= 0:
            next_minus = A[i]
            break
    ## これから数の入れ替えを行う
    if min_plus == -1: ## 初めのK個にplusがない場合
        ans = ans * pow(min_minus, MOD-2, MOD) * next_plus % MOD
    elif min_minus == 1: ## 初めのK個にminusがない場合
        ans = ans * pow(min_plus, MOD-2, MOD) * next_minus % MOD
    else: ## 初めのK個にplusもminusもある場合
        ## ここまでで必ずmin_plus>0, min_minus<0, next_plus>=0, next_minus<=0
        if next_plus * min_plus >= next_minus * min_minus:
            ans = ans * pow(min_minus, MOD-2, MOD) * next_plus % MOD
        else:
            ans = ans * pow(min_plus, MOD-2, MOD) * next_minus % MOD
    #print(min_plus, min_minus, next_plus, next_minus)
    print(ans)

Submission status: Wrong Answer

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

AA = []
for a in A:
    AA.append((a, abs(a)))

AA.sort(key=lambda x: x[1], reverse=True)
ans = 1
if K == N:
    for a, _ in AA:
        ans *= a % M
    print(ans%M)

if K&1 and all([0>x for x in A]):
    AAA = list(reversed(AA))
    for a in AAA[:K]:
        ans *= a[0] % M
    # print(ans)
    ans %= M
    print(ans)
    exit(0)

for x in range(K):
    ans *= (AA[x][0] % M)
ans %= M
if ans > 0:
    print(ans)
    exit(0)
else:
    #マイナスを抜いて、プラスを足すか、プラスを抜いて、マイナスを入れるか

    ## マイナス抜く
    mans = ans
    for ri in reversed(AA[:K]):
        if ri[0] < 0:
            mans /= ri[0]%M
            break
    for i, _ in AA[K:]:
        if i > 0:
            mans *= i %M
    
    pans = ans
    for ri in reversed(AA[:K]):
        if ri[0] > 0:
            pans /= ri[0]%M
            break

    for i, _ in AA[K:]:
        if i < 0:
            mans *= i %M
    
    if mans > pans:
        ans = mans
    else:
        ans = pans
    
    print(ans)
    exit(0)

Submission status: Wrong Answer

Solution code:
import heapq
mod = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a > 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0

if len(P)==0 and K%2 == 1:
    for i in range(len(M)-K,len(M)):
        ans2 = ans2 * M[i] % mod 

else:
    while i < K-1:
        i += 1
        if(len(P)>=2 and len(M)>=2):
            i +=1
            if(P[0]*P[1]<M[0]*M[1]):
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
            else:
                ans2 = ans2*(heapq.heappop(P)*heapq.heappop(P))%mod
        elif len(P)==0:
            if len(M)>=2:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 1
            else:
                ans2 =  ans2*M[-1]%mod
        elif len(M)==0:
            ans2 = -ans2*heapq.heappop(P)%mod
        elif len(M)==1 and len(P)==1:
            ans2 = -ans2*heapq.heappop(P)%mod
        elif len(P)==1:
            if(P[0]<M[0]*M[1]):
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i +=1
            else:
                ans2 = -ans2*heapq.heappop(P)%mod
        elif len(M)==1:
            ans2 = -ans2*heapq.heappop(P)%mod
    if i < K:
        if len(P)>=1:
            ans2 = -ans2*heapq.heappop(P)%mod
        else:
            ans2 = ans2*M[-1]%mod


print(ans2)

Submission status: Wrong Answer

Solution code:
import copy
INF = 10 ** 9 + 7
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

if K == 1:
    print(a[0])
    exit()

if K == N:
    ans = 1
    for i in a:
        ans *= i
        ans %= INF
    print(ans)
    exit()

if a[0] < 0:
    ans = 1
    if K % 2 == 1:
        for i in range(K):
            ans *= a[i]
            ans %= INF
    else:
        for i in range(K):
            ans *= a[-i - 1]
            ans %= INF
    print(ans)
    exit()

sei = []
hu = []
for i in a:
    if i >= 0:
        sei.append(i)
    else:
        hu.append(i)

seis = []
hus = []
total = []
ans = 1
if K % 2 != 0:
    for i in range(3, len(sei)):
        seis.append(sei[i] * sei[i - 1])
        ans = sei[0]
else:
    for i in range(1, len(sei)):
        seis.append(sei[i] * sei[i - 1])
for i in range(1, len(hu)):
    hus.append(hu[i] * hu[i - 1])

total = seis + hus
total.sort(reverse=True)

for i in range(K // 2):
    ans *= total[i]
    ans %= INF

print(ans)