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 functools import reduce

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return x2, y2, n

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

MOD = 10**9 + 7
N, K = map(int, input().split())
*A, = map(int, input().split())
A = sorted(A, key=abs, reverse=True)
cand = []
minus = False
last_plus, last_minus = None, None
for a in A[:K]:
    cand.append(a)
    if a < 0: minus = not minus; last_minus = a
    elif a > 0: last_plus = a
    else: minus = False
ans = reduce(lambda x, y: x * y % MOD, cand)
if minus and K != N:
    non_neg, neg = None, None
    for a in A[K:]:
        if a >= 0 and non_neg is None: non_neg = a
        elif a < 0 and neg is None: neg = a
        if non_neg is not None and neg is not None: break
    if non_neg is None:
        if last_plus:
            ans *= modular_inverse(last_plus, MOD) * neg; ans %= MOD
        else:
            ans = reduce(lambda x, y: x * y % MOD, A[::-1][:K])
    elif neg is None:
        ans *= modular_inverse(last_minus, MOD) * non_neg; ans %= MOD
    else:
        if last_plus and abs(last_plus * non_neg) < abs(last_minus * neg):
            ans *= modular_inverse(last_plus, MOD) * neg; ans %= MOD
        else:
            ans *= modular_inverse(last_minus, MOD) * non_neg; ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys

if(__name__ == "__main__"):

    N, K = map( int, input().strip().split() )
    divisor = 10**9+7
    list_a = list( map( int, input().strip().split() ) )
    multiplies = 1
    if(N==K):
        for i in range(N):
            multiplies = multiplies * list_a[i] % divisor
    else:
        list_a.sort()
        """
        解が負になるのはN>Kの時には
        正の項が1つもなく、Kが奇数の時
        """
        if(list_a[-1] < 0 and K % 2 != 0):
            """
            全て負の項
            list_a = [-5, -3, -1]のようにソートされている
            末尾の項から選んでいく
            """
            for i in range(K):
                multiplies = multiplies * list_a[N-1-i] % divisor
        elif(K==1):
            multiplies = list_a[N-1]
        else:
            left = 0
            right = N-1
            if(K%2!=0):
                multiplies = multiplies * list_a[right] % divisor
                right -= 1
            multiply_left = list_a[left] * list_a[left+1]
            multiply_right = list_a[right] * list_a[right-1]

            for s in range(K//2-1):
                if(multiply_left < multiply_right):
                    multiply_right %= divisor
                    multiplies = multiplies * multiply_right % divisor
                    right -= 2
                    multiply_right = list_a[right] * list_a[right-1]

                else:
                    multiply_left%=divisor
                    multiplies = multiplies * multiply_left % divisor
                    left += 2
                    multiply_left = list_a[left] * list_a[left+1]

            if(multiply_left < multiply_right):
                multiply_right %= divisor
                multiplies = multiplies * multiply_right % divisor

            else:
                multiply_left%=divisor
                multiplies = multiplies * multiply_left % divisor


    print(multiplies)

Submission status: Accepted

Solution code:
mod = 10**9+7
n, k = map(int, input().split())
a = [int(x) for x in input().split()]

pl = []
mn = []
zr = []

tmp = 1
cnt = 0

for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mn.append(-x)
    else:
        zr.append(x)

pl = sorted(pl, reverse=True)
mn = sorted(mn, reverse=True)

ans = 0

if n == k:
    ans = 1
    for i in range(n):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()

if len(mn) >= k and k % 2:
    tmp = 1
    for i in range(1, k+1):
        tmp *= mn[-i]
        tmp %= mod
    ans = -tmp

if len(zr) > 0:
    ans = max(0, ans)

pl_cum = [1]
for i, x in enumerate(pl):
    pl_cum.append(pl_cum[-1]*x % mod)

mn_cum = [1]
for i, x in enumerate(mn):
    mn_cum.append(mn_cum[-1]*x % mod)


for p in range(0, k+1, 2):
    if len(mn) < p:
        break
    first = False
    if len(pl) >= k-p:
        first = True
        pl_ind = k-p
        mn_ind = p
        break

if not first:
    print(ans % mod)
    exit()

while pl_ind-2 > -1 and mn_ind+1 < len(mn):
    if pl[pl_ind-1]*pl[pl_ind-2] <= mn[mn_ind]*mn[mn_ind+1]:
        pl_ind -= 2
        mn_ind += 2
    else:
        break

if pl_ind < 0:
    ans = mn_cum[mn_ind]
else:
    ans = pl_cum[pl_ind]*mn_cum[mn_ind]

print(ans % mod)

Submission status: Accepted

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

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, K, XS):
    "void()"

    posi = [x for x in XS if x >= 0]
    nega = [x for x in XS if x < 0]

    nega.sort(reverse=True)
    posi.sort()

    if K == N:
        # no choice
        ret = 1
        for i in range(N):
            ret *= XS[i]
            ret %= MOD
        return ret

    if not posi and K % 2:
        # negative answer
        # find smallest abs
        ret = 1
        for i in range(K):
            ret *= nega[i]
            ret %= MOD
        return ret

    ret = 1
    while K:
        # debug(": K, nega, posi", K, nega, posi)
        if K >= 2:
            if len(posi) >= 2:
                v = posi[-1] * posi[-2]
                if len(nega) >= 2:
                    w = nega[-1] * nega[-2]
                else:
                    w = -INF
                if v > w:
                    posi.pop()
                    posi.pop()
                    ret *= v
                    ret %= MOD
                else:
                    nega.pop()
                    nega.pop()
                    ret *= w
                    ret %= MOD

            else:
                w = nega[-1] * nega[-2]
                nega.pop()
                nega.pop()
                ret *= w
                ret %= MOD

            K -= 2
        else:
            ret *= posi[-1]
            ret %= MOD
            K -= 1
    return ret


