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:
N, K = map(int, input().split())
A = 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:
n,k=map(int, input().split())
a = list(map(int, input().split()))
mod=10**9+7
if n==k:
    ans=1
    for i in range(k):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()
minus=[i for i in a if i<0]
plus=[i for i in a if i>=0]
from collections import deque
minus=deque(sorted(minus))
plus=deque(sorted(plus,reverse=True))

n_minus=len(minus)
n_plus=len(plus)

if n_minus==n:
    ans=1
    if k%2==0:
        for i in range(k):
            ans*=minus.popleft()
            ans+=mod
            ans%=mod
        print(ans)
        exit()
    else:
        for i in range(k):
            ans*=minus.pop()
            ans+=mod
            ans%=mod
        print(ans)
        exit()

cnt_minus=0
cand=deque([])
for i in range(k):
    if not plus or ((plus and minus) and abs(minus[0])>abs(plus[0])):
        cand.append(minus.popleft())
        cnt_minus+=1
    elif not minus or ((plus and minus) and abs(minus[0])<abs(plus[0])):
        cand.append(plus.popleft())
    else:
        if cnt_minus%2==1:
            cand.append(minus.popleft())
            cnt_minus+=1
        else:
            cand.append(plus.popleft())

if cnt_minus%2==0:
    ans=1
    for i in range(k):
        ans*=cand[i]
        ans+=mod
        ans%=mod
    print(ans)
    exit()

if 0 in cand:
    print(0)
    exit()

tmpm,tmpp=None,None

for i in range(k-1,-1,-1):
    if cand[i]<0 and tmpm==None:
        tmpm=cand[i]
    elif cand[i]>=0 and tmpp==None:
        tmpp=cand[i]

#print(tmpm,tmpp)
cand1,cand2=None,None
if tmpm!=None and plus:
    cand1=plus[0]/abs(tmpm)
if tmpp!=None and minus:
    if tmpp!=0:
        cand2=abs(minus[0])/abs(tmpp)
    else:
        cand2=0

if tmpp==0:
    if minus:
        ans=1
        flg=True
        for i in range(k):
            if flg and cand[i]==tmpp:
                flg=False
                continue
            ans*=cand[i]
            ans+=mod
            ans%=mod
        print((ans*minus[0])%mod)
        exit()
elif (cand1!=None and cand2==None) or ((cand1!=None and cand2!=None) and cand1>=cand2):
    ans=1
    flg=True
    for i in range(k):
        if flg and cand[i]==tmpm:
            flg=False
            continue
        ans*=cand[i]
        ans+=mod
        ans%=mod
    print((ans*plus[0])%mod)
    exit()

elif (cand1==None and cand2!=None) or ((cand1!=None and cand2!=None) and cand1<cand2):
    ans=1
    flg=True
    for i in range(k):
        if flg and cand[i]==tmpp:
            flg=False
            continue
        ans*=cand[i]
        ans+=mod
        ans%=mod
    print((ans*minus[0])%mod)
    exit()

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:
mod = 1000000007
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
ans = 1
if A[-1] < 0:
    for i in range(K):
        ans = ans * (A[-i-1]%mod) % mod
else:
    n = 0
    p = -1
    i = K
    while i > 0:
        if i == 1:
            ans = ans * (A[p]%mod) % mod
            i -= 1
        else:
            if A[n]*A[n+1] > A[p]*A[p-1]:
                ans = ans * (A[n]%mod) % mod
                ans = ans * (A[n+1]%mod) % mod
                n += 2
                i -= 2
            else:
                ans = ans * (A[p]%mod) % mod
                p += 1
                i -= 1

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)
    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 >= 0:
            ans = ans * pow(min_minus, MOD-2, MOD) * next_plus % MOD
        else:
            ans = ans * pow(min_plus, MOD-2, MOD) * next_minus % MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int, input().split())
a = list(map(int, input().split()))
mod=10**9+7
if n==k:
    ans=1
    for i in range(k):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()
