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 bisect

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

n0, n1 = bisect.bisect_left(A, 0), bisect.bisect_left(A, 1)
if N - (n1 - n0) < K:
    print(0)
    exit()

m, z, p= n0, n1 - n0, N - n1
if K - p == min(K, m) and (K - p) % 2 == 1:
    ans = 1
    for a in sorted([abs(x) for x in A])[:K]:
        ans = (ans * a) % MOD
    print((-ans) % MOD)
else:
    if K % 2 != 0:
        ans, i, j = A[-1], N-2, 0
    else:
        ans, i, j = 1, N-1, 0
    
    for _ in range(K//2):
        if i <= n1:
            pos = False
        elif j >= n0-1:
            pos = True
        elif A[i] * A[i-1] > A[j] * A[j+1]:
            pos = True
        else:
            pos = False

        if pos:
            ans = (ans * ((A[i] * A[i-1]) % MOD)) %MOD
            i -= 2
        else:
            ans = (ans * ((A[j] * A[j+1]) % MOD)) %MOD
            j += 2
    print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
mod=10**9+7
P=1
if N==K:
  for i in range(N):
    P=P*A[i]%mod
  print(P)
  exit()
B=[]
C=False
for i in range(N):
  if A[i]:
    B.append(A[i])
  else:
    C=True
if len(B)<K:
  print(0)
  exit()
B.sort(reverse=True,key=lambda x:abs(x))
Y=0
for i in range(K):
  if B[i]<0:
    Y+=1
  P=P*B[i]%mod
if Y&1==0:
  print(P)
  exit()
if Y==K:
  B.sort()
  if B[-1]<0:
    if C:
      print(0)
      exit()
    P=1
    for i in range(K):
      P=P*B[-(i+1)]%mod
    print(P)
    exit()
  for i in range(K-1,-1,-1):
    if B[0]<0:
      P=P*pow(B[i],mod-2,mod)*B[-1]%mod
      break
  print(P)
  exit()
Y,Z=0,0
for i in range(K,len(B)):
  if B[i]<0:
    Y=B[i]
    break
for i in range(K,len(B)):
  if B[i]>0:
    Z=B[i]
    break
if Y==Z==0:
  if C:
    print(0)
  else:
    print(P)
  exit()
if Y==0:
  for i in range(K-1,-1,-1):
    if B[i]<0:
      P=P*pow(B[i],mod-2,mod)
      break
    if i==0:
      if C:
        print(0)
      else:
        print(P)
      exit()
  print(P*Z%mod)
elif Z==0:
  for i in range(K-1,-1,-1):
    if B[i]>0:
      P=P*pow(B[i],mod-2,mod)
      break
    if i==0:
      if C:
        print(0)
      else:
        print(P)
      exit()
  print(P*Y%mod)
if Y==0 or Z==0:
  exit()
V,W=0,0
for i in range(K-1,-1,-1):
  if B[i]<0:
    V=B[i]
    break
for i in range(K-1,-1,-1):
  if B[i]>0:
    W=B[i]
    break
if Y*V>Z*W:
  print(P*Y*pow(W,mod-2,mod)%mod)
else:
  print(P*Z*pow(V,mod-2,mod)%mod)

Submission status: Accepted

Solution code:
def main():
    MOD = 10 ** 9 + 7
    N, K = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    A.sort()
    if K == 1:
        print(A[N - 1])
        return
    # マイナスが0 or 1個の時はtop Kの積
    if A[1] >= 0:
        ans = 1
        for k in range(1, K + 1):
            ans *= A[-k]
            ans %= MOD
        print(ans)
        return
    # 非負が0個の場合
    # K:even -> tail Kの積
    # K:odd -> top Kの積
    if A[N - 1] < 0:
        ans = 1
        if K % 2 == 0:
            for k in range(K):
                ans *= A[k]
                ans %= MOD
        else:
            for k in range(1, K + 1):
                ans *= A[-k]
                ans %= MOD
        print(ans)
        return
    # 非負が1個の場合
    # K:even -> tail Kの積
    # K:odd -> tail (K - 1), top 1の積
    if A[N - 2] < 0 and A[N - 1] >= 0:
        ans = 1
        if K % 2 == 0:
            for k in range(K):
                ans *= A[k]
                ans %= MOD
        else:
            for k in range(1, K):
                ans *= A[-k]
                ans %= MOD
            ans *= A[N - 1]
            ans %= MOD
        print(ans)
        return
    # マイナスも非負も2つ以上ある場合
    # 両端から2要素ずつ走査していく
    left, right = 0, N - 1
    ans = 1
    while K >= 2:
        left_prod = A[left] * A[left + 1]
        right_prod = A[right - 1] * A[right]
        if left_prod < right_prod:
            ans *= right_prod
            right -= 2
        else:
            ans *= left_prod
            left += 2
        ans %= MOD
        K -= 2
    if K == 1:
        ans *= A[right]
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N, K = rl()
A = rl()

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

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

def get_positive():
	i, j = 0, 0
	ans = 1
	k = 0
	while k < K:
		if K == k+1:
			if i > len(plus)-1:
				return -1
			ans = (ans * plus[i]) % mod
			i += 1
			k += 1
		else:
			p, m = -1, -1
			if i <= len(plus)-2:
				p = plus[i]*plus[i+1]
			if j <= len(minus)-2:
				m = minus[j]*minus[j+1]
			if p < 0 and m < 0:
				return -1
			if p > m:
				ans = (ans * plus[i]) % mod
				i += 1
				k += 1
			else:
				ans = (ans * m) % mod
				j += 2
				k += 2
	return ans

def get_negative():
	plus.reverse()
	minus.reverse()
	i, j = 0, 1
	ans = minus[0]
	k = 1
	while k < K:
		if K == k+1:
			if i > len(plus)-1:
				print('ErrorX!')
				return -999
			ans = (ans * plus[i]) % mod
			i += 1
			k += 1
		else:
			p, m = float('inf'), float('inf')
			if i <= len(plus)-2:
				p = plus[i]*plus[i+1]
			if j <= len(minus)-2:
				m = minus[j]*minus[j+1]
			if p < 0 and m < 0:
				print('ErrorXX!')
				return -999
			if p < m:
				ans = (ans * plus[i]) % mod
				i += 1
				k += 1
			else:
				ans = (ans * m) % mod
				j += 2
				k += 2
	return ans

if N-K < len(zero):
	print(0)
	exit()
p = get_positive()
if p > 0:
	print(p % mod)
	exit()
if len(zero) > 0:
	print(0)
	exit()
n = get_negative()

print(n % mod)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


import math
n,k = map(int, input().split())
a = list(map(int, input().split()))
a1 = [item for item in a if item>0]
a2 = [item for item in a if item<0]
n1 = sum(item>0 for item in a)
n2 = sum(item<0 for item in a)
nz = sum(item==0 for item in a)
a1.sort(reverse=True)
a2.sort()
c1 = [math.log10(item) for item in a1]
c2 = [math.log10(-item) for item in a2]
def cumsum(a):
    """l[i] = sum(a[:i]) なるlを返す
    sum(a[i:j]) == l[j+1] - l[i]
    """
    c = 0
    l = [None] * (len(a)+1)
    for i,num in enumerate(a):
        l[i] = c
        c += num
    l[-1] = c
    return l
cc1 = cumsum(c1)
cc2 = cumsum(c2)
if n1+n2<k:
    ans = 0
else:
    best = -10**12
    ind = None
    for i in range(n2//2+1):
        # マイナスを偶数個
        if 2*i>k:
            continue
        if 2*i+n1<k:
            continue
        if k-2*i<=n1:
            val = cc2[2*i] + cc1[k-2*i]
            if val>best:
                ind = i
                best = val
    M = 10**9+7
    if ind is None:
        if nz>0:
            ans = 0
        else:
            # マイナスだけ
            ans = 1
            if k<=n2:
                for i in range(k):
                    ans *= a2[-(i+1)]
                    ans %= M
            else:
                for i in range(n2):
                    ans *= a2[i]
                    ans %= M
                for i in range(n1):
                    ans *= a1[i]
                    ans %= M
    else:
        ans = 1
        for i in range(2*ind):
            ans *= a2[i]
            ans %= M
        for i in range(k-2*ind):
            ans *= a1[i]
            ans %= M
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
minus = []
zero = 0
plus = []
for i in a:
    if i < 0:
        minus.append(i)
    elif i == 0:
        zero += 1
    else:
        plus.append(i)
minus.sort()
plus.sort(reverse=True)
len_plus = len(plus)
len_minus = len(minus)
if len_plus + len_minus < k:
    print(0)
    exit()
elif len_plus + len_minus == k:
    ans = 1
    for i in a:
        ans *= i
        ans %= mod
    print(ans)
    exit()
elif len_plus == 0:
    if k % 2:
        if zero:
            print(0)
        else:
            ans = 1
            cnt = 0
            for i in minus[::-1]:
                if cnt == k:
                    break
                ans *= i
                ans %= mod
                cnt += 1
            print(ans)
    else:
        ans = 1
        for i in minus[:k]:
            ans *= i
            ans %= mod
        print(ans)
    exit()
ans = 1
pl = min(k,len_plus - (k-len_plus) % 2)
mi = k-pl
for i in plus[:pl]:
    ans *= i
    ans %= mod
for i in minus[:k-pl]:
    ans *= i
    ans %= mod
for i in range(0,len_minus+1,2):
    if mi+i+1 >= len_minus or pl-i-2 < 0:
        break
    MINUS = minus[mi+i] * minus[mi+i+1]
    PLUS = plus[pl-i-1] * plus[pl-i-2]
    if MINUS < PLUS:
        break
    ans = (ans * MINUS * pow(PLUS, mod-2, mod)) % mod
print(ans)

Submission status: Accepted

Solution code:
mod = 10**9 + 7

def sgn(v):
    return (v > 0) - (v < 0)

def compute_answer():
    v.sort(key=abs, reverse=True)
    prod = 1
    sg = 1
    for a in xrange(k):
        prod *= v[a]
        prod %= mod
        sg *= sgn(v[a])

    if sg >= 0:
        return prod

    if max(v) <= 0:
        prod = 1
        for a in xrange(-k,0):
            prod *= v[a]
            prod %= mod
        return prod

    def find_pair(comp):
        i = k-1
        while i >= 0 and comp(v[i]): i -= 1
        j = k
        while j < n and not comp(v[j]): j += 1
        if j == n: j = i
        return i, j
    i, j = find_pair(lambda w: w >= 0)
    I, J = find_pair(lambda w: w <= 0)
    if I >= 0 and v[j] * v[I] < v[i] * v[J]:
        i = I
        j = J

    prod = v[j]
    for a in xrange(k):
        if a != i:
            prod *= v[a]
            prod %= mod
    return prod

n, k = map(int, raw_input().strip().split())
v = map(int, raw_input().strip().split())
print compute_answer()

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from scipy.sparse.csgraph import floyd_warshall
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush, heapify
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    a.sort()
    ans = 1
    cnt = 0
    l = 0
    r = n-1
    x = bisect.bisect_left(a,0)
    y = bisect.bisect_right(a,0)
    flag = 0
    if n == 1:
        print(a[0]%mod)
        return
    if n == 2:
        if k == 1:
            print((max(a[0],a[1]))%mod)
        else:
            print(a[0]*a[1]%mod)
        return
    if k == n:
        if x%2 == 0:
            flag = 1
    elif k == n-1:
        if x == n:
            if k%2 == 0:
                flag = 1
        else:
            if x%2 == 1:
                flag = 1
            else:
                if x != n:
                    flag = 1
    else:
        if x == n:
            if k%2 == 0:
                flag = 1
        else:
            flag = 1
    if flag:
        while True:
            if a[l+1] >= 0:
                ans *= a[r]
                ans %= mod
                cnt += 1
                r -= 1
            else:
                if a[l]*a[l+1] >= a[r]*a[r-1] and cnt < k-1:
                    ans *= a[l]
                    ans *= a[l+1]
                    ans %= mod
                    cnt += 2
                    l += 2
                else:
                    ans *= a[r]
                    ans %= mod
                    cnt += 1
                    r -= 1
            if cnt == k:
                break
        print(ans)
    else:
        if 0 in a:
            print(0)
            return
        for i in range(n):
            a[i] = abs(a[i])
        a.sort()
        for i in range(k):
            ans *= a[i]
            ans %= mod
        ans *= -1
        ans %= mod
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 7 + 10**9
    if N == K:
        r = 1
        for i in A:
            r *= i
            r %= mod
        return r % mod
    if max(A) <= 0 and K % 2 == 1:
        A.sort(reverse=True)
        r = 1
        for i in range(K):
            r *= A[i]
            r %= mod
        return r % mod
    a = []
    for i in A:
        a.append((abs(i), i))
    a.sort(reverse=True)
    cm = 0
    lp = None
    lm = None
    for i in range(K):
        if a[i][1] >= 0:
            lp = i
        else:
            lm = i
            cm += 1
    if cm % 2 == 0:
        r = 1
        for i in range(K):
            r *= a[i][1]
            r %= mod
        return r
    if not lp:
        r = 1
        for i in range(K-1):
            r *= a[i][1]
            r %= mod
        r *= max(A)
        return r % mod
    np = None
    nm = None
    for i in range(K, N):
        if a[i][1] >= 0 and not np:
            np = i
        if a[i][1] < 0 and not nm:
            nm = i
        if np and nm:
            break
    if not np:
        r = 1
        for i in range(K):
            if i != lp:
                r *= a[i][1]
                r %= mod
        r *= a[nm][1]
        return r % mod
    if not nm:
        r = 1
        for i in range(K):
            if i != lm:
                r *= a[i][1]
                r %= mod
        r *= a[np][1]
        return r % mod
    r = 1
    for i in range(K):
        if i not in (lp, lm):
            r *= a[i][1]
            r %= mod
    r *= max(a[np][1] * a[lp][1], a[lm][1] * a[nm][1])
    return r % mod
print(main())

Submission status: Accepted

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

b = [(abs(i), 1 if i >= 0 else -1) for i in a]

b = sorted(b)
b = list(reversed(b))
mod = int(1e9 + 7)

def fp(x,y):
	res=1
	while y > 0:
		if y % 2 == 1:
			res *= x
		x *= x
		y //= 2
		x %= mod
		res %= mod
	return res

def inv(x):
	return fp(x,mod-2)

p = 1
signe = 1
for i in range(k):
	p *= b[i][0]
	p %= mod
	if b[i][0] == 0:
		signe = 0
	signe *= b[i][1]

if signe >= 0:
	print(p % mod)
else:
	# choice between replacing the last positive by the next negative
	# and replacing the last negative by the next positive
	lastP, nextP, lastN, nextN = -1, -1, -1, -1
	for i in range(k):
		if b[i][0] * b[i][1] >= 0:
			lastP = i
		if b[i][0] * b[i][1] <= 0:
			lastN = i
	for i in range(k, n):
		if b[i][0] * b[i][1] >= 0 and nextP==-1:
			nextP = i
		if b[i][0] * b[i][1] <= 0 and nextN==-1:
			nextN = i
	if (lastP!=-1 and nextN !=-1) and (lastN!=-1 and nextP!=-1):
		if b[nextN][0] * b[lastN][0] >= b[nextP][0] * b[lastP][0]:
			ans = p * inv(b[lastP][0]) * b[nextN][0]
			ans %= mod
			print(ans)
		else:
			ans = p * inv(b[lastN][0]) * b[nextP][0]
			ans %= mod
			print(ans)
	elif lastP!=-1 and nextN!=-1:
		ans = p * inv(b[lastP][0]) * b[nextN][0]
		ans %= mod
		print(ans)
	elif lastN!=-1 and nextP!=-1:
		ans = p * inv(b[lastN][0]) * b[nextP][0]
		ans %= mod
		print(ans)
	else:
		# tout le monde est negatif
		a = list(reversed(sorted(a)))
		p = 1
		for i in range(k):
			p *= a[i]
			p %= mod
		print(p)

Submission status: Accepted

Solution code:
from functools import reduce
import operator
MOD = 10**9+7
mprod = lambda it: reduce(lambda x,y: (x*y)%MOD,it,1)
nprod = lambda it: reduce(lambda x,y: (x*y),it,1)


from fractions import Fraction

def solve(A,K):
    N = len(A)
    if N == K:
        return mprod(A)

    if all(v <= 0 for v in A) and K%2 == 1:
        A.sort()
        return mprod(A[-K:])

    A.sort(key=lambda x: abs(x))

    if A[-K] == 0:
        return 0

    parity = sum(v < 0 for v in A[-K:])%2
    if parity == 0:
        return mprod(A[-K:])

    rp = N-K
    while rp < N and A[rp] < 0:
        rp += 1

    rn = N-K
    while rn < N and A[rn] > 0:
        rn += 1


    lp = N-K-1
    while lp >= 0 and A[lp] < 0:
        lp -= 1

    ln = N-K-1
    while ln >= 0 and A[ln] > 0:
        ln -= 1

    if rp < N and ln >= 0:
        r1 = Fraction(-A[ln],A[rp])
    else:
        r1 = 0
    if rn < N and lp >= 0:
        r2 = Fraction(-A[lp],A[rn])
    else:
        r2 = 0
    if r1 > r2:
        return (mprod(A[-K:])*A[ln]*pow(A[rp],-1,MOD))%MOD
    else:
        return (mprod(A[-K:])*A[lp]*pow(A[rn],-1,MOD))%MOD

from itertools import combinations
def naive(A,K):
    return max(nprod(p) for p in combinations(A,K))%MOD


if __name__ == '__main__':
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    
    print(solve(A,K)%MOD)

    # from random import randrange

    # N = 9
    # K = 8
    # for _ in range(100000):
    #     A = [randrange(-8,8) for _ in range(N)]
    #     if solve(A.copy(),K) != naive(A.copy(), K):
    #         print(A, solve(A.copy(),K),naive(A.copy(), K) )

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
p = []
m = []
mod = 10**9 + 7
if n == k:
  ans = 1
  for x in a:
    ans *= x
    ans %= mod
  print(ans)
  exit()
zero = 0
for x in a:
  if x == 0:
    zero += 1
  if x > 0:
    p.append(x)
  else:
    m.append(-x)
p.sort(reverse=True)
m.sort(reverse=True)
#print(zero,p,m)
nowp = 0
nowm = 0
lenp = len(p)
lenm = len(m)
if k + zero > n:
  print(0)
  exit()
n -= zero
ans = 1
def inv(x):
  y = 1
  while x != 1:
    y *= mod // x + 1
    y %= mod
    x -= mod % x
  return y
pp = 0
for _ in range(k):
  if nowp == lenp:
    ans *= m[nowm]
    ans *= -1
    ans %= mod
    nowm += 1
    pp = 1-pp
  elif nowm == lenm:
    ans *= p[nowp]
    ans %= mod
    nowp += 1
  elif p[nowp] >= m[nowm]:
    ans *= p[nowp]
    ans %= mod
    nowp += 1
    #print('$$')
  else:
    ans *= m[nowm]
    ans *= -1
    ans %= mod
    nowm += 1
    pp = 1-pp
    #print('$')
  #print(pp,nowp,nowm)
#print(pp,ans)
if pp == 0:
  print(ans)
  exit()
if lenm == 0:
  print(ans)
  exit()
if lenp == 0:
  ans = 1
  m.reverse()
  for d in range(k):
    ans *= -m[d]
    ans %= mod
  print(ans)
  exit()
ans *= -1
ans %= mod
if lenp == nowp:
  ans *= inv(p[-1])
  ans *= m[nowm]
  ans %= mod
  print(ans)
  exit()
if lenm == nowm:
  ans *= inv(m[-1])
  ans *= p[nowp]
  ans %= mod
  print(ans)
  exit()
if nowp == 0:
  ans *= inv(m[nowm-1])
  ans *= p[0]
  ans %= mod
  print(ans)
  exit()
if nowm == 0:
  ans *= inv(p[nowp-1])
  ans *= m[0]
  ans %= mod
  print(ans)
  exit()
pl = p[nowp-1]
pr = p[nowp]
ml = m[nowm-1]
mr = m[nowm]
if mr * ml > pl * pr:
  ans *= inv(pl)
  ans *= mr
  ans %= mod
  print(ans)
else:
  ans *= inv(ml)
  ans *= pr
  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()))