def main():
    N, K = map(int, input().split())
    XS = list(map(int, input().split()))
    print(solve(N, K, XS))


T1 = """
4 2
1 2 -3 -4
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    12
    """


T2 = """
4 3
-1 -2 -3 -4
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    1000000001
    """


T3 = """
2 1
-1 1000000000
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    1000000000
    """


T4 = """
10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    999983200
    """


def _test():
    import doctest
    doctest.testmod()


T5 = """
3 2
1 1 -1
"""


def test_T5():
    """
    >>> as_input(T5)
    >>> main()
    1
    """


T6 = """
3 2
1 -1 -1
"""


def test_T6():
    """
    >>> as_input(T6)
    >>> main()
    1
    """


T7 = """
3 2
2 -1 -1
"""


def test_T7():
    """
    >>> as_input(T7)
    >>> main()
    1
    """


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
mod = 10**9+7
n, k = map(int, input().split())
a = [int(x) for x in input().split()]


def sgn(x):
    if x >= 0:
        return 0
    elif x < 0:
        return 1


pl = []
mn = []

for x in a:
    if x >= 0:
        pl.append(x)
    elif x < 0:
        mn.append(-x)

pl = sorted(pl, reverse=True)
mn = sorted(mn, reverse=True)


b = [(abs(a[i]), sgn(a[i])) for i in range(n)]
b = sorted(b, reverse=True)

c = [0, 0]
for i in range(k):
    c[b[i][1]] += 1


def solve(c):
    ans = 1
    for i in range(c[0]):
        ans *= pl[i]
        ans %= mod
    for i in range(c[1]):
        ans *= mn[i]
        ans %= mod
    if c[1] % 2:
        ans = (-ans) % mod
    return ans


if c[1] % 2 == 0:
    print(solve(c))
    exit()

if len(mn) == n and k % 2:
    tmp = 1
    for i in range(k):
        tmp *= mn[-i-1]
        tmp %= mod
    ans = -tmp
    print(ans % mod)
    exit()

ans = 0

chk1 = False
chk2 = False

if c[0] <= len(pl) - 1:
    chk1 = True

if 0 < c[0] and c[1] <= len(mn)-1:
    chk2 = True

if chk1 and chk2:
    tmp1 = pl[c[0]]*pl[c[0]-1]
    tmp2 = mn[c[1]]*mn[c[1]-1]
    if tmp1 > tmp2:
        c[0] += 1
        c[1] -= 1
        print(solve(c))
    else:
        c[0] -= 1
        c[1] += 1
        print(solve(c))