minus=[i for i in a if i<0]
plus=[i for i in a if i>=0]
from collections import deque
minus=deque(sorted(minus))
plus=deque(sorted(plus,reverse=True))

n_minus=len(minus)
n_plus=len(plus)

if n_minus==n:
    ans=1
    if k%2==0:
        for i in range(k):
            ans*=minus.popleft()
            ans%=mod
        print(ans)
        exit()
    else:
        for i in range(k):
            ans*=minus.pop()
            ans%=mod
        print(ans)
        exit()

cnt_minus=0
cand=deque([])
for i in range(k):
    if not plus or ((plus and minus) and abs(minus[0])>abs(plus[0])):
        cand.append(minus.popleft())
        cnt_minus+=1
    elif not minus or ((plus and minus) and abs(minus[0])<abs(plus[0])):
        cand.append(plus.popleft())
    else:
        if cnt_minus%2==1:
            cand.append(minus.popleft())
            cnt_minus+=1
        else:
            cand.append(plus.popleft())

if cnt_minus%2==0:
    ans=1
    for i in range(k):
        ans*=cand[i]
        ans%=mod
    print(ans)
    exit()

if 0 in cand:
    print(0)
    exit()

tmpm,tmpp=None,None

for i in range(k-1,-1,-1):
    if cand[i]<0 and tmpm==None:
        tmpm=cand[i]
    elif cand[i]>=0 and tmpp==None:
        tmpp=cand[i]

#print(tmpm,tmpp)
cand1,cand2=None,None
if tmpm!=None and plus:
    cand1=plus[0]/abs(tmpm)
if tmpp!=None and minus:
    if tmpp!=0:
        cand2=abs(minus[0])/abs(tmpp)
    else:
        cand2=0

if tmpp==0:
    if cnt_minus%2==0:
        print(0)
        exit()
    elif minus:
        ans=1
        flg=True
        for i in range(k):
            if flg and cand[i]==tmpp:
                flg=False
                continue
            ans*=cand[i]
            ans%=mod
        print((ans*minus[0])%mod)
        exit()
elif (cand1!=None and cand2==None) or ((cand1!=None and cand2!=None) and cand1>=cand2):
    ans=1
    flg=True
    for i in range(k):
        if flg and cand[i]==tmpm:
            flg=False
            continue
        ans*=cand[i]
        ans%=mod
    print((ans*plus[0])%mod)
    exit()

elif (cand1==None and cand2!=None) or ((cand1!=None and cand2!=None) and cand1<cand2):
    ans=1
    flg=True
    for i in range(k):
        if flg and cand[i]==tmpp:
            flg=False
            continue
        ans*=cand[i]
        ans%=mod
    print((ans*minus[0])%mod)
    exit()

Submission status: Wrong Answer

Solution code:
print(0)

Submission status: Wrong Answer

Solution code:
n,k=map(int, input().split())
a = list(map(int, input().split()))
mod=10**9+7
if n==k:
    ans=1
    for i in range(k):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()
minus=[i for i in a if i<0]
plus=[i for i in a if i>=0]
from collections import deque
minus=deque(sorted(minus))
plus=deque(sorted(plus,reverse=True))

n_minus=len(minus)
n_plus=len(plus)

if n_minus==n:
    ans=1
    if k%2==0:
        for i in range(k):
            ans*=minus.popleft()
            ans%=mod
        print(ans)
        exit()
    else:
        for i in range(k):
            ans*=minus.pop()
            ans%=mod
        print(ans)
        exit()

cnt_minus=0
cand=deque([])
for i in range(k):
    if not plus or ((plus and minus) and abs(minus[0])>abs(plus[0])):
        cand.append(minus.popleft())
        cnt_minus+=1
    elif not minus or ((plus and minus) and abs(minus[0])<abs(plus[0])):
        cand.append(plus.popleft())
    else:
        if cnt_minus%2==1:
            cand.append(minus.popleft())
            cnt_minus+=1
        else:
            cand.append(plus.popleft())