canPositive = 0
Positive = 0
ans = 1
def inv(arg):
    return pow(arg,mod-2,mod)
for i in range(N):
    if A[i] >= 0:
        Positive += 1
if N - K >= 1 and Positive >= 1:
    canPositive = 1
if Positive == 0 and K % 2 == 0:
    canPositive = 1
anslist = []
if canPositive:
    A.sort(key=lambda x:abs(x),reverse=True)
    n = 0
    for a in A[:K]:
        anslist.append(a)
        if a < 0:
           n += 1
    if n % 2 == 1:
        minpos = 0
        minneg = 0
        maxpos = 0
        maxneg = 0
        for i in anslist[::-1]:
            if i > 0:
                minpos = i
                break
        for i in anslist[::-1]:
            if i < 0:
                minneg = i
                break
        for i in A[K:]:
            if i < 0:
                maxneg = i
                break
        for i in A[K:]:
            if i > 0:
                maxpos = i
                break
        if maxneg == 0 or minpos == 0:
            ans *= maxpos*inv(minneg) 
        elif maxpos == 0 or minneg == 0:
            ans *= maxneg*inv(minpos) 
        else:
            if abs(minpos*maxpos) > abs(maxneg*minneg):
                ans *= maxpos*inv(minneg) 
            else:
                ans *= maxneg*inv(minpos) 