elif chk1:
    c[0] += 1
    c[1] -= 1
    print(solve(c))
elif chk2:
    c[0] -= 1
    c[1] += 1
    print(solve(c))
else:
    print(solve(c))

Submission status: Accepted

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

allm = True
for a in A:
    if a > 0:
        allm = False
        break

if N == K:
    ans = 1
    for a in A:
        ans = (ans*a) % MOD
    print(ans)
elif allm and K % 2 == 1:
    A.sort()
    A.reverse()
    ans = 1
    for a in A[:K]:
        ans = (ans*a) % MOD
    print(ans)
else:
    p, m = [], []
    for a in A:
        if a > 0:
            p.append(a)
        if a < 0:
            m.append(-a)
    p.sort(key=lambda k: -k)
    m.sort(key=lambda k: -k)

    pi, mi = 0, 0
    ans = 1
    while K > 0:
        if K == 1:
            ans = (ans*p[pi]) % MOD
            break
        elif pi < len(p)-1 or mi < len(m)-1:
            pv, mv = 0, 0
            if pi < len(p)-1:
                pv = p[pi]*p[pi+1]
            if mi < len(m)-1:
                mv = m[mi]*m[mi+1]

            if pv > mv:
                ans = (ans*pv) % MOD
                pi += 2
            else:
                ans = (ans*mv) % MOD
                mi += 2
            K -= 2
        else:
            ans = 0
            break
    print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
*A, = map(int, input().split())
p = 10**9 + 7
A.sort()
ans = 1
if A[n - 1] <= 0 and k % 2 == 1:
    for i in range(k):
        ans *= A[n - 1 - i]
        ans %= p
    print(ans)
    exit()
i = 0
j = n - 1
if k % 2 == 1:
    ans *= A[j]
    ans %= p
    j -= 1
    k -= 1
    n -= 1
