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: Accepted

Solution code:
from collections import deque
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9 + 7
# 0以上の数
X = []
# 負の数
Y = []
for a in A:
    if a >= 0:
        X.append(a)
    else:
        Y.append(a)
X.sort(reverse=True)
X = deque(X)
Y.sort()
Y = deque(Y)
# print(X)
# print(Y)

nums = []
# 全部選ぶしかない場合
if K == N:
    nums = A
# どうやっても負にしかならない場合
# 絶対値が小さくなるように取っていく
elif len(Y) == N and K % 2 == 1:
    for _ in range(K):
        nums.append(Y.pop())
# 上位以外の場合、結果を0以上にすることが出来る
# 絶対値が大きくなるように and 負にならないように 取っていく
else:
    while len(nums) < K:
        if len(X) >= 2 and len(Y) >= 2:
            if X[0] * X[1] >= Y[0] * Y[1] or len(nums) == K - 1:
                nums.append(X.popleft())
            else:
                nums.append(Y.popleft())
                nums.append(Y.popleft())
        elif len(X) >= 2 and len(Y) <= 1:
            nums.append(X.popleft())
        elif len(X) == 1 and len(Y) >= 2:
            if X[0] >= Y[0] * Y[1] or len(nums) == K - 1:
                nums.append(X.popleft())
            else:
                nums.append(Y.popleft())
                nums.append(Y.popleft())
        elif len(X) == 1 and len(Y) <= 1:
            nums.append(X.popleft())
        elif len(X) == 0 and len(Y) >= 2:
            if len(nums) == K - 1:
                nums.append(Y.pop())
            else:
                nums.append(Y.popleft())
                nums.append(Y.popleft())
        elif len(X) == 0 and len(Y) <= 1:
            num.append(Y.pop())

ans = 1
for num in nums:
    ans *= num
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def main():
    mod = 10**9+7
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(key=lambda x: -abs(x))
    kouho = []
    minus = 0
    last_plus = None
    last_minus = None
    if k == 1:
        print(max(a))
        return
    for i in range(k):
        kouho.append(a[i])
        if a[i] >= 0:
            last_plus = a[i]
        if a[i] < 0:
            minus += 1
            last_minus = a[i]
    if minus % 2 == 0:
        ans = 1
        for i in kouho:
            ans = ans*i % mod
        print(ans)
        return
    change_plus = None
    change_minus = None
    if last_plus != None:
        # マイナスを追加する
        for i in range(k, n):
            if a[i] <= 0:
                change_plus = a[i]
                break
    if last_minus != None:
        # マイナスを追加する
        for i in range(k, n):
            if a[i] >= 0:
                change_minus = a[i]
                break

    # print(kouho)
    #print(last_plus, change_plus)
    #print(last_minus, change_minus)

    if change_plus == None and change_minus == None:
        ans = 1
        for i in range(k):
            ans = ans*a[-i-1] % mod
    elif change_plus == None:
        ans = change_minus
        for i in kouho:
            ans = ans*i % mod
        ans = ans*pow(last_minus, mod-2, mod) % mod
    elif change_minus == None:
        ans = change_plus
        for i in kouho:
            ans = ans*i % mod
        ans = ans*pow(last_plus, mod-2, mod) % mod
    else:
        if abs(change_plus*last_minus) < abs(change_minus*last_plus):
            ans = change_minus
            for i in kouho:
                ans = ans*i % mod
            ans = ans*pow(last_minus, mod-2, mod) % mod
        else:
            ans = change_plus
            for i in kouho:
                ans = ans*i % mod
            ans = ans*pow(last_plus, mod-2, mod) % mod
    print(ans)


main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 1
if N == K:
    for a in A:
        ans = ans * a % MOD
    print(ans)
    exit(0)

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

if len(minus) == N:
    if K % 2 == 0:
        A.sort()
    else:
        A.sort(reverse=True)
    for i in range(K):
        ans = ans * A[i] % MOD
    print(ans)
    exit(0)

minus.sort(reverse=True)
plus.sort()

if  K % 2:
    ans *= plus.pop()

B = []

while len(minus) > 1:
    a = minus.pop()
    b = minus.pop()
    B.append(a * b)

while len(plus) > 1:
    a = plus.pop()
    b = plus.pop()
    B.append(a * b)

B.sort()