if cnt_minus%2==0:
    ans=1
    for i in range(k):
        ans*=cand[i]
        ans%=mod
    print(ans)
    exit()

if 0 in cand:
    print(0)
    exit()

tmpm,tmpp=None,None

for i in range(k-1,-1,-1):
    if cand[i]<0 and tmpm==None:
        tmpm=cand[i]
    elif cand[i]>=0 and tmpp==None:
        tmpp=cand[i]

#print(tmpm,tmpp)
cand1,cand2=None,None
if tmpm!=None and plus:
    cand1=plus[0]/abs(tmpm)
if tmpp!=None and minus:
    if tmpp!=0:
        cand2=abs(minus[0])/abs(tmpp)
    else:
        cand2=0

elif (cand1!=None and cand2==None) or ((cand1!=None and cand2!=None) and cand1>=cand2):
    ans=1
    flg=True
    for i in range(k):
        if flg and cand[i]==tmpm:
            flg=False
            continue
        ans*=cand[i]
        ans%=mod
    print((ans*plus[0])%mod)
    exit()

elif (cand1==None and cand2!=None) or ((cand1!=None and cand2!=None) and cand1<cand2):
    ans=1
    flg=True
    for i in range(k):
        if flg and cand[i]==tmpp:
            flg=False
            continue
        ans*=cand[i]
        ans%=mod
    print((ans*minus[0])%mod)
    exit()

Submission status: Wrong Answer

Solution code:
n,k=map(int, input().split())
a = list(map(int, input().split()))
mod=10**9+7
if n==k:
    ans=1
    for i in range(k):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()
minus=[i for i in a if i<0]
plus=[i for i in a if i>=0]
from collections import deque
minus=deque(sorted(minus))
plus=deque(sorted(plus,reverse=True))

n_minus=len(minus)
n_plus=len(plus)

if n_minus==n:
    ans=1
    if k%2==0:
        for i in range(k):
            ans*=minus.popleft()
            ans%=mod
        print(ans)
        exit()
    else:
        for i in range(k):
            ans*=minus.pop()
            ans%=mod
        print(ans)
        exit()

cnt_minus=0
cand=deque([])
for i in range(k):
    if not plus or ((plus and minus) and abs(minus[0])>abs(plus[0])):
        cand.append(minus.popleft())
        cnt_minus+=1
    elif not minus or ((plus and minus) and abs(minus[0])<abs(plus[0])):
        cand.append(plus.popleft())
    else:
        if cnt_minus%2==1:
            cand.append(minus.popleft())
            cnt_minus+=1
        else:
            cand.append(plus.popleft())

if cnt_minus%2==0:
    ans=1
    for i in range(k):
        ans*=cand[i]
        ans%=mod
    print(ans)
    exit()

tmpm,tmpp=None,None

for i in range(k-1,-1,-1):
    if cand[i]<0 and tmpm==None:
        tmpm=cand[i]
    elif cand[i]>=0 and tmpp==None:
        tmpp=cand[i]

#print(tmpm,tmpp)
cand1,cand2=None,None
if tmpm!=None and plus:
    cand1=plus[0]/abs(tmpm)
if tmpp!=None and minus:
    if tmpp!=0:
        cand2=abs(minus[0])/abs(tmpp)
    else:
        cand2=0


if (cand1!=None and cand2==None) or ((cand1!=None and cand2!=None) and cand1>=cand2):
    ans=1
    flg=True
    for i in range(k):
        if flg and cand[i]==tmpm:
            flg=False
            continue
        ans*=cand[i]
        ans%=mod
    print((ans*plus[0])%mod)
    exit()
elif (cand1==None and cand2!=None) or ((cand1!=None and cand2!=None) and cand1<cand2):
    ans=1
    flg=True
    for i in range(k):
        if flg and cand[i]==tmpp:
            flg=False
            continue
        ans*=cand[i]
        ans%=mod
    print((ans*minus[0])%mod)
    exit()