for _ in range(k // 2):
    left = A[i] * A[i + 1]
    right = A[j] * A[j - 1]
    if (left > right):
        ans *= left
        ans %= p
        i += 2
    else:
        ans *= right
        ans %= p
        j -= 2
print(ans)

Submission status: Accepted

Solution code:
n , k = map(int, input().split())
a = list(map(int, input().split()))
neg = []
pos = []
mod = 10**9+7
for i in range(n):
    if a[i] >= 0:
        pos.append(a[i])
    else:
        neg.append(a[i])
neg.sort()
pos.sort(reverse = True)
if (len(pos) == 0 and k % 2 == 1) or n == k:
    ans = 1
    a.sort(reverse = True)
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans % mod)
else:
    #最大化するとき
    from collections import deque
    ans = 1
    neg_new = []
    for i in range(0, len(neg)//2):
        neg_new.append(neg[2*i] * neg[2*i+1])
    neg_new = deque(sorted(neg_new, reverse = True))
    pos = deque(pos)
    if k % 2 == 1:
        k -= 1
        ans = pos.popleft()
    else:
        ans = 1
    while k > 0:
        if len(pos) >= 2 and len(neg_new) >= 1:
            if pos[0] * pos[1] > neg_new[0]:
                ans *= pos.popleft() * pos.popleft()
            else:
                ans *= neg_new.popleft()
        elif len(pos) >= 2:
            ans *= pos.popleft() * pos.popleft()
        else:
            ans *= neg_new.popleft()
        k -= 2
        ans %= mod
    print(ans % mod)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9+7
a.sort()
mi = []
pl = []
if n == k:
    ans = 1
    for i in a:
        ans *= i
        ans %= mod
    print(ans)
    exit()
for i in a:
    if i < 0:
        mi.append(i)
    else:
        pl.append(i)
if pl == []:
    ans = 1
    count = 0
    if k%2:
        while count < k:
            ans *= a[-1-count]
            ans %= mod
            count += 1
    else:
        while count < k:
            ans *= a[count]
            ans %= mod
            count += 1
    print(ans)    
    exit()
pl = sorted(pl,reverse=True)
ip = 0
im = 0
if k%2:
    count = pl[0]
    k -= 1
    ip += 1
else:
    count = 1
while k > 0:
    check1 = True
    check2 = True
    if ip+2 <= len(pl):
        x = pl[ip]*pl[ip+1]    
    else:
        x = 1
        check1 = False
    if im+2 <= len(mi):
        y = mi[im]*mi[im+1]
    else:
        y = 1
        check2 = False
    if x > y or (check1 and not check2):
        ip += 2
        count = (x*count)%mod
    else:
        if check2:
            im += 2
            count = (y*count)%mod
    if check1 == False and check2 == False:
        break
    k -= 2

print(count%mod)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
MOD=10**9+7
p=[]
n=[]
for i in range(N):
    if A[i]<=0:
        n.append(A[i])
    else:
        p.append(A[i])
p.sort(reverse=True)
n.sort()
numplus=len(p)
if numplus==0:
    ans=1
    if K%2==1:
        for i in range(1,K+1):
            ans=(ans*n[i*(-1)])%MOD
    else:
        for i in range(K):
            ans=(ans*n[i])%MOD
elif N==K:
    ans=1
    for i in range(N):
        ans=(ans*A[i])%MOD
else:
    if numplus>=K:
        x=K
        if 0 in p:
            zero=p.index(0)
            len(p)-zero-1
    else:
        if (K-numplus)%2==1:
            x=numplus-1
        else:
            x=numplus
    ans=1
    for i in range(x):
        ans=(ans*p[i])%MOD
    for i in range(K-x):
        ans=(ans*n[i])%MOD
    temp=ans
    while x>1:
        if len(n)<(K-x+2):
            break
        if n[K-x]*n[K-x+1]<p[x-1]*p[x-2]:
            break
        temp=(temp*n[K-x]*n[K-x+1])%MOD
        temp=(temp*pow(p[x-1]*p[x-2],MOD-2,MOD))%MOD
        ans=temp
        x-=2
print(ans)

Submission status: Accepted

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

num_neg=0
num_pos=0
num_zero=0
aalist=[]
for a in alist:
  if a>0:
    num_pos+=1
  elif a<0:
    num_neg+=1
  else:
    num_zero+=1
  aalist.append((abs(a),a))
aalist.sort(reverse=True)
    
if N==K:
  answer=1
  for a in alist:
    answer*=a
    answer%=MOD
  print(answer)
  sys.exit(0)
  
pos_possible=True
if num_neg==N and K%2==1:
  pos_possible=False
    
if not pos_possible:
  aalist.sort()
  answer=1
  for i in range(K):
    aa,a=aalist[i]
    answer*=a
    answer%=MOD
  print(answer)
  sys.exit(0)
    
aalist.sort(reverse=True)
#print(aalist)
answer=1
sgn=1
pos_absmin=0
neg_absmin=0
for i in range(K):
  aa,a=aalist[i]
  answer*=a
  answer%=MOD
  if a>0:
    pos_absmin=a  
  elif a<0:
    neg_absmin=a
    sgn*=-1
  else:
    sgn=0

if sgn==0:
  print(0)    
elif sgn>0:
  print(answer)
else:
  pos_absmax=0
  neg_absmax=0
  for i in reversed(range(K,N)):
    aa,a=aalist[i]
    if a>0:
      pos_absmax=a
    else:
      neg_absmax=a
      
  #print(pos_absmin,neg_absmin,pos_absmax,neg_absmax)
  if pos_absmin==0:
    answer*=pos_absmax
    answer*=pow(neg_absmin%MOD,MOD-2,MOD)
    answer%=MOD
  elif neg_absmin==0:
    answer*=neg_absmax%MOD
    answer*=pow(pos_absmin,MOD-2,MOD)
    answer%=MOD
  elif pos_absmin*pos_absmax<neg_absmin*neg_absmax:
    answer*=neg_absmax%MOD
    answer*=pow(pos_absmin,MOD-2,MOD)
    answer%=MOD
  else:
    answer*=pos_absmax
    answer*=pow(neg_absmin%MOD,MOD-2,MOD)
    answer%=MOD
  
  print(answer)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True, key = lambda x: abs(x))