else:
    A.sort(key=lambda x:abs(x))
    for a in A[:K]:
        anslist.append(a)
for i in anslist:
    ans *= i
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
n, k = map(int, input().split())
a_i = list(map(int, input().split()))
list.sort(a_i)
ans = 1
isminus = False
if k % 2 == 0:
    left = 0
    right = n - 1
else:
    left = 0
    right = n - 2
    ans *= a_i[n - 1]
if ans < 0: isminus = True
for x in range(k // 2):
    ans_L = a_i[left] * a_i[left + 1]
    ans_R = a_i[right] * a_i[right - 1]
    if (isminus == False and ans_L < ans_R) or (isminus == True and ans_L > ans_R):
        ans *= ans_R
        right -= 2
    else:
        ans *= ans_L
        left += 2
    if ans < 0 or ans >= mod: 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()))

if N == K:
    #全部かけて出力
    ans = 1
    for i in range(0,N,1):
        ans = (ans*A[i])%MOD
    print(ans)
    exit()

plus = []
minus = []
for i in range(0,N,1):
    if A[i] < 0:
        minus.append(-A[i])
    if A[i] > 0:
        plus.append(A[i])
    if A[i]==0:
        minus.append(0)
        plus.append(0)


if len(plus)==0 and K%2 == 1:
    minus.sort()
    ans = 1
    for i in range(0,K,1):
        ans = (ans*(-minus[i]))%MOD
    print(ans)
    exit()
        


