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:
import sys

sys.setrecursionlimit(10 ** 7)
# import bisect
# import numpy as np
# from collections import deque
from collections import deque
# map(int, sys.stdin.read().split())
import itertools
import heapq


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    A.sort()
    A = deque(A)
    #    print(A)
    A_minus = deque([s for s in A if s < 0])
    A_plus = deque([s for s in A if s >= 0])

    #    print(A_plus)
    #    print(A_minus)
    AA = []
    if N == K:
        ans = 1
        for l in range(N):
            ans *= A[l] 
            ans %=mod
        print(ans % mod)

    elif K % 2 == 0:
        while len(A_minus) >= 2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            AA.append(-a1 * a2)

        while len(A_plus) >= 2:
            a1 = A_plus.pop()
            a2 = A_plus.pop()
            AA.append(-a1 * a2)
        ans = 1
        heapq.heapify(AA)
        for i in range(K // 2):
            ans *= (-1 * heapq.heappop(AA)) % mod
            ans %= mod
        print(ans % mod)

    elif len(A_plus) == 0:
        ans = 1
        for i in range(K):
            ans *= A_minus.pop() % mod
            ans %= mod
        print(ans % mod)

    else:
        ans = A_plus.pop()
        while len(A_minus) >= 2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            AA.append(-a1 * a2)

        while len(A_plus) >= 2:
            a1 = A_plus.pop()
            a2 = A_plus.pop()
            AA.append(-a1 * a2)

        heapq.heapify(AA)
        for i in range(K // 2):
            ans *= (-1 * heapq.heappop(AA)) 
            ans %= mod
        print(ans % mod)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

# import bisect
# import numpy as np
# from collections import deque
from collections import deque
# map(int, sys.stdin.read().split())
# import heapq
import bisect


# def input():
#     return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    mod = 10 ** 9 + 7

    if N == K:
        ans = 1
        for i in range(N):
            ans *= A[i]
            ans %= mod
        print(ans % mod)



    elif K % 2 == 0:
        ans = 1
        j = 0
        i = N - 1
        for _ in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)

    elif A[-1] < 0:
        ans = 1
        for i in range(K):
            ans *= A[-(i + 1)]
            ans %= mod
        print(ans % mod)
    else:
        ans = A[-1]
        j = 0
        i = N - 2
        for _ in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)


if __name__ == "__main__":
    main()

Submission status: Accepted

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 and K%2 == 1:
    for i in range(K):
        ans = ans * (A[-i-1]%mod) % mod