mod = 10**9+7
nega = 0
posi = 0
zero = 0
for i in range(n):
    if a[i] > 0:
        posi += 1
    elif a[i] == 0:
        zero += 1
    else:
        nega += 1

if n == k:
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod
    if nega%2 == 1:
        ans *= -1

elif posi == 0:

    if k % 2 == 0:
        ans = 1
        for i in range(k):
            ans *= abs(a[i])
            ans %= mod

    else:
        if zero > 0:
            ans = 0
        else:
            a.reverse()
            ans = 1
            for i in range(k):
                ans *= abs(a[i])
                ans %= mod

            ans *= -1


else:
    posi = 0
    nega = 0
    zero = 0
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod

    for i in range(k):
        if a[i] > 0:
            posi += 1
        elif a[i] < 0:
            nega += 1
        else:
            zero += 1

    if zero > 0:
        ans = 0

    elif nega % 2 != 0:
        minposi = 0
        minnega = 0
        for i in range(k-1, -1, -1):
            if a[i] > 0:
                if minposi == 0:
                    minposi = a[i]
            else:
                if minnega == 0:
                    minnega = a[i]

        maxposi = 0
        maxnega = 0
        for i in range(k, n):
            if a[i] > 0:
                if maxposi == 0:
                    maxposi = a[i]
            elif a[i] < 0:
                if maxnega == 0:
                    maxnega = a[i]


        if minposi == 0:
            ans *= pow(abs(minnega), mod-2, mod)
            ans *= abs(maxposi)

        elif abs(minposi*maxposi) <= abs(minnega*maxnega):
            ans *= pow(abs(minposi), mod-2, mod)
            ans *= abs(maxnega)

        else:
            ans *= pow(abs(minnega), mod-2, mod)
            ans *= abs(maxposi)



print(ans % mod)

Submission status: Accepted

Solution code:
import sys


def solve(n, k, aaa):
    MOD = 10 ** 9 + 7

    if n == k:
        ans = 1
        for a in aaa:
            ans = ans * a % MOD
        return ans

    pos = []  # Strictly, Non-neg
    neg = []
    for a in aaa:
        if a >= 0:
            pos.append(a)
        elif a < 0:
            neg.append(a)

    if len(pos) == 0:
        if k % 2 == 1:
            neg.sort(reverse=True)
        else:
            neg.sort()
        ans = 1
        for a in neg[:k]:
            ans = ans * a % MOD
        return ans

    pos.sort()
    neg.sort(reverse=True)
    ans = 1
    r = k

    if r % 2 == 1:
        ans = ans * pos.pop() % MOD
        r -= 1

    while r > 0:
        if len(pos) <= 1:
            ans = ans * neg.pop() * neg.pop() % MOD
        elif len(neg) <= 1:
            ans = ans * pos.pop() * pos.pop() % MOD
        else:
            pm = pos[-1] * pos[-2]
            nm = neg[-1] * neg[-2]
            if pm > nm:
                ans = ans * pos.pop() * pos.pop() % MOD
            else:
                ans = ans * neg.pop() * neg.pop() % MOD
        r -= 2

    return ans