#既に絶対値を格納
plus.sort(reverse=True)
minus.sort(reverse=True)

ans = 1
if K%2 ==1:#奇数
    ans = ans*plus[0]#一番でかいやつ
    plus.pop(0)

pairs = []
for i in range(1,len(plus),2):
    pairs.append(plus[i]*plus[i-1])
for i in range(1,len(minus),2):
    pairs.append(minus[i]*minus[i-1])
pairs.sort(reverse=True)
#でかいほうから K//2 こかける

for i in range(0,K//2,1):
    ans = (ans * pairs[i])%MOD

print(ans)

Submission status: Accepted

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

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

Mi = []
for a in A:
    if a != 0:
        Mi.append((abs(a), a//abs(a)))

Mi.sort(reverse=True)

if len(Mi) < K:
    ans = 0
else:
    ans = 1
    seg = 1
    lastinv = -1
    lastpu = -1
    for i in range(K):
        a, iv = Mi[i]
        seg *= iv
        if iv == -1:
            lastinv = a
        else:
            lastpu = a
        ans = ans * a % mod

    if seg == -1:
        fpu = -1
        fmi = -1
        ind = K
        while ind < len(Mi):
            a, iv = Mi[ind]
            ind += 1
            if iv == -1:
                if fmi == -1:
                    fmi = a
            else:
                if fpu == -1:
                    fpu = a
        
        if lastpu == -1:
            if fpu != -1:
                ans = ans * fpu * pow(lastinv, mod-2, mod) % mod
            elif 0 in A:
                ans = 0
            else:
                ans = -1
                for i in range(K):
                    ans = ans * Mi[-i-1][0] % mod
        elif fpu == -1 or fmi == -1:
            if fpu == -1 and fmi == -1:
                if 0 in A:
                    ans = 0
                else:
                    ans = -ans
            elif fpu == -1:
                ans = ans * fmi * pow(lastpu, mod-2, mod) % mod
            else:
                ans = ans * fpu * pow(lastinv, mod-2, mod) % mod
        elif lastpu * fpu > lastinv * fmi:
            ans = ans * fpu * pow(lastinv, mod-2, mod) % mod
        else:
            ans = ans * fmi * pow(lastpu, mod-2, mod) % mod
    
print(ans % mod)

Submission status: Accepted

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft



def main():
    n, k = map(int, input().split())
    a = sorted([(abs(i), (1 if i > 0 else -1)) for i in map(int, input().split())], reverse=True)
    if n == k:
        s = 1
        for x in a:
            s = s * x[0] * x[1] % mod
        print(s)
        return
    if len([i for i in a if i[1] == -1]) == n:
        if k % 2 == 0:
            s = 1
            for i in a[:k]:
                s = (s * i[0]) % mod
            print(s)
        else:
            s = 1
            for i in a[-k:]:
                s = (s * i[0]) % mod
            print((-s) % mod)
        return
    s = 1
    c = 1
    for i in range(k):
        s = s * a[i][0] % mod
        c *= a[i][1]
    if c == 1:
        print(s)
        return

    x_minus1 = -1
    x_plus1 = -1
    for i in range(k):
        if a[i][1] == -1:
            x_minus1 = a[i][0]
    for i in range(k, n):
        if a[i][1] == 1:
            x_plus1 = a[i][0]
            break

    x_minus2 = -1
    x_plus2 = -1
    for i in range(k):
        if a[i][1] == 1:
            x_minus2 = a[i][0]
    for i in range(k, n):
        if a[i][1] == -1:
            x_plus2 = a[i][0]
            break
    if x_minus1 == -1 or x_plus1 == -1:
        s = (s * inverse(x_minus2)) % mod * x_plus2 % mod
        print(s)
        return
    if x_minus2 == -1 or x_plus2 == -1:
        s = (s * inverse(x_minus1)) % mod * x_plus1 % mod
        print(s)
        return
    if x_plus1 * x_minus2 > x_plus2 * x_minus1:
        s = (s * inverse(x_minus1)) % mod * x_plus1 % mod
    else:
        s = (s * inverse(x_minus2)) % mod * x_plus2 % mod
    print(s)
main()

Submission status: Accepted

Solution code:
MOD = 10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
sign = dict({-1:0,0:0,1:0})
for a in A:
    if a<0:
        sign[-1]+=1
    elif a>0:
        sign[1]+=1
    else:
        sign[0]+=1
if sign[1]==0 and K%2!=0:
    A.sort(reverse=True)
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
elif sign[1]==0 and K%2==0:
    A.sort()
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
else:
    A.sort()
    ans = 1
    i,j = 0,N-1
    while K>0:
        if K>1 and A[i]*A[i+1]>=A[j]*A[j-1]:
            ans *= A[i]*A[i+1]
            ans %= MOD
            i += 2
            K -= 2
        else:
            ans *= A[j]
            ans %= MOD
            j -= 1
            K -= 1
print(ans)

Submission status: Accepted

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

A.sort()

mod = int(1e9+7)
AM = []
AP = []
AZC = 0
for a in A:
  if a < 0:
    AM.append(a)
  elif a == 0:
    AZC += 1
  else:
    AP.append(a)

#print(AM)
#print(AP)
#print(AZC)
# zero選ばないとだめならゼロ
if N-K < AZC:
  print(0)
  exit(0)

if N == K:
  wk = 1
  for a in A:
    wk *= a
    wk %= mod
  print(wk)
  exit(0)
  
# minusしか選べないケースってあるの？
# AMしかなくて、Kがodd
# zeroが一つでもあればZERO
if len(AP) == 0 and K%2 == 1:
  if AZC > 0:
    print(0)
  else:
    wk = 1
    for i in range(K):
      wk *= AM[-1-i]
      wk %= mod
    print(wk)
  exit(0)  
   
# plusを狙える
# K odd -> plus max 1
# K even -> ２個いちで選んで行ってMAXを
wk = 1
if K%2 == 1:
  wk *= AP.pop(-1)
  wk %= mod
  
K = K // 2
mi, pi = 0, 0
AP = AP[::-1]
while K>0:
  mwk = AM[mi] * AM[mi + 1] if mi + 1 < len(AM) else 0
  pwk = AP[pi] * AP[pi + 1] if pi + 1 < len(AP) else 0
  if mwk <= pwk:
    wk *= pwk % mod
    pi += 2
  else:
    wk *= mwk % mod
    mi += 2
  #print(wk)
  wk %= mod
  K -= 1
print(wk)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

pos = A[bisect_left(A, 0):]
pos.reverse()
neg = A[:bisect_left(A, 0)]

mod = 10**9+7
ans = 1
if len(pos) == 0 and K % 2 == 1:
    for i in range(K):
        ans *= neg[-i-1]
        ans %= mod
elif N == K:
    for i in range(K):
        ans *= A[i]
        ans %= mod
else:
    p, n = 0, 0
    for i in range(0, K-1, 2):
        v1 = 0
        v2 = 0
        if K % 2 == 0:
            if len(pos) >= p + 2:
                v1 = pos[p] * pos[p+1]
        else:
            if len(pos) >= p + 3:
                v1 = pos[p] * pos[p+1]

        if len(neg) >= n + 2:
            v2 = neg[n] * neg[n+1]

        if v2 > v1:
            ans *= v2
            ans %= mod
            n += 2
        else:
            ans *= v1
            ans %= mod
            p += 2

    if K % 2 == 1:
        ans *= pos[p]
        ans %= mod

print(ans)