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:
# coding: utf-8
# Your code here!

# リストxsの総乗
def inf_product(xs):
    limit = int(1e9) + 7
    p = 1
    for x in xs:
        p *= x
        p %= limit
    return p

def calp():
    '''
    import random
    limit = int(1e9)
    n = int(2e5)
    k = int(n*9/10)
    x = []
    for i in range(n):
        x.append(random.randint(-limit,limit))
    '''
    n,k = map(int,input().split())
    x = list(map(int,input().split()))
    
    # n=kであれば、全要素の総乗をpとして返す
    if n == k:
        return inf_product(x)
    # 要素0の個数がn-kより大きければ、pとして0を返す
    if x.count(0) > n-k:
        return 0

    #要素を負の配列x1 と 正の配列x2 0の配列x3に分ける
    x.append(0)
    x.sort()
    #print(x)
    m1 = x.index(0)
    m2 = x.count(0)
    x1 =x[:m1]
    x2 =x[m1+m2:]
    x3 =x[m1:m1+m2-1]
    #print(x1,x2,x3)

    # 正の要素がない場合、kが偶数の場合小さい順（絶対値の大きい順）に拾う
    # kが奇数で要素に0を含む場合は、0を返す
    # kが奇数で要素に0を含まない場合は、大きい順（絶対値の小さい順）に拾う
    if len(x2) == 0:
        if k%2 == 0:
            return inf_product(x1[:k])
        elif len(x3) != 0:
            return 0
        else:
            return inf_product(x1[-k:])

    # kが奇数の場合、正のリストの最大のものをまず1個選択する
    p = 1
    if k%2 ==1:
        p *= x2[-1]
        x2.pop(-1)
        k -= 1

    x1b,x2b = [],[]
    for i in range(0,2*int(len(x1)/2),2):
        x1b.append(x1[i]*x1[i+1])
    x2.sort(reverse=True)
    for i in range(0,2*int(len(x2)/2),2):
        x2b.append(x2[i]*x2[i+1])
    
    x1b.extend(x2b)
    x1b.sort(reverse=True)
    x1b.insert(0,p)
    #print(x1b,int(k/2)+1)
    temp = int(k/2)

    if len(x1b) > temp:
        return inf_product(x1b[:int(k/2)+1])
    else:
        if len(x3) != 0:
            return 0
        else:
            return(-1)

print(calp())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
MOD = 10**9 + 7
N, K = map(int, input().split())
A = list(map(int, (input().split())))
pos, neg = [], []
for a in A:
    if a<0:
        neg.append(a)   # 負
    else:
        pos.append(a)   # 0以上
if pos:
    if N==K:    # 全て選択で負の数が奇数ならfalse（正にできない）
        ok = (len(neg)%2 == 0)
    else:
        ok = True
else:
    ok = (K%2 == 0) # すべて負で奇数ならfalse（正にできない）
ans = 1
if ok == False: # false（正にできない）場合、絶対値が小さいものからk個かける
    A.sort(key=abs)
    for i in range(K):
        ans *= A[i]
        ans %= MOD