n, k, *aaa = map(int, sys.stdin.buffer.read().split())
print(solve(n, k, aaa))

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:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, K = getlist()
	A = getlist()
	B = []
	for i in range(N):
		val = abs(A[i])
		if A[i] > 0:
			B.append([val , 1])
		elif A[i] < 0:
			B.append([val, -1])
		else:
			B.append([val, 0])
	B = sorted(B)

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

	M = 0; p = 0; m = 0; Aplus = []; Aminus = []; zerocnt = 0
	for i in A:
		if i == 0:
			zerocnt += 1
		elif i > 0:
			Aplus.append(i)
			M += 1; p += 1
		else:
			Aminus.append(i)
			M += 1; m += 1
	Aplus.sort()
	Aminus.sort()

	# 0が絶対に入る場合
	if K > M:
		print(0)
		return
	# マイナスになるから絶対ゼロを入れる場合
	if zerocnt > 0 and M == m and K % 2 == 1:
		print(0)
		return
	# マイナスのみの時の処理
	if m == N:
		if K % 2 == 0:
			ans = 1
			for i in range(K):
				ans *= Aminus[i]
				ans %= con
			print(ans)
			return
		else:
			ans = 1
			for i in range(K):
				ans *= Aminus[-1 - i]
				ans %= con
			print(ans)
			return

	# マイナスと0のとき
	if m == M:
		if K % 2 == 0:
			ans = 1
			for i in range(K):
				ans *= Aminus[i]
				ans %= con
			print(ans)
			return
		else:
			print(0)
			return

	pindPre = -100; pindAfter = INF
	mindPre = -100;	mindAfter = INF
	# print(B)

	for i in range(N - K):
		if B[i][1] == 1:
			pindPre = i
		elif B[i][1] == -1:
			mindPre = i

	for i in range(N - 1, N - K - 1, -1):
		if B[i][1] == 1:
			pindAfter = i
		elif B[i][1] == -1:
			mindAfter = i

	cnt = 0
	ans = 1
	for i in range(K):
		ans *= B[-1 - i][0]
		ans %= con
		if B[-1 - i][1] == -1:
			cnt += 1

	if cnt % 2 == 0:
		print(ans)
		return
	else:
		# ans *= -1
		ans %= con
		if mindPre >= 0 and pindPre >= 0 and pindAfter <= N and mindAfter <= N:
			if B[mindPre][0] * B[mindAfter][0] <= B[pindPre][0] * B[pindAfter][0]:
				ans *= B[pindPre][0] * pow(B[mindAfter][0], con - 2, con)
				ans %= con
			else:
				ans *= B[mindPre][0] * pow(B[pindAfter][0], con - 2, con)
				ans %= con
			print(ans)
			return

		elif pindPre >= 0 and mindAfter <= N:
			ans *= B[pindPre][0] * pow(B[mindAfter][0], con - 2, con)
			ans %= con
			print(ans)
			return
		elif mindPre >= 0 and pindAfter <= N:
			ans *= B[mindPre][0] * pow(B[pindAfter][0], con - 2, con)
			ans %= con
			print(ans)
			return
		else:
			print(0)
			return


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import math
import fractions
import collections
import itertools
import pprint
from collections import deque
N,K=map(int,input().split())
A=list(map(int,input().split()))
plist=[]
mlist=[]
ans=1
p=10**9+7
for i in range(N):
    if A[i]>=0:
        plist.append(A[i])
    else:
        mlist.append(A[i])
if len(plist)==0:
    if K%2==1:
        A.sort(reverse=True)
    else:
        A.sort()
    for i in range(K):
        ans=(ans*A[i])%p
    print(ans%p)
elif len(plist)==1:
    #print(plist,mlist)
    mlist.sort()
    if K%2==1:
        ans=plist[0]
    for i in range(K-1):
        ans=(ans*mlist[i])%p
    print(ans%p)
else:
    ans=1
    plist.sort(reverse=True)
    mlist.sort()
    pmap=deque()
    mmap=deque()
    if K%2==1:
        ans=plist[0]%p
        plist.pop(0)
        K=K-1
    #print(plist,mlist)
    for i in range(0,len(plist)-1,2):
        pmap.append(plist[i]*plist[i+1])
    if len(plist)>0:
        pres=plist[len(plist)-1]
    if len(mlist)>0:
        mres=mlist[len(mlist)-1]
    for i in range(0,len(mlist)-1,2):
        mmap.append(mlist[i]*mlist[i+1])
    #print(K)
    mapnum=K//2
    #print(mapnum)
    #print(pmap,mmap,ans)
    for i in range(mapnum):
        if (len(pmap)>0)and(len(mmap)>0):
            pl=pmap.popleft()
            mi=mmap.popleft()
            if pl>mi:
                ans=(ans*pl)%p
                mmap.appendleft(mi)
            else:
                ans=(ans*mi)%p
                pmap.appendleft(pl)
        elif (len(pmap)==0)and(len(mmap)>0):
            mi=mmap.popleft()
            ans = (ans *mi) % p
        elif (len(mmap)==0)and(len(pmap)>0):
            pl=pmap.popleft()
            ans = (ans *pl) % p
        else:
            ans=(ans*pres*mres)%p
    print(ans)

Submission status: Accepted