Submission status: Wrong Answer

Solution code:
def get_neg(neg_list, k, mod):
    ans = 1
    neg_list.sort(reverse=True)
    for num in neg_list[:k]:
        ans = ans * num % mod
    return ans


def get_pos(pos_list, neg_list, k, mod):
    ans = 1
    nums = []
    neg_iter = iter(sorted(neg_list))
    pos_iter = iter(sorted(pos_list, reverse=True))
    if k % 2 == 1:
        ans *= pos_iter.__next__()
        k -= 1
    for a, b in zip(pos_iter, pos_iter):
        nums.append(a * b)

    for a, b in zip(neg_iter, neg_iter):
        nums.append(a * b)

    nums.sort(reverse=True)
    for num in nums[:k//2]:
        ans *= num
        ans %= mod
    return ans


def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    pos_list = []
    neg_list = []

    for a in A:
        if a >= 0:
            pos_list.append(a)
        else:
            neg_list.append(a)

    if k % 2 and not pos_list:
        ans = get_neg(neg_list, k, mod)
    else:
        ans = get_pos(pos_list, neg_list, k, mod)

    print(ans)


if __name__ == "__main__":
    main()

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 = INF
min_minus = - INF
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:
    if A[K] >= 0:
        ans = ans * pow(min_minus, MOD-2, MOD) * A[K] % MOD
    else:
        ans = ans * pow(min_plus, MOD-2, MOD) * A[K] % MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    N, K = in_nn()
    A = in_nl()

    #import random
    #N, K = 100, 99
    #A = [random.randint(-10**9, 10**9) for _ in range(N)]

    mod = 10 ** 9 + 7

    Am = []
    Ap = []

    for i in range(N):
        if A[i] < 0:
            Am.append(A[i])
        elif A[i] >= 0:
            Ap.append(A[i])

    Ap = list(sorted(Ap, reverse=True))
    Am = list(sorted(Am))

    Nm = len(Am)
    Np = len(Ap)

    if Nm + Np == K:
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= mod
    elif Np == 0:
        if K % 2 == 0:
            ans = 1
            for i in range(K):
                ans *= Am[i]
                ans %= mod
        else:
            ans = 1
            for i in range(K):
                ans *= Am[Nm - 1 - i]
                ans %= mod
    else:
        count = 0
        nums = []

        Am = deque(Am)
        Ap = deque(Ap)

        while True:
            if count == K:
                break
            elif count == K - 1:
                nums.append(Ap.popleft())
                count += 1
            else:
                if len(Ap) >= 2 and len(Am) >= 2:
                    tp = Ap[0] * Ap[1]
                    tm = Am[0] * Am[1]
                    if tp > tm:
                        nums.append(Ap.popleft())
                        nums.append(Ap.popleft())
                    else:
                        nums.append(Am.popleft())
                        nums.append(Am.popleft())
                elif len(Ap) >= 2:
                    nums.append(Ap.popleft())
                    nums.append(Ap.popleft())
                elif len(Am) >= 2:
                    nums.append(Am.popleft())
                    nums.append(Am.popleft())
                count += 2

        ans = 1
        for n in nums:
            ans *= n
            ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 1
mod = 10**9 + 7
c = 0
z = 0
for i in a:
    if i < 0:
        c += 1
    elif i == 0:
        z += 1
if c == n and k & 1:
    a.reverse()
    for i in range(k):
        ans *= -a[i]
        ans %= mod
    print(-ans % mod)
elif c == n:
    for i in range(k):
        ans *= -a[i]
        ans %= mod
    print(ans)
elif k == n:
    for i in a:
        ans *= abs(i)
        ans %= mod
    print(((-1)**(c&1) * ans) % mod)
else:
    plus = [i for i in a if i > 0]
    minus = [i for i in a if i <= 0]
    plus.sort(reverse=1)
    minus.sort()
    plus += [0] * z
    x = len(plus)
    y = len(minus)
    p, m = 0, 0
    for i in range(k // 2):
        if x - 1 <= p:
            ans *= minus[m] * minus[m + 1]
            m += 2
        elif y - 1 <= m:
            ans *= plus[p] * plus[p + 1]
            p += 2
        else:
            if minus[m] * minus[m + 1] >= plus[p] * plus[p + 1]:
                ans *= minus[m] * minus[m + 1]
                m += 2
            else:
                ans *= plus[p] * plus[p + 1]
                p += 2
        ans %= mod
    if k & 1:
        if p < x:
            ans *= plus[p]
        else:
            ans *= minus[-1]
        ans %= mod

    print(ans % mod)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    N, K = in_nn()
    A = in_nl()

    #import random
    #N, K = 100, 99
    #A = [random.randint(-10**9, 10**9) for _ in range(N)]

    mod = 10 ** 9 + 7

    Am = []
    Ap = []

    for i in range(N):
        if A[i] < 0:
            Am.append(A[i])
        elif A[i] >= 0:
            Ap.append(A[i])

    Ap = list(sorted(Ap, reverse=True))
    Am = list(sorted(Am))

    Nm = len(Am)
    Np = len(Ap)

    if Nm + Np == K:
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= mod
    elif Np == 0:
        if K % 2 == 0:
            ans = 1
            for i in range(K):
                ans *= Am[i]
                ans %= mod
        else:
            ans = 1
            for i in range(K):
                ans *= Am[Nm - 1 - i]
                ans %= mod
    else:
        count = 0
        nums = []

        Am = deque(Am)
        Ap = deque(Ap)

        while True:
            if count == K:
                break
            elif count == K - 1:
                nums.append(Ap.popleft())
                count += 1
            else:
                if len(Ap) >= 2 and len(Am) >= 2:
                    tp = Ap[0] * A[1]
                    tm = Am[0] * Am[1]
                    if tp > tm:
                        nums.append(Ap.popleft())
                        nums.append(Ap.popleft())
                    else:
                        nums.append(Am.popleft())
                        nums.append(Am.popleft())
                elif len(Ap) >= 2:
                    nums.append(Ap.popleft())
                    nums.append(Ap.popleft())
                elif len(Am) >= 2:
                    nums.append(Am.popleft())
                    nums.append(Am.popleft())
                count += 2

        ans = 1
        for n in nums:
            ans *= n
            ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

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
min_plus = INF
min_minus = - INF
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]
    else:
        ans = 0
        print(0)
        exit()
if ans > 0:
    print(ans)
    exit()
else:
    if A[K] >= 0:
        ans = ans * pow(min_minus, MOD-2) * A[K] % MOD
    else:
        ans = ans * pow(min_plus, MOD-2) * A[K] % MOD
    print(ans)

Submission status: Wrong Answer

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

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

ans=1

if K%2==1:
    p=0
    z=0
    for a in A:
        if a>0: p+=1
        if a==0: z+=1

    if p==0 and z==0: ans=-1
    if p==0 and z>0: ans=0

N,P=[],[]

if ans>0:
    A=sorted(A, key=lambda x: abs(x),reverse=True)
    i=0
    ni=0
    for a in A:
        if a>0: 
            P.append(a)
            i+=1
        if a<0: 
            N.append(a)
            ni+=1
            i+=1
            

        if a==0: 
            ans=0
            i+=1
        
        if i >= K: 
            if ni%2==1:
                N=N[:-1]
                ni-=1
            else:
                break

if ans<0:
    ans=1
    A=sorted(A, key=lambda x: abs(x))
    for a in A[:K]:
        N.append(a)
#print(P)
#print(N)

if ans!=0:
    for p in P:
        ans*=p
        ans%=1000000007

    for n in N:
        ans*=n
        ans%=1000000007


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 *= 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 *= 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 *= pairs[i] % MOD

    print(ans % MOD)


if __name__ == "__main__":
    main()