else:
    pos.sort()              # 後ろから取っていくので正は昇順
    neg.sort(reverse=True)  # 後ろから取っていくので負は降順
    if K%2:
        ans *= pos.pop()    # kが奇数個なら1個は正を選ぶ
    p = []  # 2個ずつかけた数を格納
    while len(pos)>=2:
        p.append(pos.pop() * pos.pop())
    while len(neg)>=2:  # 負を2回かけるのでxは正
        p.append(neg.pop() * neg.pop())
    p.sort(reverse=True)
    for i in range(K//2):   # 降順にk//2個見ていく
        ans *= p[i]
        ans %= MOD
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
ans = 1
plus = []
minus = []

if n == k:
    for i in range(n):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()
    
for i in range(n):
    if a[i] >= 0:
        plus.append(a[i])
    elif a[i] < 0:
        minus.append(a[i])

if not plus and k % 2 == 1:
    minus.sort(reverse=True)
    for i in range(k):
        ans *= minus[i]
        ans %= mod
    print(ans)
    exit()

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

cou = []
while True:
    if len(cou) == k:
        break
    elif len(cou) == k-1:
        cou.append(plus.popleft())
        break
    else:
        if len(plus)>=2 and len(minus)>=2:
            p1 = plus.popleft()
            p2 = plus.popleft()
            m1 = minus.popleft()
            m2 = minus.popleft()
            if p1*p2 > m1*m2:
                cou.append(p1)
                plus.appendleft(p2)
                minus.appendleft(m2)
                minus.appendleft(m1)
            else:
                cou.append(m1)
                cou.append(m2)
                plus.appendleft(p2)
                plus.appendleft(p1)
        elif len(plus) < 2:
            m1 = minus.popleft()
            m2 = minus.popleft()
            cou.append(m1)
            cou.append(m2)
        elif len(minus) < 2:
            p1 = plus.popleft()
            cou.append(p1)

        
for i in cou:
    ans *= i
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
M=10**9+7
n,k,*l=map(int,open(0).read().split())
lp,lm=[],[]
for i in l:
  if i<0: lm+=[i]
  else: lp+=[i]
cp,cm=len(lp),len(lm)
ok=0
if cp:
  if n==k: ok=1-cm%2
  else: ok=1
else: ok=1-k%2
a=1
if ok<1:
  l.sort(key=lambda x:abs(x))
  for i in range(k): a=a*l[i]%M
else:
  lp.sort()
  lm.sort(reverse=1)
  if k%2: a=lp.pop()
  p=[]
  while len(lp)>1: p+=[lp.pop()*lp.pop()]
  while len(lm)>1: p+=[lm.pop()*lm.pop()]
  p.sort(reverse=1)
  for i in range(k//2): a=a*p[i]%M
print(a)

Submission status: Accepted

Solution code:
M=10**9+7
n,k,*l=map(int,open(0).read().split())
lp,lm=[],[]
for i in l:
  if i<0: lm+=[i]
  else: lp+=[i]
cp,cm=len(lp),len(lm)
ok=0
if cp>0:
  if n==k: ok=1-cm%2
  else: ok=1
else: ok=1-k%2
a=1
if ok<1:
  l.sort(key=lambda x:abs(x))
  for i in range(k):
    a=a*l[i]%M
else:
  lp.sort()
  lm.sort(reverse=1)
  if k%2:
    a=lp.pop()
  p=[]
  while len(lp)>1:
    p+=[lp.pop()*lp.pop()]
  while len(lm)>1:
    p+=[lm.pop()*lm.pop()]
  p.sort(reverse=1)
  for i in range(k//2):
    a=a*p[i]%M
print(a)

Submission status: Accepted

Solution code:
def solve():
    can_positive = False
    if len(p) > 0:
        if k<n:
            can_positive = True
        else:
            can_positive = len(m) % 2 == 0
    else:
        can_positive=k%2==0
    if not can_positive:
        m.sort(reverse=True)
        return m[:k]+p
    p.sort()
    m.sort(reverse=True)
    a = [p.pop()] if k % 2 else [1]
    while len(p) >= 2:
        a.append(p.pop()*p.pop())
    while len(m) >= 2:
        a.append(m.pop()*m.pop())
    return a[:1] + sorted(a[1:], reverse=True)[:(k-k%2)//2]

mod = 10**9+7
n, k = list(map(int, input().split()))
m, p = [], []
for i in map(int, input().split()):
    if i < 0:
        m.append(i)
    else:
        p.append(i)
ans = 1
for i in solve():
    ans = ans * i % mod
print(ans)

Submission status: Accepted

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

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9+7
p, n = [], []

for Ai in A:
    if Ai>=0:
        p.append(Ai)
    else:
        n.append(Ai)

if len(n)==N and K%2==1:
    n.sort(reverse=True)
    ans = 1
    
    for ni in n[:K]:
        ans *= ni
        ans %= MOD
    
    print(ans)
    exit()

if K==N and len(n)%2==1:
    ans = 1
    
    for Ai in A:
        ans *= Ai
        ans %= MOD
    
    print(ans)
    exit()

p.sort(reverse=True)
n.sort()
l = []

if K%2==1:
    ans = p[0]
    p = p[1:]
else:
    ans = 1
    
for i in range(len(p)//2):
    l.append(p[2*i]*p[2*i+1])
    
for i in range(len(n)//2):
    l.append(n[2*i]*n[2*i+1])
    
l.sort(reverse=True)
    
for li in l[:K//2]:
    ans *= li
    ans %= MOD
    
print(ans)

Submission status: Accepted

Solution code:
def solve():
    can_positive = False
    if len(P) > 0:
        if k < n:
            can_positive = True
        else:
            can_positive = len(M) % 2 == 0
    else:
        can_positive = k % 2 == 0
    if not can_positive:
        return sorted(P + M, key=lambda x: abs(x))[:k]
    P.sort()
    M.sort(reverse=True)
    a = [P.pop()] if k % 2 else [1]
    while len(P) >= 2:
        a.append(P.pop() * P.pop())
    while len(M) >= 2:
        a.append(M.pop() * M.pop())
    return a[:1] + sorted(a[1:], reverse=True)[:(k - k%2) // 2]

n, k = map(int, input().split())
P, M = [], []
for a in map(int, input().split()):
    if a < 0:
        M.append(a)
    else:
        P.append(a)
ans, mod = 1, 10 ** 9 + 7
for a in solve():
    ans *= a
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
A.sort(key=lambda x:-abs(x))
mod=10**9+7

ans=1
if (max(A)<=0 and k%2==1) or n==k:
    for i in range(k):
        ans=ans*A[n-1-i]%mod
else:
    mi=0
    pl=0
    flg=1
    for i in range(k):
        ans=ans*A[i]%mod
        if A[i]>0:
            pl=A[i]
        if A[i]<0:
            mi=A[i]
            flg*=-1
    if ans==0:
        pass
    elif flg==-1:
        mi2=None
        pl2=None
        for i in range(k,n):
            if A[i]>=0:
                pl2=A[i]
                break
        for i in range(k,n):
            if A[i]<=0:
                mi2=A[i]
                break
        can=0
        if mi!=0 and pl2 is not None and pl!=0 and mi2 is not None:
            if pl2*pl > mi2*mi:
                can = pow(mi,-1,mod)*pl2%mod
            else:
                can = pow(pl,-1,mod)*mi2%mod
        elif mi!=0 and pl2 is not None:
            can = pow(mi,-1,mod)*pl2%mod
        elif pl!=0 and mi2 is not None:
            can = pow(pl,-1,mod)*mi2%mod
        ans=ans*can%mod

print(ans)

Submission status: Accepted

Solution code:
def solve():
    can_positive = False
    if len(P) > 0:
        if k < n: can_positive = True
        else: can_positive = len(M)%2 == 0
    else: can_positive = k%2 == 0

    if not can_positive: return sorted(P+M, key=lambda x:abs(x))[:k]
    P.sort()
    M.sort(reverse=True)
    a = [P.pop()] if k%2 else [1]
    while len(P) >= 2: a.append(P.pop() * P.pop())
    while len(M) >= 2: a.append(M.pop() * M.pop())
    return a[:1] + sorted(a[1:], reverse=True)[:(k-k%2)//2]

n, k = map(int, input().split())
P, M = [], []
for a in map(int, input().split()):
    if a < 0: M.append(a)
    else: P.append(a)
ans, MOD = 1, 10**9 + 7
for a in solve(): ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def solve():
    P.sort()
    M.sort(reverse = True)
    p, m = [], []
    while len(p) + len(m) < k:
        if len(P) > 0 and len(M) <= 0: p.append(P.pop())
        elif len(P) <= 0 and len(M) > 0: m.append(M.pop())
        elif P[-1] < -M[-1]: m.append(M.pop())
        else: p.append(P.pop())
    if len(m)%2:
        Mi = M.pop() if len(p)*len(M) else 1  #  1 is no data
        Pi = P.pop() if len(m)*len(P) else -1 # -1 is no data
        if Mi < 0 and Pi >= 0:
            if abs(p[-1] * Pi) < abs(m[-1] * Mi):
                p.pop()
                m.append(Mi)
            else:
                m.pop()
                p.append(Pi)
        elif Mi < 0:
            p.pop()
            m.append(Mi)
        elif Pi >= 0:
            m.pop()
            p.append(Pi)
        else:
            p = sorted(p+P+m+M, key=lambda x:abs(x))[:k]
            m = []
    return p + m

n, k = map(int, input().split())
P, M = [], [] # plus, minus
for a in map(int, input().split()):
    if a < 0: M.append(a)
    else: P.append(a)
ans, MOD = 1, 10**9 + 7
for a in solve(): ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Submission status: Accepted

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

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

mod=10**9+7
# mod の逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

# 正,負 で分ける
b=[]
c=[]
for i in a:
    if i>=0:
        b.append(i)
    else:
        c.append(i)

b.sort(reverse=True)
c.sort()
ans=1
if k==n:
    for i in range(n):
        ans*=a[i]
        ans%=mod

elif k%2==1 and len(c)==n:
    c.sort(reverse=True)
    for i in range(k):
        ans*=c[i]
        ans%=mod

else:
    x=k
    # プラスの配列をどこまで進めたか
    v=0
    # マイナスの配列をどこまで進めたか？
    w=0
    if k%2==1:
        ans*=b.pop(0)
        k-=1

    for i in range(k):
        if x>=2:
            x-=2
            if v+2<=len(b) and w+2<=len(c):
                if b[v]*b[v+1]>c[w]*c[w+1]:
                    ans*=b[v]*b[v+1]
                    v+=2
                else:
                    ans*=c[w]*c[w+1]
                    w+=2


            elif v+2<=len(b):
                ans*=b[v]*b[v+1]
                v+=2

            else:
                ans*=c[w]*c[w+1]
                w+=2

            ans%=mod
            if x==0:
                break

print(ans)

Submission status: Accepted

Solution code:
def solve():
    can_positive = False
    if len(P) > 0:
        if k < n: can_positive = True
        else: can_positive = len(M)%2 == 0
    else: can_positive = k%2 == 0

    if not can_positive: return sorted(P+M, key=lambda x:abs(x))[:k]

    P.sort()
    M.sort(reverse = True)
    p, m = [], []
    while len(p) + len(m) < k:
        if len(P) > 0 and len(M) <= 0: p.append(P.pop())
        elif len(P) <= 0 and len(M) > 0: m.append(M.pop())
        elif P[-1] < -M[-1]: m.append(M.pop())
        else: p.append(P.pop())
    if len(m)%2:
        Mi = M.pop() if len(p)*len(M) else 1  #  1 is no data
        Pi = P.pop() if len(m)*len(P) else -1 # -1 is no data
        if Mi < 0 and Pi >= 0:
            if abs(p[-1] * Pi) < abs(m[-1] * Mi):
                p.pop()
                m.append(Mi)
            else:
                m.pop()
                p.append(Pi)
        elif Mi < 0:
            p.pop()
            m.append(Mi)
        elif Pi >= 0:
            m.pop()
            p.append(Pi)
    return p + m

n, k = map(int, input().split())
P, M = [], [] # plus, minus
for a in map(int, input().split()):
    if a < 0: M.append(a)
    else: P.append(a)
ans, MOD = 1, 10**9 + 7
for a in solve(): ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from logging import *
basicConfig(level=DEBUG, format='%(levelname)s: %(message)s')
disable(CRITICAL)

def solve():
    can_positive = False
    if len(P) > 0:
        if k < n: can_positive = True
        else: can_positive = len(M)%2 == 0
    else: can_positive = k%2 == 0

    if not can_positive: return sorted(P+M, key=lambda x:abs(x))[:k]

    P.sort()
    M.sort(reverse = True)
    debug('k {} n {}'.format(k,n))
    debug('P {}'.format(P))
    debug('M {}'.format(M))
    p, m = [], []
    while len(p) + len(m) < k:
        if len(P) > 0 and len(M) <= 0: p.append(P.pop())
        elif len(P) <= 0 and len(M) > 0: m.append(M.pop())
        elif P[-1] < -M[-1]: m.append(M.pop())
        else: p.append(P.pop())

    debug('p {}'.format(p))
    debug('m {}'.format(m))
    debug('P {}'.format(P))
    debug('M {}'.format(M))

    if len(m)%2:
        Mi = M.pop() if len(p)*len(M) else 1  #  1 is no data
        Pi = P.pop() if len(m)*len(P) else -1 # -1 is no data
        if Mi < 0 and Pi >= 0:
            if abs(p[-1] * Pi) < abs(m[-1] * Mi):
                p.pop()
                m.append(Mi)
            else:
                m.pop()
                p.append(Pi)
        elif Mi < 0:
            p.pop()
            m.append(Mi)
        elif Pi >= 0:
            m.pop()
            p.append(Pi)
    return p + m

n, k = map(int, input().split())
P, M = [], [] # plus, minus
for a in map(int, input().split()):
    if a < 0: M.append(a)
    else: P.append(a)
ans, MOD = 1, 10**9 + 7
for a in solve(): ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

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

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

plus = []
minus = []
zeros = []

for i in range(N):
    if A[i] > 0:
        plus.append(A[i])
    elif A[i] < 0:
        minus.append(-A[i])
    else:
        zeros.append(A[i])

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

if len(plus):
    if K%2:
        ans = plus[0]
        p_place = 1
        m_place = 0
        K -= 1
    else:
        ans = 1
        p_place = 0
        m_place = 0
    while K:
        val1 = plus[p_place]*plus[p_place+1] if p_place <= len(plus)-2 else -float('inf')
        val2 = minus[m_place]*minus[m_place+1] if m_place <= len(minus)-2 else -float('inf')
        if val1 == val2 == -float('inf'):
            if p_place == len(plus)-1:
                ans *= plus[p_place]
                ans %= mod
                K -= 1
            if K:
                print(0)
                exit()
        else:
            K -= 2
            if val1 == -float('inf'):
                ans *= val2
                ans %= mod
                m_place += 2
            elif val2 == -float('inf'):
                ans *= val1
                ans %= mod
                p_place += 2
            elif val1 >= val2:
                ans *= val1
                ans %= mod
                p_place += 2
            else:
                ans *= val2
                ans %= mod
                m_place += 2
    print(ans)
else:
    if K%2:
        if len(zeros):
            print(0)
        else:
            ans = 1
            for i in range(K):
                ans *= -minus[len(minus)-1-i]
                ans %= mod
            print(ans)
    else:
        m_place = 0
        ans = 1
        while K:
            if m_place <= len(minus)-2:
                ans *= minus[m_place]*minus[m_place+1]
                ans %= mod
                m_place += 2
                K -= 2
            else:
                print(0)
                exit()
        print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
A.sort(key=lambda x:-abs(x))
mod=10**9+7

ans=1
if (max(A)<=0 and k%2==1) or n==k:
    for i in range(k):
        ans=ans*A[n-1-i]%mod
else:
    mi=0
    pl=0
    flg=1
    for i in range(k):
        ans=ans*A[i]%mod
        if A[i]>0:
            pl=A[i]
        if A[i]<0:
            mi=A[i]
            flg*=-1
    if ans==0:
        pass
    elif flg==-1:
        mi2=None
        pl2=None
        for i in range(k,n):
            if A[i]>=0:
                pl2=A[i]
                break
        for i in range(k,n):
            if A[i]<=0:
                mi2=A[i]
                break
        can=0
        if mi!=0 and pl2 is not None and pl!=0 and mi2 is not None:
            if pl2*pl > mi2*mi:
                can = pow(mi,-1,mod)*pl2%mod
            else:
                can = pow(pl,-1,mod)*mi2%mod
        elif mi!=0 and pl2 is not None:
            can = pow(mi,-1,mod)*pl2%mod
        elif pl!=0 and mi2 is not None:
            can = pow(pl,-1,mod)*mi2%mod 
        ans=ans*can%mod

print(ans)

Submission status: Accepted

Solution code:
import copy
from sys import exit
n, k = map(int, input().split())
A = list(map(int, input().split()))

mod = 10**9 + 7

plus = []
minus = []
for a in A:
    if a >= 0:
        plus.append(a)
    else:
        minus.append(a)
plus.sort()
minus.sort(reverse=True)

def is_ans_plus():
    if len(plus) > 0:
        if n == k:
            if len(minus) % 2 == 0:
                return True
            else:
                return  False
        else:
            return True
    else:
        if k % 2 == 0:
            return True
        else:
            return False

ans = 1
if is_ans_plus():
    if k % 2 == 1:
        ans *= plus.pop()
        k -= 1
    for i in range(k // 2):
        plus_pair, minus_pair = -1, -1
        if len(plus) >= 2:
            plus_pair = plus[-1] * plus[-2]
        if len(minus) >= 2:
            minus_pair = minus[-1] * minus[-2]
        if plus_pair >= minus_pair:
            ans *= plus_pair
            plus.pop()
            plus.pop()
        else:
            ans *= minus_pair
            minus.pop()
            minus.pop()
        ans %= mod
else:
    ans = -1
    A = sorted([abs(a) for a in A])
    for i in range(k):
        ans *= A[i]
        ans %= mod
print(ans)

Submission status: Accepted

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

A.sort(reverse = True)
ans = 1
if A[-1] >= 0:
    for i in range(K):
        ans *= A[i]
        ans %= MOD
elif A[0] < 0:
    if K % 2 == 0:
        for i in range(K):
            ans *= A[N-1-i]
            ans %= MOD
    else:
        for i in range(K):
            ans *= A[i]
            ans %= MOD
else:
    r,l = N-1,0
    n = 0
    while n < K:
        if K-n == 1:
            ans *= A[l]
            ans %= MOD
            n += 1
        else:
            if A[r]*A[r-1] > A[l]*A[l+1]:
                ans *= (A[r]*A[r-1])
                ans %= MOD
                r -= 2
                n += 2
            else:
                ans *= A[l]
                ans %= MOD
                l += 1
                n += 1
print(ans)

Submission status: Accepted

Solution code:
def solve():
    can_positive = False
    if len(P) > 0:
        if k < n: can_positive = True
        else: can_positive = len(M)%2 == 0
    else: can_positive = k%2 == 0

    if can_positive:
        P.sort()
        M.sort(reverse=True)
        a = [P.pop()] if k%2 else [1]
        while len(P) >= 2: a.append(P.pop() * P.pop())
        while len(M) >= 2: a.append(M.pop() * M.pop())
        return a[:1] + sorted(a[1:], reverse=True)[:(k-k%2)//2]
    else: return sorted(P+M, key=lambda x:abs(x))[:k]

n, k = map(int, input().split())
P, M = [], []
for a in map(int, input().split()):
    if a < 0: M.append(a)
    else: P.append(a)
ans, MOD = 1, 10**9 + 7
for a in solve(): ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def solve():
    can_positive = False
    if len(P) > 0:
        if k < n: can_positive = True
        else: can_positive = len(M)%2 == 0
    else: can_positive = k%2 == 0

    if can_positive:
        P.sort()
        M.sort(reverse = True)
        a = [P.pop()] if k%2 else [1]
        while len(P) >= 2: a.append(P.pop() * P.pop())
        while len(M) >= 2: a.append(M.pop() * M.pop())
        return a[:k%2] + sorted(a[1:], reverse = True)[:(k-k%2)//2]
    else: return sorted(P+M, key=lambda x: abs(x))[:k]

n, k = map(int, input().split())
P, M = [], [] # plus, minus
for a in map(int, input().split()):
    if a < 0: M.append(a)
    else: P.append(a)
ans, MOD = 1, 10**9 + 7
for a in solve(): ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from logging import *
basicConfig(level=DEBUG, format='%(levelname)s: %(message)s')
disable(CRITICAL)

def solve():
    debug('k {} n {}'.format(k,n))
    debug('P {}'.format(P))
    debug('M {}'.format(M))
    can_positive = False
    if len(P) > 0:
        if k < n: can_positive = True
        else: can_positive = len(M)%2 == 0
    else: can_positive = k%2 == 0

    if can_positive:
        debug('positive')
        P.sort()
        M.sort(reverse = True)
        p0 = []
        if k%2: p0.append(P.pop())
        ar = []
        while len(P) >= 2: ar.append(P.pop() * P.pop())
        while len(M) >= 2: ar.append(M.pop() * M.pop())
        ar.sort(reverse = True)
        debug('p0 {}'.format(p0))
        debug('ar {}'.format(ar))
        debug('ar[:k] {}'.format(ar[:(k-k%2)//2]))
        return p0 + ar[:(k-k%2)//2]
    else: # can negative
        debug('negative')
        return sorted(P+M, key=lambda x: abs(x))[:k]


n, k = map(int, input().split())
P, M = [], [] # plus, minus
for a in map(int, input().split()):
    if a < 0: M.append(a)
    else: P.append(a)
ans, MOD = 1, 10**9 + 7
for a in solve(): ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from logging import *
basicConfig(level=DEBUG, format='%(levelname)s: %(message)s')
disable(CRITICAL)

def solve():
    P.sort(reverse = True)
    M.sort()
    debug('k {} n {}'.format(k,n))
    debug('P {}'.format(P))
    debug('M {}'.format(M))
    can_positive = False
    if len(P) > 0:
        if k < n: can_positive = True
        else: can_positive = len(M)%2 == 0
    else: can_positive = k%2 == 0

    if can_positive:
        debug('positive')
        P.sort()
        M.sort(reverse = True)
        p0 = []
        if k%2: p0.append(P.pop())
        ar = []
        while len(P) >= 2: ar.append(P.pop() * P.pop())
        while len(M) >= 2: ar.append(M.pop() * M.pop())
        ar.sort(reverse = True)
        debug('p0 {}'.format(p0))
        debug('ar {}'.format(ar))
        debug('ar[:k] {}'.format(ar[:(k-k%2)//2]))
        return p0 + ar[:(k-k%2)//2]
    else: # can negative
        debug('negative')
        return sorted(P+M, key=lambda x: abs(x))[:k]


n, k = map(int, input().split())
P, M = [], [] # plus, minus
for a in map(int, input().split()):
    if a < 0: M.append(a)
    else: P.append(a)
ans, MOD = 1, 10**9 + 7
for a in solve(): ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
 
N, K = map(int, input().split())
A = list(map(int, input().split()))
M = 10**9 + 7
 
def prod(X):
    ans = 1
    for x in X:
        ans = ans * x % M
    return ans
 
def solve():
    # Case 1: N == K
    if N == K:
        return prod(A)
 
    # Case 2: ans is negative
    if all(a < 0 for a in A) and K % 2 == 1:
        return prod(sorted(A)[-K:])
 
    # Case 3: ans is positive
    posA = np.int64(sorted([a for a in A if a >= 0]))
    negA = np.int64(sorted([a for a in A if a < 0]))
 
    ans = 1
    if K % 2 == 1: # Keep the largest positive
        ans = ans * posA[-1] % M
        posA = posA[:-1]
    
    # Construct largest value by pairing items
    if len(posA) % 2 == 1: # Discard the one with smallest absolute value
        posA = posA[1:]
    if len(negA) % 2 == 1: # Discard the one with smallest absolute value
        negA = negA[:-1]
    pos_pairs = posA[0::2] * posA[1::2]
    neg_pairs = negA[0::2] * negA[1::2]
    pairs = np.concatenate([pos_pairs, neg_pairs], axis=0).tolist()
    pairs = sorted(pairs, reverse=True)[:K//2]
    ans = ans * prod(pairs) % M
 
    return ans
 
print(solve())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
a = LI()
a.sort(key = lambda x:abs(x), reverse = True)
ans = 1
p = 0
m = 0
plus = []
minus = []
use = []
f = 0
for i in range(n):
    if a[i] >= 0:
        p += 1
        if i < k:
            plus.append(a[i])
            use.append(a[i])
            ans *= a[i]
            ans %= mod
    else:
        m += 1
        if i < k:
            minus.append(a[i])
            f ^= 1
            use.append(a[i])
            ans *= -a[i]
            ans %= mod
if f:
    ans = -ans
if ans < 0:
    if k == n:
        print(ans % mod)
    elif p == 0:
        a.sort(key = lambda x:abs(x))
        ans = 1
        for i in range(k):
            ans *= -a[i]
            ans %= mod
        if k % 2:
            ans = -ans
        print(ans % mod)
    else:
        for i in range(k, n):
            if a[i] < 0:
                break
        else:
            ans = -ans
            ans *= pow(-minus[-1], mod-2, mod)
            ans *= max(a[k:])
            print(ans % mod)
            quit()
        if plus:
            ans = -ans
            ans *= pow(plus[-1], mod-2, mod)
            ans %= mod
            ans *= pow(-minus[-1], mod-2, mod)
            ans %= mod
            ans1 = plus[-1] * max(a[k:])
            ans2 = minus[-1] * min(a[k:])
            print(max(ans1, ans2) * ans % mod)
        else:
            ans = -ans
            ans *= pow(-minus[-1], mod-2, mod)
            ans %= mod
            ans *= max(a[k:])
            print(ans % mod)
else:
    print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7

n, k = map(int, input().split())
a = list(map(int, input().split()))
p, q = [], []
for x in a:
    if x >= 0: p.append(x)
    else: q.append(x)
lp, lq = len(p), len(q)

def sp():
    p.sort(reverse=True)
    q.sort()
    ans = p[0] if k % 2 else 1
    s = []
    for i in range(0, lq-1, 2):
        s.append(q[i]*q[i+1])
    for i in range(k % 2, lp-1, 2):
        s.append(p[i]*p[i+1])
    s.sort(reverse=True)
    for i in range(k//2):
        ans *= s[i]
        ans %= MOD
    print(ans)

def sq():
    a.sort(key=lambda x: abs(x))
    ans = 1
    for i in range(k):
        ans *= a[i]
        ans %= MOD
    print(ans)

if k % 2 and not p: sq()
elif n == k and lq % 2: sq()
else: sp()

Submission status: Accepted

Solution code:
from collections import deque #両端から取り出すのが速い
N,K = map(int,input().split())
A = list(map(int,input().split()))
pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(-a)
pos = deque(sorted(pos))
neg = deque(sorted(neg))
mod = 10**9+7
ans = 1
sign = 1
if K%2 == 1: #Kが奇数の時pos（ある場合）から必ず１つ取る
    if len(pos) > 0:
        ans = ans*pos.pop() % mod
    else:
        ans = ans*neg.popleft() % mod
        sign *= -1
    K -= 1
while K > 0: #偶数の場合と奇数の残りの処理
    if len(pos) == 1 and len(neg) == 1:
        ans = ans*-neg.pop()*pos.pop() % mod
    elif sign == 1:#通常バージョン
        if len(pos) < 2 or (len(neg) >= 2 and pos[-2]*pos[-1] < neg[-2]*neg[-1]):
            ans = ans*neg.pop()*neg.pop() % mod
        else:
            ans = ans*pos.pop()*pos.pop() % mod
    else:#奇数の前処理で負になっている場合(最終結果も負になるので小さくしたい)
        if len(pos) < 2 or (len(neg) >= 2 and pos[-2]*pos[-1] < neg[-2]*neg[-1]):
            ans = ans*neg.popleft()*neg.popleft() % mod
        else:
            ans = ans*pos.popleft()*pos.popleft() % mod
    K -= 2
ans = ans*sign % mod
print(ans)