Solution code:
import math
import os 
def main(): #get the driver code
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
 
    a.sort()
    ret = 1
    if k % 2 == 0 or a[-1] >= 0:
        l = 0
        r = -1
        mlt1 = a[0] * a[1]
        mlt2 = a[-2] * a[-1]
        for _ in range(k//2):
            if mlt1 >= mlt2:
                ret *= mlt1 % mod
                l += 2
                if l <= n-2:
                    mlt1 = a[l+1] * a[l]
            else:
                ret *= mlt2 % mod
                r -= 2
                if r >= -n+1:
                    mlt2 = a[r-1] * a[r]
            ret %= mod
 
        if k % 2 == 1:
            ret *= a[r]
            ret %= mod
 
    else:
        for i in range(k):
            ret *= a[n-1-i]
            ret %= mod
 
    print(ret)
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter, deque

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

MOD = 10 ** 9 + 7

n_minus = 0
for a in A:
    if a < 0:
        n_minus += 1
if N == K:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
elif n_minus == N and K % 2 == 1:
    def f(x):
        if x == 0:
            return 10 ** 9
        else:
            return abs(x)


    A = sorted(A, key=f)
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD

    print(ans)
else:
    A = sorted(A, key=lambda x: abs(x), reverse=True)
    plus = deque()
    minus = deque()

    for i in range(K):
        if A[i] >= 0:
            plus.append(A[i])
        else:
            minus.append(A[i])

    if len(minus) % 2 == 1:
        if len(plus) == 0:
            minus.pop()
            for a in A[K:]:
                if a >= 0:
                    plus.append(a)
                    break
        else:
            p = None
            m = None
            for a in A[K:]:
                if a >= 0 and p is None:
                    p = a
                if a < 0 and m is None:
                    m = a
                if p is not None and m is not None:
                    break

            if m is None:
                minus.pop()
                plus.append(p)
            elif p is None:
                plus.pop()
                minus.append(m)
            elif minus[-1] * m > plus[-1] * p:
                plus.pop()
                minus.append(m)
            else:
                minus.pop()
                plus.append(p)

    ans = 1
    while plus:
        ans *= plus.popleft()
        ans %= MOD
    while minus:
        ans *= minus.popleft()
        ans %= MOD

    print(ans)

Submission status: Accepted

Solution code:
import copy

# a = get_int()
def get_int():
    return int(input())

# a = get_string()
def get_string():
    return input()

# a_list = get_int_list()
def get_int_list():
    return [int(x) for x in input().split()]

# a_list = get_string_list():
def get_string_list():
    return input().split()

# a, b = get_int_multi()
def get_int_multi():  # a, b = get_int_multi()
    return map(int, input().split())

# a_list = get_string_char_list()
def get_string_char_list():
    return list(str(input()))

# print("{} {}".format(a, b))
# for num in range(0, a):
# a_list[idx]
# a_list = [0] * a
'''
while (idx < n) and ():

    idx += 1
'''

def main():

    n, k = get_int_multi()
    a_list = get_int_list()

    p_list=[]
    m_list=[]
    for num in a_list:
        if num > 0:
            p_list.append(num)
        else :
            m_list.append(num)


    p_list.sort()
    m_list.sort(reverse=True)


    if k % 2 == 1:
        if (len(p_list) > 0):
            ans = p_list.pop()
            k -= 1
        else:
            m_list.sort()
            ans = m_list.pop()
            k -= 1
    else:
        ans = 1

    nokori = k
    while nokori > 0:
        if len(p_list) == 1 and len(m_list) == 1:
            ans = ans * p_list.pop() * m_list[0]
            del m_list[0]
            nokori -= 2
        else:
            if len(p_list) >= 2:
                pval = p_list[-1] * p_list[-2]
            else:
                pval = 0

            if len(m_list) >= 2:
                mval = m_list[-1] * m_list[-2]
            else:
                mval = 0

            if pval > mval:
                p_list.pop()
                p_list.pop()
                ans = ans * pval % 1000000007
            else:
                m_list.pop()
                m_list.pop()
                ans = ans * mval % 1000000007
            nokori -= 2

    print(ans % 1000000007)

if __name__ == '__main__':
    main()