for i in range(K // 2):
    ans = ans * B.pop() % MOD

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
X = list(map(int, input().split()))
MOD = 10 ** 9 + 7
 
pos = sorted(v for v in X if v >= 0)
neg = sorted(-v for v in X if v < 0)
if N == K:
    ans = 1
    for x in X:
        ans *= x
        ans %= MOD
    print(ans % MOD)
    exit()
ok = False  # True: ans>=0, False: ans<0
if pos:
    #正の数があるとき
    ok = True
else:
    #全部負-> Kが奇数なら負にならざるをえない。
    ok = (K % 2 == 0)
 
ans = 1
if ok:
    # ans >= 0
    if K % 2 == 1:
        #Kが奇数の場合初めに1つ正の数を掛けておく
        #こうすれば後に非負でも負でも2つずつのペアで
        #考えられる
        ans = ans * pos.pop() % MOD
 
    # 答えは非負になる→二つの数の積は必ず非負になる．
    cand = []
    while len(pos) >= 2:
        x = pos.pop() * pos.pop()
        cand.append(x)
 
    while len(neg) >= 2:
        x = neg.pop() * neg.pop()
        cand.append(x)
 
    cand.sort(reverse=True) # ペアの積が格納されているので必ず非負
    # ペア毎に掛けていく
    for i in range(K // 2):
        ans = ans * cand[i] % MOD
else:
    # ans <= 0
    cand = sorted(X, key=lambda x: abs(x))
    for i in range(K):
        ans = ans * cand[i] % MOD
 
print(ans)

Submission status: Accepted

Solution code:
def myabs(n):
    n = int(n)
    if n>0:
        return [n,1]
    else:
        return [abs(n),-1]


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

def main(n,k,a,mod):
    flag = True
    for i in a:
        if i[1]==1:
            flag = False
            break
    if k%2==0:
        flag = False

    #All elements are negative and odd k
    if flag:
        ans = 1
        for i in range(n-1,n-1-k,-1):
            ans *= (a[i][0]*(-1))%mod
            ans %= mod
        print(ans)
    else:
        ans = [1,1]
        neg_flag = False
        min_neg = -1
        min_pos = -1
        for i in range(k):
            if a[i][1]==-1:
                if neg_flag == True:
                    neg_flag = False
                    ans[1] *= a[i][0]
                    ans[0] = ans[1]
                else:
                    neg_flag = True
                    ans[1] *= a[i][0]
                    min_neg = i
            else:
                ans[0] *= a[i][0]
                ans[1] *= a[i][0]
                min_pos = i
            ans[0] %= mod
            ans[1] %= mod

        if neg_flag and n!=k:
            next_pos = -1
            next_neg = -1
            for i in range(k,n):
                if next_pos==-1 and a[i][1]==1:
                    next_pos = a[i][0]
                elif next_neg==-1 and a[i][1]==-1:
                    next_neg = a[i][0]
                if next_pos>=0 and next_neg>=0:
                    break
            if min_pos==-1:
                ans[0] *= next_pos%mod
                ans[0] %= mod
                print(ans[0])
            elif a[min_neg][0]*next_neg>a[min_pos][0]*next_pos:
                fin_ans = 1
                for i in range(k):
                    if i!=min_pos:
                        fin_ans *= a[i][0]%mod
                        fin_ans %= mod
                fin_ans *= next_neg%mod
                fin_ans %= mod
                print(fin_ans)
            else:
                fin_ans = 1
                for i in range(k):
                    if i!=min_neg:
                        fin_ans *= a[i][0]%mod
                        fin_ans %= mod
                fin_ans *= next_pos%mod
                fin_ans %= mod
                print(fin_ans)
        elif n==k and neg_flag:
            print((ans[1]*-1)%mod)
        else:
            print(ans[1])




if __name__=="__main__":
    main(N,K,A,Mod)

Submission status: Accepted

Solution code:
#E_Multiplication4
N,K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 1000000007
#ソート
arr = []
j = 0
i = 0
seki = 1
gyaku = 1
minuscount = 0
minusposition = 0

def modpow(a,n,mod):
    res = 1
    while n > 0 :
        if n & 1 :
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res
def modinv(a,mod):
    return modpow(a, mod - 2, mod)
 
arr = sorted(A,reverse = True)
if arr[(N -1)] > 0 :
    for i in range(K):
        seki = seki * arr[i] % MOD
else:
    if arr[0] < 0 :
        for j in range(K):
            if K % 2 == 1:
                seki = seki * arr[j] % MOD
            else:
                seki = seki * arr[N-j-1] % MOD
    else:
        while (i + j) < K:
            if (i + j + 1) < K :
                if arr[i] * arr[i+1] > (arr[(N - j -1)] * arr[(N - j -2)]):
                    seki = seki * arr[i] % MOD
                    i += 1
                else:
                    minuscount += 2
                    minusposition = N - j -2
                    seki = (seki * arr[(N - j -1)] % MOD) * arr[(N - j -2)] % MOD
                    j += 2
            else:
                if abs(arr[i]) > abs( arr[(N - j -1)]) :
                    seki = seki * arr[i] % MOD
                    i += 1
                else:               
                    minuscount += 1
                    minusposition = N - j -1
                    seki = seki * arr[(N - j -1)] % MOD
                    j += 1
if (minuscount % 2) != 0:
    if minusposition != (i - 1):
        gyaku = modinv(arr[minusposition],MOD)
        seki  = seki * gyaku % MOD
        seki  = seki * arr[i] % MOD
print(seki)

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
mul = lambda x, y : x * y % MOD
from functools import reduce
def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(key = abs, reverse = 1)

    if all(a < 0 for a in A) or n == k:
        if k & 1:
            print(reduce(mul, A[-k:]))
        else:
            print(reduce(mul, A[:k]))
        return

    pos = []
    neg = []
    for a in A:
        if a >= 0:
            pos.append(a)
        else:
            neg.append(-a)

    pos.reverse()
    neg.reverse()
    ans = 1
    if k & 1:
        ans *= pos.pop()
        k -= 1

    for _ in range(k // 2):
        if len(pos) >= 2 and len(neg) >= 2:
            a, b = pos[-2:]
            c, d = neg[-2:]
            if a * b >= c * d:
                ans *= pos.pop()
                ans *= pos.pop()
                ans %= MOD
            else:
                ans *= neg.pop()
                ans *= neg.pop()
                ans %= MOD
        elif len(pos) >= 2:
            ans *= pos.pop()
            ans *= pos.pop()
            ans %= MOD
        elif len(neg) >= 2:
            ans *= neg.pop()
            ans *= neg.pop()
            ans %= MOD
    print(ans)
resolve()

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

import numpy as np

x = np.argsort(list(map(lambda x: -abs(x), A)))
B = []
C = []

for xx in x:
    B.append(A[xx])
    C.append(np.sign(A[xx]))

ans = 1
s = 1
flag4 = 0

for i in range(K):
    s *= C[i]

if s < 0:
    p = np.sign(B[K-1])
    flag1 = 0
    for i in range(K-1,-1,-1):
        if C[i] == p*(-1):
            idx1 = i
            flag1 = 1
            break

    flag2 = 0
    for i in range(K,N):
        if C[i] == p*(-1):
            idx2 = i
            flag2 = 1
            break

    flag3 = 0
    if flag1 == 1:
        for i in range(K,N):
            if C[i] == p:
                idx3 = i
                flag3 = 1
                break

    if flag1 and flag2 and flag3:
        if abs(B[K-1])*abs(B[idx3]) <= abs(B[idx1])*abs(B[idx2]):
            B[K-1] = B[idx2]
        else:
            B[idx1] = B[idx3]
    elif flag1 and (not flag2) and flag3:
        B[idx1] = B[idx3]
    elif flag1 and flag2 and (not flag3):
        B[K-1] = B[idx2]
    elif (not flag1) and flag2:
        B[K-1] = B[idx2]
    else:
        flag4 = 1

if flag4:
    for i in range(N-1,N-K-1,-1):
        ans = (ans * (B[i] % mod)) % mod
else:
    for i in range(K):
        ans = (ans * (B[i] % mod)) % mod

print(ans % mod)

Submission status: Accepted

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

MOD = 10**9+7
N, K = map(int, readline().split())
A = list(map(int, readline().split()))
posi = [(a, 0) for a in A if a >= 0]
nega = [(-a, 1) for a in A if a < 0]
B = posi + nega
B.sort(reverse = True)

if N == K:
    ans = 1
    for i in range(K):
        ans = (ans*A[i]) % MOD  
    print(ans)
elif N == len(nega):
    if K & 1:
        A.sort(reverse = True)
    else:
        A.sort()
    ans = 1
    for i in range(K):
        ans = (ans*A[i]) % MOD  
    print(ans)
else:
    cnt = 0
    for i in range(K):
        _, s = B[i]
        cnt ^= s
    
    res, _ = map(list, zip(*B[:K]))
    if cnt:
        pf, nf, ps, ns = None, None, 0, 0
        for i in range(K):
            b, s = B[i]
            if s:
                nf = b
            else:
                pf = b
        
        for i in range(K, N):
            b, s = B[i]
            if s:
                ns = b
                break
        for i in range(K, N):
            b, s = B[i]
            if not s:
                ps = b
                break
        
        if pf is None:
            res.remove(nf)
            res.append(ps)
        elif nf is None:
            res.remove(pf)
            res.append(ns)
        elif ns*nf >= pf*ps:
            res.remove(pf)
            res.append(ns)
        else:
            res.remove(nf)
            res.append(ps)
        
    ans = 1
    for r in res:
        ans = (ans*r) % MOD
        
    print(ans)

Submission status: Accepted

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

def main():
    N,K = list(map(int, sys.stdin.readline().split()))
    A_list = list(map(int, sys.stdin.readline().split()))
    

    A_list.sort(key=lambda x: -abs(x))
    A_plus = []
    A_minus = []
    mod = 10**9 + 7

    for val in A_list:
        if val >= 0:
            A_plus.append(val)
        else:
            A_minus.append(val)
    

    ans = 1
    cnt = 0
    i_p = 0  # index of A_plus
    i_m = 0  # index of A_minus


    while (cnt < K):
        if (K - cnt) == 1:
            if i_p < len(A_plus):
                ans *= A_plus[i_p]
                ans %= mod
                cnt += 1
                i_p += 1
                break
            
            else:
                ans2 = 1

                for i in range( len(A_list)-K, len(A_list) ):
                    ans2 *= A_list[i]
                    ans2 %= mod

                print(ans2)
                return


        if (i_m + 1) < len(A_minus):
            if (i_p + 1) < len(A_plus):
                if abs( A_plus[i_p] * A_plus[i_p + 1] ) > abs( A_minus[i_m] * A_minus[i_m + 1] ):
                    ans *= A_plus[i_p]
                    cnt += 1
                    i_p += 1
                else:
                    ans *= (A_minus[i_m] * A_minus[i_m + 1])
                    cnt += 2
                    i_m += 2

            else:
                ans *= (A_minus[i_m] * A_minus[i_m + 1])
                cnt += 2
                i_m += 2
            
        else:
            ans *= A_plus[i_p]
            cnt += 1
            i_p += 1
        

        ans %= mod
    
    
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N,K = list(map(int, sys.stdin.readline().split()))
    A_list = list(map(int, sys.stdin.readline().split()))
    

    A_list.sort(key=lambda x: -abs(x))
    A_plus = []
    A_minus = []
    mod = 10**9 + 7

    for val in A_list:
        if val >= 0:
            A_plus.append(val)
        else:
            A_minus.append(val)
    

    select = []
    i_p = 0  # index of A_plus
    i_m = 0  # index of A_minus

    
    while (len(select) < K):
        if (K - len(select)) == 1:
            if i_p < len(A_plus):
                select.append( A_plus[i_p] )
                i_p += 1
                break
            
            else:
                ans = 1

                for i in range( len(A_list)-K, len(A_list) ):
                    ans *= A_list[i]
                    ans %= mod

                print(ans)
                return


        if (i_m + 1) < len(A_minus):
            if (i_p + 1) < len(A_plus):
                if abs( A_plus[i_p] * A_plus[i_p + 1] ) > abs( A_minus[i_m] * A_minus[i_m + 1] ):
                    select.append( A_plus[i_p] )
                    i_p += 1
                else:
                    select.extend( [ A_minus[i_m] , A_minus[i_m + 1] ] )
                    i_m += 2

            else:
                select.extend( [ A_minus[i_m] , A_minus[i_m + 1] ] )
                i_m += 2
            
        else:
            select.append( A_plus[i_p] )
            i_p += 1
    


    ans = 1
 
    for i in range(K):
        ans *= select[i]
        ans %= mod
    
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N,K = list(map(int, sys.stdin.readline().split()))
    A_list = list(map(int, sys.stdin.readline().split()))
    

    A_list.sort(key=lambda x: -abs(x))
    A_plus = []
    A_minus = []
    mod = 10**9 + 7

    for val in A_list:
        if val >= 0:
            A_plus.append(val)
        else:
            A_minus.append(val)
    

    if (not A_plus):
        if (K % 2 == 0):
            target_range = range(K)
        else:
            target_range = range(len(A_minus)-K, len(A_minus))

        ans = 1

        for i in target_range:
            ans *= A_minus[i]
            ans %= mod
        
        print(ans)
        return


    if (not A_minus):
        ans = 1

        for i in range(K):
            ans *= A_plus[i]
            ans %= mod
        
        print(ans)
        return


    select = []
    i_p = 0  # index of A_plus
    i_m = 0  # index of A_minus


    while (len(select) < K):
        if (K - len(select)) == 1:
            if i_p < len(A_plus):
                select.append( A_plus[i_p] )
                i_p += 1
                break
            
            else:
                ans = 1

                for i in range( len(A_list)-K, len(A_list) ):
                    ans *= A_list[i]
                    ans %= mod

                print(ans)
                return


        if (i_m + 1) < len(A_minus):
            if (i_p + 1) < len(A_plus):
                if abs( A_plus[i_p] * A_plus[i_p + 1] ) > abs( A_minus[i_m] * A_minus[i_m + 1] ):
                    select.append( A_plus[i_p] )
                    i_p += 1
                else:
                    select.extend( [ A_minus[i_m] , A_minus[i_m + 1] ] )
                    i_m += 2

            else:
                select.extend( [ A_minus[i_m] , A_minus[i_m + 1] ] )
                i_m += 2
            
        else:
            select.append( A_plus[i_p] )
            i_p += 1
    

    ans = 1
 
    for i in range(K):
        ans *= select[i]
        ans %= mod
    
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N,K = list(map(int, sys.stdin.readline().split()))
    A_list = list(map(int, sys.stdin.readline().split()))


    A_list.sort(key=lambda x: -abs(x))
    mod = 10**9 + 7

    L_plus  = R_plus  = -1 # the Index of plus value
    L_minus = R_minus = -1 # the Index of minus value
    # L : between index 0 to (K-1)
    # R : between index K to end


    for i in range(K-1, -1, -1):
        if (L_plus == -1) and (A_list[i] >= 0):
            L_plus = i
        if (L_minus == -1) and (A_list[i] < 0):
            L_minus = i
        if (L_plus != -1) and (L_minus != -1):
            break
    
    for i in range(K,N):
        if (R_plus == -1) and (A_list[i] >= 0):
            R_plus = i
        if (R_minus == -1) and (A_list[i] < 0):
            R_minus = i
        if (R_plus != -1) and (R_minus != -1):
            break


    cnt_minus = 0

    for i in range(K):
        if A_list[i] < 0:
            cnt_minus += 1


    if cnt_minus % 2 == 0:
        target_idx = [0, K-1]
    
    else: # cnt_minus % 2 != 0
        if (R_plus == -1) and \
           ( (L_plus == -1) or (R_minus == -1) ) :
        
            calc1 = calc2 = 0
        
        elif (R_plus != -1) and \
           ( (L_plus == -1) or (R_minus == -1) ) :
        
            calc1 = 1
            calc2 = 0
        
        elif (R_plus == -1) and \
           ( (L_plus != -1) and (R_minus != -1) ) :
        
            calc1 = 0
            calc2 = 1
        
        elif (R_plus != -1) and \
           ( (L_plus != -1) and (R_minus != -1) ) :
            
            calc1 = A_list[L_plus] * A_list[R_plus]
            calc2 = A_list[L_minus] * A_list[R_minus]


        if calc1 == calc2:
            target_idx = [N-K, N-1]
        
        elif calc1 > calc2:
            A_list[L_minus], A_list[R_plus] = A_list[R_plus], A_list[L_minus]
            target_idx = [0, K-1]

        elif calc1 < calc2:
            A_list[L_plus], A_list[R_minus] = A_list[R_minus], A_list[L_plus]
            target_idx = [0, K-1]


    ans = 1

    for i in range( target_idx[0], (target_idx[1] + 1) ):
        ans *= A_list[i]
        ans %= mod
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N,K = list(map(int, sys.stdin.readline().split()))
    A_list = list(map(int, sys.stdin.readline().split()))


    A_list.sort(key=lambda x: -abs(x))
    mod = 10**9 + 7

    L_plus  = R_plus  = -1 # the Index of plus value
    L_minus = R_minus = -1 # the Index of minus value
    # L : between index 0 to (K-1)
    # R : between index K to end


    for i in range(K-1, -1, -1):
        if (L_plus == -1) and (A_list[i] >= 0):
            L_plus = i
        if (L_minus == -1) and (A_list[i] < 0):
            L_minus = i
        if (L_plus != -1) and (L_minus != -1):
            break
    
    for i in range(K,N):
        if (R_plus == -1) and (A_list[i] >= 0):
            R_plus = i
        if (R_minus == -1) and (A_list[i] < 0):
            R_minus = i
        if (R_plus != -1) and (R_minus != -1):
            break


    cnt_minus = 0

    for i in range(K):
        if A_list[i] < 0:
            cnt_minus += 1


    if cnt_minus % 2 == 0:
        target = A_list[:K]
    
    else: # cnt_minus % 2 != 0
        if (R_plus == -1) and \
           ( (L_plus == -1) or (R_minus == -1) ) :
        
            calc1 = calc2 = 0
        
        elif (R_plus != -1) and \
           ( (L_plus == -1) or (R_minus == -1) ) :
        
            calc1 = 1
            calc2 = 0
        
        elif (R_plus == -1) and \
           ( (L_plus != -1) and (R_minus != -1) ) :
        
            calc1 = 0
            calc2 = 1
        
        elif (R_plus != -1) and \
           ( (L_plus != -1) and (R_minus != -1) ) :
            
            calc1 = A_list[L_plus] * A_list[R_plus]
            calc2 = A_list[L_minus] * A_list[R_minus]


        if calc1 == calc2:
            target = A_list[N-K:N]
        
        elif calc1 > calc2:
            A_list[L_minus], A_list[R_plus] = A_list[R_plus], A_list[L_minus]
            target = A_list[:K]

        elif calc1 < calc2:
            A_list[L_plus], A_list[R_minus] = A_list[R_minus], A_list[L_plus]
            target = A_list[:K]


    ans = 1

    for i in range(len(target)):
        ans *= target[i]
        ans %= mod
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

X = sorted([a for a in A if a >= 0])
Y = sorted([a for a in A if a < 0], key=lambda x: abs(x))
ans = 1

if 2 * (min(K, len(Y)) // 2) + len(X) >= K:
    if K % 2 == 1:
        ans *= X.pop()
        K -= 1

    XX = [(x1 * x2) for x1, x2 in zip(*[iter(X[::-1])] * 2)]
    YY = [(y1 * y2) for y1, y2 in zip(*[iter(Y[::-1])] * 2)]
    ZZ = sorted(XX + YY)

    for i in range(K // 2):
        ans *= ZZ.pop()
        ans %= MOD

else:
    Z = sorted(X + Y, key=lambda x: abs(x), reverse=True)
    for i in range(K):
        ans *= Z.pop()
        ans %= MOD

print(ans)

Submission status: Accepted

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

X = sorted([a for a in A if a >= 0])
Y = sorted([a for a in A if a < 0], key=lambda x: abs(x))

if 2 * (min(K, len(Y)) // 2) + len(X) >= K:
    ans = 1
    if K % 2 == 1:
        ans *= X.pop()
        K -= 1

    XX = [(x1 * x2) for x1, x2 in zip(*[iter(X[::-1])] * 2)]
    YY = [(y1 * y2) for y1, y2 in zip(*[iter(Y[::-1])] * 2)]
    ZZ = sorted(XX + YY)

    for i in range(K // 2):
        ans *= ZZ.pop()
        ans %= MOD

    print(ans)

else:
    ans = 1
    Z = sorted(X + Y, key=lambda x: abs(x), reverse=True)
    for i in range(K):
        ans *= Z.pop()
        ans %= MOD
    print(ans)

Submission status: Accepted

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

X = sorted([a for a in A if a > 0])
Y = sorted([a for a in A if a < 0], key=lambda x: abs(x))

if 2 * (min(K, len(Y)) // 2) + len(X) >= K:
    ans = 1
    if K % 2 == 1:
        ans *= X.pop()
        K -= 1

    XX = [(x1 * x2) for x1, x2 in zip(*[iter(X[::-1])] * 2)]
    YY = [(y1 * y2) for y1, y2 in zip(*[iter(Y[::-1])] * 2)]
    ZZ = sorted(XX + YY)

    for i in range(K // 2):
        ans *= ZZ.pop()
        ans %= MOD

    print(ans)

elif 0 in A:
    print(0)

else:
    ans = 1
    Z = sorted(X + Y, key=lambda x: abs(x), reverse=True)
    for i in range(K):
        ans *= Z.pop()
        ans %= MOD
    print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a_list = list(map(int, input().split()))
mod = 10**9+7
a_list.sort()
ans = 1
if k % 2 == 1 and a_list[-1] < 0:
    for i in range(k):
        ans *= a_list[n - 1 - i]
        ans %= mod
else:
    l = 0
    r = -1
    mlt1 = a_list[0] * a_list[1]
    mlt2 = a_list[-2] * a_list[-1]
    count = 0
    while True:
        if count == k:
            break
        elif count == k - 1:
            ans *= a_list[r] % mod
            ans %= mod
            break
        if mlt1 >= mlt2:
            ans *= mlt1 % mod
            l += 2
            count += 2
            if l <= n - 2:
                mlt1 = a_list[l + 1] * a_list[l]
        else:
            ans *= a_list[r] % mod
            r -= 1
            count += 1
            if r >= - n + 1:
                mlt2 = a_list[r - 1] * a_list[r]
        ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce

N, K = map(int, input().split())
A = list(map(int, input().split()))
Ap = [a for a in A if a>0]
Am = [a for a in A if a<0]
mod = 10**9+7
if len(Ap) + len(Am) < K:
    print(0)
    exit()
if len(Ap) + len(Am) == K:
    if 0 in A and len(Am) % 2:
        print(0)
    else:
        ans = reduce(lambda a, b: a * b % mod, Ap+Am, 1)
        print(ans)
    exit()
Ap.sort(reverse=True)
Am.sort()
if len(Ap) == 0:
    if K%2:
        if 0 in A:
            ans = 0
        else:
            ans = reduce(lambda a, b: a*b%mod, Am[-K:], 1)
    else:
        ans = reduce(lambda a, b: a*b%mod, Am[:K], 1)
    print(ans)
    exit()

idx_Am = 0
n = 0
ans = 1
for idx_Ap, ap in enumerate(Ap+[0]):
    while idx_Am < len(Am) and n < K and -Am[idx_Am] > ap:
        ans = ans * Am[idx_Am] % mod
        idx_Am += 1
        n += 1
    if n == K:
        break
    n += 1
    idx_Ap += 1
    ans = ans * ap % mod
    if n == K:
        break
else:
    assert False
if idx_Am % 2 == 0:
    print(ans)
else:
    if idx_Ap == len(Ap) or (idx_Am != len(Am) and idx_Ap > 0 and Am[idx_Am] * Am[idx_Am-1] > Ap[idx_Ap] * Ap[idx_Ap-1]):
        ans = ans * Am[idx_Am] * pow(Ap[idx_Ap-1], mod-2, mod) % mod
    else:
        ans = ans * Ap[idx_Ap] * pow(Am[idx_Am-1], mod-2, mod) % mod
    print(ans)

Submission status: Accepted

Solution code:
#時間の無駄なのでクソ問と割り切って飛ばす
def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
if N==K:
    res = 1
    for a in map(int, input().split()):
        res *= a
        res %= MOD
    print(res)
    exit()
A = []
allsgn = 0
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
    allsgn += a<0
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s
lasts = s0
if allsgn==N:
    if K%2==1:
        print((-prod(A[-K:]))%MOD)
        exit()
    else:
        print(prod(A[:K])%MOD)
        exit()
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    if lastA == -1 or (firstA is not None and A[K][0]/A[lastA][0] < A[firstA][0]/A[K-1][0]):
        res = prod(A[:K - 1]) * A[firstA][0]
    else:
        res = prod(A[:lastA]) * prod(A[lastA + 1:K + 1])
print(res%MOD)
"""
6 3
5 -3 -3 -3 -3 -2

10 7
-10 -10 -10 -10 10 10 10 10 10 10
"""