else:
    n = 0
    p = -1
    # Kが奇数の時、正の候補の最大値をあらかじめ消費しておき、偶数の時と同様に処理できるようにする。
    if K%2 == 1:
        ans = ans * (A[p]%mod) % mod
        p -= 1
    # 正/負の候補から２つずつ消費していく
    for _ in range(K//2):
        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
        else:
            ans = ans * (A[p]%mod) % mod
            ans = ans * (A[p-1]%mod) % mod
            p -= 2        

print(ans)

Submission status: Accepted

Solution code:
mod = 1000000007
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
ans = 1
# 選択の余地がない時
if len(A) == K:
    for i in range(K):
        ans = ans * (A[i]%mod) % mod
# 負になってしまう時
elif A[-1] < 0 and K%2 == 1:
    for i in range(K):
        ans = ans * (A[-i-1]%mod) % mod
else:
    n = 0
    p = -1
    # Kが奇数の時、正の候補の最大値をあらかじめ消費しておき、偶数の時と同様に処理できるようにする。
    if K%2 == 1:
        ans = ans * (A[p]%mod) % mod
        p -= 1
    # 正/負の候補から２つずつ消費していく
    for _ in range(K//2):
        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
        else:
            ans = ans * (A[p]%mod) % mod
            ans = ans * (A[p-1]%mod) % mod
            p -= 2        

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate
from functools import reduce
from operator import mul
from bisect import bisect_left


def read():
    N, K = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, K, A


def sign(x):
    if x == 0:
        return 0
    return 1 if x > 0 else -1


def solve(N, K, A, p=10**9+7):
    A.sort(key=lambda a: -abs(a))
    s = 1  # sign
    v = 1  # value
    idx_minus = -1
    idx_not_minus = -1
    for i in range(K):
        _s = sign(A[i])
        s *= _s
        v *= A[i]
        v %= p
        if _s >= 0:
            idx_not_minus = i
        else:
            idx_minus = i
    if s >= 0 or N == K:
        return v
    
    # 以下、左からK個を掛けた数が負になるとき
    # 絶対値が小さな負の数を1つ取り除いて、絶対値が大きな正の数を1つ追加する
    a1 = A[idx_minus]
    b1 = max(A[K:])
    # 絶対値が小さな正の数を1つ取り除いて、絶対値が大きな負の数を1つ追加する
    a2 = A[idx_not_minus]
    b2 = min(A[K:])

    use_1, use_2 = True, True
    if not(idx_minus >= 0 and b1 >= 0):
        use_1 = False
    if not(idx_not_minus >= 0 and b2 < 0):
        use_2 = False
    
    if use_1 and use_2:
        if b1 * a2 >= b2 * a1:
            use_1 = True
            use_2 = False
        else:
            use_1 = False
            use_2 = True
    if use_1:
        v *= pow(a1, p-2, p)
        v %= p
        v *= b1
        v %= p
    elif use_2:
        v *= pow(a2, p-2, p)
        v %= p
        v *= b2
        v %= p
    else:
        # どうやっても正の数が作れないとき
        A.sort(key=lambda a: abs(a))
        s = 1
        v = 1
        for i in range(K):
            _s = sign(A[i])
            s *= _s
            v *= A[i]
            v %= p
    return v


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

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

pi = 1
ni = 0
ans = 1
i = 0
while i < K-1:
  if A[ni]*A[ni+1] > A[-pi]*A[-pi-1]:
    ans = ans*A[ni]*A[ni+1]%mod
    ni += 2
    i += 2
    
  else:
    ans = ans*A[-pi]%mod
    pi += 1
    i += 1
    
if i == K-1:
  ans = ans*A[-pi]%mod
  
if A[-1]<0 and K%2==1:
  ans = 1
  for i in A[N-K:]:
    ans = ans*i%mod

print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

S = []
T = []

for a in A:
    if a < 0:
        T.append(a)
    else:
        S.append(a)

lenS = len(S)
lenT = len(T)

ok = False
if lenS > 0:
    if N == K:
        ok = lenT % 2 == 0
    else:
        ok = True
else:
    ok = K % 2 == 0

ans = 1
if not ok:
    A.sort(key=lambda x: abs(x))
    for i in range(K):
        ans *= A[i]
        ans %= MOD
else:
    S.sort()
    T.sort(reverse=True)
    if K % 2 == 1:
        ans *= S.pop()
    P = []
    while len(S) >= 2:
        x = S.pop()
        x *= S.pop()
        P.append(x)
    while len(T) >= 2:
        x = T.pop()
        x *= T.pop()
        P.append(x)
    P.sort(reverse=True)
    for i in range(K//2):
        ans *= P[i]
        ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
# 解説見たつもりだけどまだWA
# https://atcoder.jp/contests/abc173/submissions/15052457
import sys
input = sys.stdin.readline

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
p = 10 ** 9 + 7
A.sort(key = lambda x : abs(x)) # 絶対値小→大
A_zpos = [a for a in A if a >= 0]
A_neg = [a for a in A if a < 0]

# 非負にできるか判定
nneg_en = False
if A_zpos:
    if K == N:
        if len(A_neg) % 2 == 0:
            nneg_en = True
    else:
        nneg_en = True
else:
    if K % 2 == 0:
        nneg_en = True


if nneg_en: # 非負にできる
    if K % 2 == 1:
        ans = A_zpos.pop() # 一番大きい正の数を確保
        K -= 1
    else:
        ans = 1

    while K > 0:
        # 2個ずつ取る
        next_zpos = -1 if len(A_zpos) < 2 else A_zpos[-1] * A_zpos[-2]
        next_neg = -1 if len(A_neg) < 2 else A_neg[-1] * A_neg[-2]
        if next_zpos >= next_neg:
            ans = ans * A_zpos.pop() * A_zpos.pop() % p
        else:
            ans = ans * A_neg.pop() * A_neg.pop() % p
        K -= 2
else:
    ans = 1
    for i in range(K):
        ans = ans * A[i] % p

print(ans)

Submission status: Accepted

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

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

s = [];  t = [];
for a in A:
    if a < 0:
        t.append(a)
    else:
        s.append(a)

P = 10 ** 9 + 7
# 非負にできるか判定
S = len(s)
T = len(t)
ok = False
if S > 0:
    if N == K:
        ok = (T % 2 == 0)
    else:
        ok = True
else:
    ok = (K % 2 == 0)

ans = 1
if not ok:
    A.sort(key = lambda x: abs(x))  # 絶対値小→大
    for i in range(K):
        ans = ans * A[i] % P
else:   # 非負にできる
    s.sort()    # 小→大
    t.sort(reverse = True)  # 絶対値小→大
    if K % 2 == 1:
        ans *= s.pop() # 一番大きい正の数を確保

    p = []
    while len(s) >= 2:
        x = s.pop()
        x = x * s.pop()
        p.append(x)

    while len(t) >= 2:
        x = t.pop()
        x = x * t.pop()
        p.append(x)

    p.sort(reverse = True)
    for i in range(K // 2):
        ans = ans * p[i] % P


print(ans % P)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

n,k = readints()
a = readints()

mod = 10**9+7

ans = 1
if n==k:
    for x in a:
        ans *= x
        ans %= mod
else:
    plus = []
    minus = []
    for x in a:
        if x>=0:
            plus.append(x)
        elif x<0:
            minus.append(x)
    if len(minus)==n and k%2==1:
        minus.sort(reverse=1)
        for i in range(k):
            ans*=minus[i]
            ans %= mod
    else:
        plus.sort(reverse=1)
        minus.sort()
        i = 0
        j = 0
        if k%2==1:
            ans *= plus[0]
            i+=1
            k-=1
        lp = len(plus)
        lm = len(minus)
        while k>0:
            if i+1<lp and j+1<lm:
                if plus[i]*plus[i+1] > minus[j]*minus[j+1]:
                    ans *= plus[i]*plus[i+1]
                    i+=2
                else:
                    ans *= minus[j]*minus[j+1]
                    j+=2
            elif i+1<lp:
                ans *= plus[i]*plus[i+1]
                i+=2
            else:
                ans *= minus[j]*minus[j+1]
                j+=2
            ans %= mod
            k-=2
print(ans)

Submission status: Accepted

Solution code:
import sys
from math import log

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def modinv(x, mod):
    a, b = x, mod
    u, v = 1, 0
    while b:
        t = a // b
        a -= t * b; a, b = b, a
        u -= t * v; u, v = v, u
    return u % mod


def solve():
    mod = 10**9 + 7
    n, k = nm()
    a = nl()
    a.sort(key=abs, reverse=True)

    if max(a) <= 0 or n == k:
        if k & 1:
            b = a[-k:]
        else:
            b = a[:k]
        d = 1
        for x in b:
            d = d * x % mod
        print(d)
        return

    d = 1
    for x in a[:k]:
        d = d * x % mod
    g = [x < 0 for x in a]

    if sum(g[:k]) % 2 == 0:
        print(d)
        return

    b = list(map(lambda x:-10000 if x == 0 else log(abs(x)), a))
    mpi = mmi = -1
    Mpi = Mmi = -1
    for i in range(k):
        if a[i] <= 0:
            mmi = i
        if a[i] >= 0:
            mpi = i
    for i in range(n-1, k-1, -1):
        if a[i] <= 0:
            Mmi = i
        if a[i] >= 0:
            Mpi = i
    if (mpi == -1 or Mmi == -1) and (mmi == -1 or Mpi == -1):
        if 0 in a: d = 0
    elif (mpi == -1 or Mmi == -1):
        d = d * a[Mpi] * modinv(a[mmi], mod) % mod
    elif (mmi == -1 or Mpi == -1):
        d = d * a[Mmi] * modinv(a[mpi], mod) % mod
    else:
        if a[Mpi] * a[mpi] >= a[Mmi] * a[mmi]:
            d = d * a[Mpi] * modinv(a[mmi], mod) % mod
        else:
            d = d * a[Mmi] * modinv(a[mpi], mod) % mod
    print(d)

    return

solve()

Submission status: Accepted

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

if all(a>=0 for a in A):
    A.sort()
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()
if all(a<0 for a in A):
    A.sort(reverse=K%2==0)
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()
if N==K:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

arr = []
for a in A:
    if a < 0:
        arr.append((-a,1))
    else:
        arr.append((a,0))

arr.sort()
pz = []
ng = []
ans = 1
for _ in range(K):
    v,s = arr.pop()
    if s:
        ng.append(v)
    else:
        pz.append(v)

for v in ng:
    ans *= v
    ans %= MOD
for v in pz:
    ans *= v
    ans %= MOD
if len(ng)%2 == 0:
    print(ans)
    exit()

b = pz[-1] if pz else None
c = ng[-1] if ng else None
a = d = None
while arr and (a is None or d is None):
    v,s = arr.pop()
    if s:
        if a is None:
            a = v
    else:
        if d is None:
            d = v

if (a is None or b is None) and (c is None or d is None):
    assert False

if a is None or b is None:
    ans *= d * pow(c,-1,MOD)
elif c is None or d is None:
    ans *= a * pow(b,-1,MOD)
else:
    if a*c > b*d:
        ans *= a * pow(b,-1,MOD)
    else:
        ans *= d * pow(c,-1,MOD)
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

if all(a>=0 for a in A):
    A.sort()
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()
if all(a<0 for a in A):
    A.sort(reverse=K%2==0)
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()
if N==K:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

arr = []
for a in A:
    if a < 0:
        arr.append((-a,1))
    else:
        arr.append((a,0))

arr.sort()
pz = []
ng = []
for _ in range(K):
    v,s = arr.pop()
    if s:
        ng.append(v)
    else:
        pz.append(v)

if len(ng)%2 == 0:
    ans = 1
    for v in ng:
        ans *= v
        ans %= MOD
    for v in pz:
        ans *= v
        ans %= MOD
    print(ans)
    exit()

b = pz[-1] if pz else None
c = ng[-1] if ng else None
a = d = None
while arr and (a is None or d is None):
    v,s = arr.pop()
    if s:
        if a is None:
            a = v
    else:
        if d is None:
            d = v

if (a is None or b is None) and (c is None or d is None):
    assert False

ans = 1
if a is None or b is None:
    ans = d
    for v in ng[:-1]:
        ans *= v
        ans %= MOD
    for v in pz:
        ans *= v
        ans %= MOD
elif c is None or d is None:
    ans = a
    for v in ng:
        ans *= v
        ans %= MOD
    for v in pz[:-1]:
        ans *= v
        ans %= MOD
else:
    if a*c > b*d:
        ans = a
        for v in ng:
            ans *= v
            ans %= MOD
        for v in pz[:-1]:
            ans *= v
            ans %= MOD
    else:
        ans = d
        for v in ng[:-1]:
            ans *= v
            ans %= MOD
        for v in pz:
            ans *= v
            ans %= MOD
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))
"""
N, K = LI()
A = LI()

def abssort(A):
    return sorted(A, key = lambda x:abs(x), reverse= True)

tmps = []
A_abs = abssort(A)
cnt = 0
while len(tmps) > K:
# for i in range(K):
    if A_abs[cnt] != 0:
        tmps.append(A_abs[i])
        cnt += 1

cnt = 0
for i in range(K):
    if tmps[i] < 0:
        cnt += 1
if cnt % 2 == 0:
    ans = 1
    for i in range(K):
        ans *= tmps[i]
        ans = ans % mod
    print(ans)
    sys.exit()
else:
    tmp_1 = copy.deepcopy(tmps)
    tmp_2 = copy.deepcopy(tmps)
    tmp_1.reverse()
    tmp_2.reverse()
    tmp_2_ = 0
    tmp_1_ = 0
    # -を一つ消す
    for i in range(K):
        if tmp_1[i] < 0:
            tmp_1.remove(tmp_1[i])
            break
    # + を一つたす
    for i in range(K, N):
        if A_abs[i] > 0:
            tmp_1.append(A_abs[i])
            tmp_1_ = 1
            break
    else:
        # +がなかった時
        tmp_1 = []
        tmp_1_ = -1 
        A_abs.reverse()
        for i in range(K):
            tmp_1.append(A_abs[i])

    # +を消して-を追加
    cnt = 0
    for i in range(K):
        if tmp_2[i] > 0:
            tmp_2.remove(tmp_2[i])
            cnt += 1
            break
    if cnt == 1:
        for i in range(K, N):
            if A_abs[i] < 0:
                tmp_2.append(A_abs[i])
                tmp_2_ = 1
                break
        else:
            tmp_2_ = 0
    else:
        tmp_2_ = -1
# print(tmp_1, tmp_2)



tmp_1_m = 1
tmp_2_m = 1
for i in range(K):
    tmp_1_m *= tmp_1[i]
    tmp_1_m = tmp_1_m % mod

if tmp_2_ == 0:
    pass
else:
    for i in range(K):
        tmp_2_m *= tmp_2[i]
        tmp_2_m = tmp_2_m % mod

# print(tmp_1_, tmp_2_)
if tmp_2_ == 0:
    print(tmp_1_m)
elif tmp_1_ == 1 and tmp_2_ == -1:
    print(tmp_1_m)
elif tmp_1_ == -1 and tmp_2_ == 1:
    print(tmp_2_m)
elif tmp_1_ == 1 and tmp_2_ == 1:
    for i in range(K):
        if tmp_1[i] == tmp_2[i]:
            pass
        elif abs(tmp_1[i]) > abs(tmp_2[i]):
            print(tmp_2_m)
            sys.exit()
        else:
            print(tmp_1_m)
            sys.exit()
else:
    print(tmp_1_m)
    # for i in range(K):
    #     if tmp_1[i] == tmp_2[i]:
    #         pass
    #     elif abs(tmp_1[i]) > abs(tmp_2[i]):
    #         print(tmp_2_m)
    #         sys.exit()
    #     else:
    #         print(tmp_1_m)
    #         sys.exit()
    """

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

# 正負に関係なくsort
A_abs = sorted(A, key = lambda x:abs(x))
A_p = [] # plusを入れる
A_n = [] # -を入れる
for i in range(N):
    if A[i] < 0:
        A_n.append(A[i])
    else:
        A_p.append(A[i])

A_n.sort()
A_p.sort(reverse = True)

ok = True
if len(A_p) > 0:
    # 正の数が存在している
    if N == K:
        # 選択肢がない時
        ok = (len(A_n) % 2 == 0)
        # 負の数が偶数個
    else:
        ok = True
else:
    ok = (K % 2 == 0)

ans = 1
if ok == False:
    for i in range(K):
        ans *= A_abs[i]
        ans = ans % mod
else:
    if K % 2 == 1:
        # 奇数個選ぶ
        ans *= A_p[0]
        ans = ans % mod
        A_p = A_p[1:]
    position = 0
    pairs = []
    cnt_p = len(A_p)
    cnt_n = len(A_n)
    while cnt_p - position > 1:
        pairs.append(A_p[position] * A_p[position + 1])
        position += 2
    position = 0
    while cnt_n - position > 1:
        pairs.append(A_n[position] * A_n[position + 1])
        position += 2

    pairs.sort(reverse=True)
    for i in range(K // 2):
        ans *= pairs[i]
        ans = ans % mod

print(ans)

Submission status: Accepted

Solution code:
_MULTITEST = False
##
def solve():
    MOD = int(1e9) + 7

    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()

    neg = sum(1 for x in a if x < 0)
    pos = sum(1 for x in a if x > 0)
    zero = a.count(0)
    
    ### Set lower bound for answer
    ans_is_neg = False
    if n == k:
        if zero == 0 and neg % 2 == 1:
            ans_is_neg = True
    else:
        if pos == 0:
            if zero == 0:
                if k % 2 == 1:
                    ans_is_neg = True
    
    ### Solve by window-sliding
    # set some initial vars

    #print(ans_is_neg)
    if ans_is_neg:
        prod = 1
        for i in a[n-k:n]:
            prod = (prod * i) % MOD
        print(prod)
    else:
        prod = 1
        p1 = 0; p2 = n-1;
        while k > 0:
            if k > 1 and p1 + 1 < n and 0 < p2 and a[p1] * a[p1+1] > a[p2] * a[p2-1]:
                prod = (prod * a[p1] * a[p1 + 1]) % MOD
                p1 += 2; k -= 2;
            else:
                prod = (prod * a[p2]) % MOD
                p2 -= 1; k -= 1;
        print(prod)

##
if __name__ == "__main__":
    t = (int(input()) if _MULTITEST else 1)
    for tt in range(t):
        solve()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
mod = 10**9+7
if (max(a) < 0 and k%2) or n == k:
  ans = 1
  for i in range(n-k,n):
    ans *= a[i]
    ans %= mod
  print(ans)
  exit()
cntn = 0
cntp = n-1
if k%2:
  ans = a[-1]
  cntp -= 1
  n -= 1
else:
  ans = 1
for i in range(k//2):
  tmp = 0
  if (cntn < n-1 and a[cntn+1] < 0) and (cntp > 0 and a[cntp-1] >= 0):
    if a[cntn]*a[cntn+1] > a[cntp-1]*a[cntp]:
      tmp = a[cntn]*a[cntn+1]
      cntn += 2
    else:
      tmp = a[cntp-1]*a[cntp]
      cntp -= 2
  elif cntn < n-1 and a[cntn+1] < 0:
    tmp = a[cntn]*a[cntn+1]
    cntn += 2
  else:
    tmp = a[cntp-1]*a[cntp]
    cntp -= 2  
  ans *= tmp
  ans %= mod
print(ans)

Submission status: Accepted

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

plus = []
minus = []
zero = 0
ans = 1

for i in a:
    if i > 0:
        plus.append(i)
    elif i < 0:
        minus.append(-i)
    else:
        zero += 1

plus.sort()
minus.sort()
p_l = len(plus)
m_l = len(minus)
cnt = 0


def tail_num(p):
    return p[-1] * p[-2]


if k == 1:
    print(max(a) % num)
elif zero > n - k:
    print(0)
elif zero == n - k:
    for i in plus:
        ans = (i * ans) % num
    for j in minus:
        ans = (ans * j) % num
    if m_l % 2 == 0:
        print(ans)
    else:
        print(-ans % num)
elif len(plus) == 0:
    if k % 2 == 0:
        for j in range(k):
            ans = ans * (minus[-(j + 1)]) % num
        print(ans % num)
    else:
        if 0 in a:
            print(0)
        else:
            for j in range(k):
                ans = ans * (minus[j]) % num
            print(-ans % num)
else:
    if k % 2 == 1:
        ans = ans * plus.pop() % num
        p_l -= 1
    for i in range(k//2):
        if p_l >= 2 and m_l >= 2:
            if tail_num(minus) >= tail_num(plus):
                ans = ans * tail_num(minus) % num
                minus.pop()
                minus.pop()
                m_l -= 2
            else:
                ans = ans * tail_num(plus) % num
                plus.pop()
                plus.pop()
                p_l -= 2
        else:
            if p_l <= 1:
                ans = ans * tail_num(minus) % num
                minus.pop()
                minus.pop()
                m_l -= 2
            else:
                ans = ans * tail_num(plus) % num
                plus.pop()
                plus.pop()
                p_l -= 2
    print(ans)

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

p = []
m = []
for i in a:
    if i >= 0:p.append(i)
    elif i < 0:m.append(i)

p.sort(reverse=True)
m.sort()
res = 1
if n == k:
    for i in a:
        res = (res * i) %mod
    print(res)
    exit()
    
if len(p) == 0 and k % 2 == 1:
    for i in range(k):
        res = (res * m[-(i + 1)]) %mod
    print(res)

else:
    p_ind = 0
    m_ind = 0
    while k:
        if k == 1:
            res = (res * p[p_ind]) % mod
            break
        
        temp = p[p_ind] * p[p_ind + 1] if p_ind + 1 < len(p) else 0
        temp1 = m[m_ind] * m[m_ind + 1] if m_ind + 1 < len(m) else 0
        if temp > temp1:
            res = (res * p[p_ind]) %mod
            p_ind += 1
            k -= 1
        else:
            res = (res * temp1) %mod
            m_ind += 2
            k -= 2
    print(res)

Submission status: Accepted

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

if K%2==1 and A[-1]<0:
    for i in range(K):
        ans=ans*A[N-(i+1)]%mod
    print(ans)
    exit()

l=0
r=N-1
if K%2==1:
    ans=ans*A[r]
    r-=1

for _ in range(K//2):
    ml=A[l]*A[l+1]
    mr=A[r]*A[r-1]
    if ml>mr:
        ans=ans*ml%mod
        l+=2
    else:
        ans=ans*mr%mod
        r-=2

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = []
T = {"mi":0, "pu":0, "zero":0}

for i in range(N):
    if A[i] < 0:
        T["mi"] += 1
    elif A[i] == 0:
        T["zero"] += 1
    else:
        T["pu"] += 1
mod = 10**9+7
for i in range(N):
    if A[i] < 0:
        B.append([A[i]*(-1), 1])
    else:
        B.append([A[i], 0])
A.sort()
B.sort(reverse=True)

ans = 1
c = 0
for i in range(K):
    ans *= B[i][0]
    ans %= mod
    c += B[i][1]

if c % 2 == 0:
    print(ans)
elif K > T["pu"]+T["mi"]:
    print(0)
elif T["mi"] == 1 and K > T["pu"]:
    ans = 1
    for i in range(N):
        ans *= A[i]
        ans %= mod
    if T["zero"] != 0:
        ans = 0
    print(ans)
elif T["pu"] == 1 and K > T["mi"]:
    ans = 1
    for i in range(N):
        ans *= A[i]
        ans %= mod
    if T["zero"] != 0:
        ans = 0
    print(ans)
elif T["pu"] == 0:
    ans = 1
    A.reverse()
    for i in range(K):
        ans *= A[i]
        ans %= mod
    if T["zero"] != 0:
        ans = 0
    print(ans)
elif N == K:
    ans = 1
    for i in range(N):
        ans *= A[i]
        ans %= mod
    print(ans)
else:
    change1 = B[K-1][1]
    change2 = (change1 + 1)%2
    chindex1 = K-1
    chindex2 = -1
    for i in range(K-1, -1, -1):
        if B[i][1] == change2:
            chindex2 = i
            break
    afterindex1 = -1
    afterindex2 = -1
    for i in range(K, N):
        if B[i][1] == change2:
            afterindex1 = i
            break
    for i in range(K, N):
        if B[i][1] == change1:
            afterindex2 = i
            break
    result1 = 0
    result2 = 0
    if chindex1 >= 0 and afterindex1 >= 0:
        ans = 1
        for i in range(N):
            if i <= K-1 or i == afterindex1:
                if i != chindex1:
                    ans *= B[i][0]
                    ans %= mod
        result1 = ans
    if chindex2 >= 0 and afterindex2 >= 0:
        ans = 1
        for i in range(N):
            if i <= K-1 or i == afterindex2:
                if i != chindex2:
                    ans *= B[i][0]
                    ans %= mod
        result2 = ans
    if result1 == 0 and result2 == 0:
        print(0)
    elif result1 == 0:
        print(result2)
    elif result2 == 0:
        print(result1)
    elif B[afterindex1][0]*B[chindex2][0] - B[afterindex2][0]*B[chindex1][0] > 0:
        print(result1)
    else:
        print(result2)

Submission status: Accepted

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

    A.sort()
    MOD = 10 ** 9 + 7
    ans = 1

    if K % 2 == 1 and A[-1] < 0:
        for i in range(K):
            ans = ans * A[N - (i + 1)] % MOD

        print(ans)
        return

    l = 0
    r = N - 1
    if K % 2 == 1:
        ans = ans * A[r]
        r -= 1
    
    for _ in range(K // 2):
        ml = A[l] * A[l + 1]
        mr = A[r] * A[r - 1]
        if ml > mr:
            ans = ans * ml % MOD
            l += 2
        else:
            ans = ans * mr % MOD
            r -= 2

    print(ans)
    return


if __name__ == '__main__':
    main()