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:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy

MAX = 10 ** 9 + 7

def prod_mod(la, mod):
  x = 1
  for a in la:
    x *= a
    x %= mod
  return x

def main():
  n, k = map(int, input().strip().split())
  la = numpy.array(list(map(int, input().strip().split())))
  la.sort()
  if n == k:
    print(prod_mod(la, MAX))
  else:
    if k % 2 == 1 and (la >= 0).sum() == 0:
      print(prod_mod(la[-k:], MAX))
    else:
      il, ir = 0, n-1
      cnt = 0
      l = []
      if k % 2 == 1:
        l.append(la[ir])
        ir -= 1
        cnt += 1
      while k - (cnt + 2) >= 0:
        if la[il] * la[il+1] > la[ir-1] * la[ir]:
          l.extend([la[il], la[il+1]])
          il += 2
        else:
          l.extend([la[ir-1], la[ir]])
          ir -= 2
        cnt += 2
      print(prod_mod(l, MAX))
      

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
M = []
m = []
for a in A:
    if a < 0:
        m.append(abs(a))
    else:
        M.append(a)

i = 0
j = 0
tmp = 1
P = 10**9 + 7

if (K%2 == 0 and (len(m)//2*2 + len(M)//2*2) >= K) or (K%2 == 1 and (len(M) + len(m)//2*2) >= K and len(M) > 0):
    m.sort(reverse=True)
    M.sort(reverse=True)
    while K > 0:
        if K >= 2:
            if j+2 <= len(M) and i+2 <= len(m):
                if m[i]*m[i+1] < M[j]*M[j+1]:
                    tmp *= M[j]
                    j += 1
                    K -= 1
                else:
                    tmp *= m[i]*m[i+1]
                    i += 2
                    K -= 2
            elif j+2 <= len(M):
                tmp *= M[j]
                j += 1
                K -= 1
            elif i+2 <= len(m):
                tmp *= m[i]*m[i+1]
                i += 2
                K -= 2
            else:
                tmp *= m[i]*M[j]
        else:
            tmp *= M[j]
            K -= 1
        tmp %= P
else:
    m.sort()
    M.sort()
    for _ in range(K):
        if j+1 <= len(M) and i+1 <= len(m):
            if M[j] < m[i]:
                tmp *= M[j]
                j += 1
            else:
                tmp *= m[i]
                i += 1
        elif j+1 <= len(M):
            tmp *= M[j]
            j += 1
        else:
            tmp *= m[i]
            i += 1
        tmp %= P
    tmp *= -1
    tmp %= P
        
print(tmp)

Submission status: Accepted

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


mod=10**9+7

if A[-1]<0 and k%2==1:
    now=1
    for i in range(k):
        now*=A[-i-1]%mod
        now%=mod
    print(now) ;exit()

l=0 ; r=n-1
ans=1
if k%2==1:
    ans=A[-1]
    r-=1

for i in range(k//2):
    mi=A[l]*A[l+1]
    pl=A[r]*A[r-1]
    if mi>pl:
        ans*= mi%mod
        ans%=mod
        l+=2
    else:
        ans*= pl%mod
        ans%=mod
        r-=2
print(ans%mod)

Submission status: Accepted

Solution code:
# AFTER EDITORIAL, WIP

def solve(ls, k, debug=0):
    modulo = 10 ** 9 + 7
    n = len(ls)
    n_neg = 0
    for i in range(n):
        n_neg += ls[i] < 0
    n_pos = n - n_neg

    # Sort by abs
    ls_abs = [abs(x) for x in ls]
    ls_abs_argsort = sorted(list(range(n)), key=lambda i: -ls_abs[i])

    # Check if positive result is impossible
    if n_neg >= k:
        positive = (k % 2 == 0) or (n_pos > 0)
    else:
        positive = (n_neg % 2 == 0) or (n > k)

    # If positive is impossible, pick "abs" small ones
    if not positive:
        p = 1
        for i in range(k):
            x = ls[ls_abs_argsort[-1 - i]]
            p *= x
            p %= modulo
        return p

    #
    # If positive is possible, ...
    #
    # PROP.
    #   At most one swap is needed for making product non-negative.
    #   PROOF. TODO
    #

    # Check sign when we pick "abs" large ones
    s = 1
    for i in range(k):
        x = ls[ls_abs_argsort[i]]
        s *= -1 if x < 0 else 1

    # If non-negative, we take as it is
    if s > 0:
        p = 1
        for i in range(k):
            x = ls[ls_abs_argsort[i]]
            p *= x
            p %= modulo
        return p

    # If negative, ...
    #   1. replace small negative with large positive, or
    #   2. replace small positive with large negative
    opt1 = None
    opt2 = None
    neg1 = pos1 = None
    pos2 = neg2 = None

    # Check if "1" is possible
    swap_pos = None
    for i in range(k, n):
        if ls[ls_abs_argsort[i]] >= 0:
            swap_pos = i
            pos1 = ls[ls_abs_argsort[i]]
            break

    swap_neg = None
    for i in range(k)[::-1]:
        if ls[ls_abs_argsort[i]] < 0:
            swap_neg = i
            neg1 = ls[ls_abs_argsort[i]]
            break

    if swap_pos is not None and swap_neg is not None:
        p = 1
        p *= ls[ls_abs_argsort[swap_pos]]
        p %= modulo
        for i in range(k):
            if i == swap_neg:
                continue
            x = ls[ls_abs_argsort[i]]
            p *= x
            p %= modulo
        opt1 = p

    # Check if "2" is possible
    swap_pos = None
    for i in range(k)[::-1]:
        if ls[ls_abs_argsort[i]] >= 0:
            swap_pos = i
            pos2 = ls[ls_abs_argsort[i]]
            break

    swap_neg = None
    for i in range(k, n):
        if ls[ls_abs_argsort[i]] < 0:
            swap_neg = i
            neg2 = ls[ls_abs_argsort[i]]
            break

    if swap_pos is not None and swap_neg is not None:
        p = 1
        p *= ls[ls_abs_argsort[swap_neg]]
        p %= modulo
        for i in range(k):
            if i == swap_pos:
                continue
            x = ls[ls_abs_argsort[i]]
            p *= x
            p %= modulo
            opt2 = p

    # Pick opt1 or opt2
    if opt1 is None:
        return opt2

    if opt2 is None:
        return opt1

    if pos1 * pos2 > neg1 * neg2:
        return opt1

    return opt2


def main(istr, ostr):
    n, k = list(map(int, istr.readline().strip().split()))
    ls = list(map(int, istr.readline().strip().split()))
    result = solve(ls, k)
    print(result, file=ostr)


if __name__ == "__main__":
    import sys

    main(sys.stdin, sys.stdout)

Submission status: Accepted

Solution code:

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

MOD = 10 ** 9 + 7

if K % 2 == 1 and all(v < 0 for v in X):
    # Minimize abs
    X.sort(key=lambda x: -x)
    ans = 1
    for i in range(K):
        ans = ans * X[i] % MOD
    print(ans)
elif K == N:
    ans = 1
    for i in range(K):
        ans = ans * X[i] % MOD
    print(ans)
else:
    pos = sorted(v for v in X if v >= 0)
    neg = sorted(-v for v in X if v < 0)

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

    cand = []
    while len(pos) >= 2:
        tmp = pos.pop() * pos.pop()
        cand.append(tmp)

    while len(neg) >= 2:
        tmp = neg.pop() * neg.pop()
        cand.append(tmp)

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

    print(ans)

Submission status: Accepted

Solution code:

import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def solve(a,k):
    a.sort()
    I = (np.abs(a)).argsort()
    a = a[I][::-1]
    if ( len(a) == k ): 
        return a
    if np.all( a<0 ):
        if ( k % 2 == 0 ):
            return a[:k]
        else:
            return a[-k:]
    p = a[a>=0]
    n = a[a<0]
    nums = [1]
    if k & 1:
        nums = [p[0]]
        p = p[1:]
        k -= 1
    if len(p) & 1:
        p = p[:-1]
    if len(n) & 1:
        n = n[:-1]
    p = p[::2] * p[1::2]
    n = n[::2] * n[1::2]
    a = np.concatenate([p,n])
    a.sort()
    a = a[::-1]
    return np.concatenate([nums,a[:k // 2]])

def main():
    n, k = map(int, readline().split())
    a = np.array(read().split(), np.int64)
    mod = 10**9 + 7
    b = solve(a,k).tolist()
    ans = 1
    for x in b:
        ans = ans * x % mod
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys


def resolve(in_):
    n, k = map(int, in_.readline().split())
    a = list(map(int, in_.readline().split()))
    mod = 10 ** 9 + 7
    assert n == len(a)
    # print(f'{n=} {k=} {len(a)=}')

    m = sorted(filter(lambda x: x < 0, a))
    p = sorted(filter(lambda x: x >= 0, a), reverse=True)

    if len(p) == 0:
        # print(f'{m=}')
        if k % 2:
            ans = m[-1] % mod
            for v in m[-k:-1]:
                v %= mod
                ans *= v
                ans %= mod
            return ans
        else:
            ans = m[0] % mod
            for v in m[1:k]:
                v %= mod
                ans *= v
                ans %= mod
            return ans
    elif len(m) == 0:
        ans = p[0] % mod
        for v in p[1:k]:
            v %= mod
            ans *= v
            ans %= mod
        return ans

    values = []
    p_index = 0
    m_index = 0
    for _ in range(k):
        if p_index < len(p) and m_index < len(m):
            if p[p_index] >= abs(m[m_index]):
                values.append(p[p_index])
                p_index += 1
            else:
                values.append(m[m_index])
                m_index += 1
        elif p_index >= len(p):
            values.append(m[m_index])
            m_index += 1
        elif m_index >= len(m):
            values.append(p[p_index])
            p_index += 1
        else:
            raise ValueError(f'{p_index=} {m_index=}')
    # print(f'{values[:10]=} {p[:10]=} {m[:10]=}')

    
    if any(v == 0 for v in values):
        return 0
    
    minus_values = sum(1 for v in values if v < 0)
    # print(f'{minus_values > 0 and minus_values % 2=}')
    if minus_values > 0 and minus_values % 2:
        x = None
        y = None
        minus_max = max((value for value in values if value < 0), default=None)
        plus_min = min((value for value in values if value >= 0), default=None)
        if len(p) > p_index and minus_max:
            # print(f'{p[p_index]=}')
            x = abs(p[p_index] + minus_max)
        if len(m) > m_index and plus_min:
            # print(f'{m[m_index]=}')
            y = abs(m[m_index] + plus_min)
        # print(f'{x=} {y=} {minus_max=} {plus_min=}')
        if x is None and y is None:
            pass
        elif x is None or y is None:
            if x is None:
                values.remove(plus_min)
                values.append(m[m_index])
            elif y is None:
                values.remove(minus_max)
                values.append(p[p_index])
        else:
            if x < y:
                values.remove(minus_max)
                values.append(p[p_index])
            elif x > y:
                values.remove(plus_min)
                values.append(m[m_index])
            elif abs(minus_max) < plus_min:
                values.remove(plus_min)
                values.append(m[m_index]) 
            else:
                values.remove(minus_max)
                values.append(p[p_index])
               

    ans = values[0] % mod
    for v in values[1:k]:
        v %= mod
        ans *= v
        ans %= mod
    
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

mod=10**9+7

if A[-1]<0 and k%2==1:
    now=1
    for i in range(k):
        now= now*A[-i-1]%mod
        # now%=mod
    print(now) ;exit()

l=0 ; r=n-1
ans=1
if k%2==1:
    ans=A[-1]
    r-=1

for i in range(k//2):
    mi=A[l]*A[l+1]
    pl=A[r]*A[r-1]
    if mi>pl:
        ans= ans*mi%mod
        l+=2
    else:
        ans= ans*pl%mod
        r-=2
print(ans%mod)

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# ------------------- fast io --------------------
from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y


for _ in range(int(input()) if not True else 1):
    n, k = map(int, input().split())
    #a, b = map(int, input().split())
    #c, d = map(int, input().split())
    a = list(map(int, input().split()))
    di = {}
    x = []
    for i in a:
        ab = abs(i)
        x += [ab]
        if ab not in di:
            di[ab] = []
        di[ab] += [1 if i>=0 else -1]

    x = sorted(x, reverse=True)
    signs = []
    for each in x:
        signs += [di[each].pop()]

    cursign = 1
    ans = 1
    firstpos = -1
    firstneg = 0
    nextpos = None
    nextneg = None
    for i in range(k):
        ans = (ans * x[i]) % (10**9+7)
        cursign *= signs[i]
        if signs[i] == 1:
            firstpos = i
        if signs[i] == -1:
            firstneg = i

    if cursign == 1:
        print(ans)
        quit()

    for i in range(k, len(x)):
        if signs[i] == 1 and nextpos is None:
            nextpos = i
        if signs[i] == -1 and nextneg is None:
            nextneg = i
    ansdex = [i for i in range(k)]
    from math import inf
    ans = ans*-1
    #print(ans)
    #print(nextpos)
    ans1, ans2 = -10**18, -10**18
    if nextpos is not None:
        ansd = [i for i in range(k)]
        ans22 = 1
        ansd[firstneg] = nextpos
        for each in ansd:
            ans22 = (ans22 * x[each]) % (10**9+7)
        ans2 = ans22

    if nextneg is not None and firstpos != -1:
        ansd = [i for i in range(k)]
        ans22 = 1
        ansd[firstpos] = nextneg
        for each in ansd:
            ans22 = (ans22 * x[each]) % (10 ** 9 + 7)
        ans1 = ans22
    if ans1 != -10**18 and ans2 != -10**18:
        print(ans1 if x[nextneg]/x[firstpos] > x[nextpos]/x[firstneg] else ans2 if x[nextneg]/x[firstpos] < x[nextpos]/x[firstneg] else max(ans1, ans2))
        quit()
    if ans1 != -10**18 or ans2 != -10**18:
        print(max(ans1, ans2))
        quit()

    a = sorted(a, reverse=True)
    ans=1
    for i in range(k):ans=(ans*(a[i])) % (10**9+7)
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
def prod(A,k,mod):
  ans = 1
  for i in range(k):
      ans *= A[i]
      ans %= mod
  return ans
def solve():
  N, K = map(int, input().split())
  A = list(map(int, input().split()))
  mod = 10**9+7
  ans = 1
  if K==N:
    return prod(A,N,mod)
  minus = len([a for a in A if a<0])
  if minus==N:
    if K%2==0:
      A.sort()
    else:
      A.sort(reverse=True)
    return prod(A,K,mod)
  if K==1:
    return max(A)
  A.sort(key=lambda x:-abs(x))
  if A[K]==0:
    return 0
  minus = len([a for a in A[:K] if a<0])
  flag = [1]*K+[0]*(N-K)
  d = defaultdict(lambda: -1)
  if minus%2==1:
    for i in range(K,N):
      if A[i]>=0:
        d['p2'] = i
        break
    for i in range(K,N):
      if A[i]<0:
        d['m2'] = i
        break
    for i in range(K-1,-1,-1):
      if A[i]>0:
        d['p1'] = i
        break
    for i in range(K-1,-1,-1):
      if A[i]<0:
        d['m1'] = i
        break
    if d['p2']==-1 or d['m1']==-1:
      flag[d['m2']],flag[d['p1']] = 1,0
    elif d['m2']==-1 or d['p1']==-1:
      flag[d['p2']],flag[d['m1']] = 1,0
    elif A[d['p2']]*A[d['p1']]>A[d['m1']]*A[d['m2']]:
        flag[d['p2']],flag[d['m1']] = 1,0
    else:
      flag[d['m2']],flag[d['p1']] = 1,0
    ans = 1
    for i in range(N):
      if flag[i]==1:
        ans *= A[i]
        ans %= mod
    return ans
  return prod(A,K,mod)
print(solve())

Submission status: Accepted

Solution code:
mod = 10**9+7

import sys
input = sys.stdin.buffer.readline

def main():

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

    PZ = []
    N = []
    for a in A:
        if a >= 0:
            PZ.append(a)
        else:
            N.append(a)

    flag = True
    if len(PZ) > 0:
        if n == k:
            if len(N)%2 != 0:
                flag = False
    else:
        if k%2 != 0:
            flag = False

    if flag:
        if k%2 == 0:
            PZ.sort(reverse=True)
            N.sort()
            s = len(PZ)
            t = len(N)
            C = []
            for i in range(s//2):
                C.append(PZ[2*i]*PZ[2*i+1])
            for i in range(t//2):
                C.append(N[2*i]*N[2*i+1])
            C.sort(reverse=True)
            ans = 1
            for i in range(k//2):
                ans *= C[i]
                ans %= mod
        else:
            PZ.sort()
            ans = PZ.pop()
            PZ.reverse()
            N.sort()
            s = len(PZ)
            t = len(N)
            C = []
            for i in range(s//2):
                C.append(PZ[2*i]*PZ[2*i+1])
            for i in range(t//2):
                C.append(N[2*i]*N[2*i+1])
            C.sort(reverse=True)
            for i in range(k//2):
                ans *= C[i]
                ans %= mod
    else:
        ABS = [abs(a) for a in A]
        ABS.sort()
        ans = 1
        for i in range(k):
            ans *= ABS[i]
            ans %= mod
        ans *= -1
        ans %= mod
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def func(A, n, k): 
    A.sort() 
    product = 1

    if (A[n - 1] == 0 and (k & 1)): 
        return 0

    if (A[n - 1] <= 0 and (k & 1)) : 
        for i in range(n - 1, n - k - 1, -1): 
            product = (product*A[i])%mod
        return product 

    i = 0
    j = n - 1
    if (k & 1): 
        product = (product*A[j])%mod 
        j-= 1
        k-=1

    k >>= 1
  
    for itr in range( k) : 
        left_product = A[i] * A[i + 1] 
 
        right_product = A[j] * A[j - 1] 
  
        if (left_product > right_product) : 
            product = (product*(left_product%mod))%mod
            i += 2
          
        else : 
            product = (product*(right_product%mod))%mod
            j -= 2
  
    return product 


n,k=map(int,input().split())
arr=list(map(int,input().split()))
global mod
mod=1000000007
ans=func(arr,n,k)
print(ans%mod)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
div=7+10**9
ans=1
t=0
i,j=0,N-1

if A[-1]<0 and K%2==1:
    for i1 in range(N-K,N):
        ans*=A[i1]
        ans%=div
else:
    while t<K-1:
        if A[i]*A[i+1]>A[j]*A[j-1]:
            ans*=A[i]*A[i+1]
            ans%=div
            i+=2
            t+=2
        else:
            ans*=A[j]
            ans%=div
            j+=-1
            t+=1
    if t==K-1:
        ans*=A[j]
        ans%=div

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = pow(10, 9) + 7
neg = 0
zero = 0
for i in range(n):
    if a[i] >= 0:
        if a[i] == 0:
            zero += 1
        a[i] = [a[i], 1]
    else:
        a[i] = [-a[i], 0]
        neg += 1
a.sort(reverse = True)
ans = 1
if n == k:
    for i in range(n):
        ans *= a[i][0]
        ans %= mod
        if not a[i][1]:
            ans *= -1
            ans %= mod
elif k % 2 == 1 and (neg == n or neg + zero == n):
    for i in range(1, k + 1):
        ans *= -a[-i][0]
        ans %= mod
else:
    pos, neg = 0, 0
    lastpos, lastneg = mod, mod
    for i in range(k):
        ans *= a[i][0]
        ans %= mod
        if a[i][1]:
            pos += 1
            lastpos = a[i][0]
        else:
            neg += 1
            lastneg = a[i][0]
    if neg % 2 == 1:
        firstpos, firstneg = mod, mod
        for i in range(k, n):
            if not firstpos == mod and not firstneg == mod:
                break
            if firstpos == mod and a[i][1]:
                firstpos = a[i][0]
            elif firstneg == mod and not a[i][1]:
                firstneg = a[i][0]
        if not mod in [lastpos, lastneg, firstpos, firstneg]:
            if firstpos * lastpos >= firstneg * lastneg:
                ans = ans * pow(lastneg, mod - 2, mod) * firstpos % mod
            else:
                ans = ans * pow(lastpos, mod - 2, mod) * firstneg % mod
        elif not mod in [lastpos, firstneg]:
            ans = ans * pow(lastpos, mod - 2, mod) * firstneg % mod
        elif not mod in [lastneg, firstpos]:
            ans = ans * pow(lastneg, mod - 2, mod) * firstpos % mod
print(ans)

Submission status: Accepted

Solution code:
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
M = 10**9 + 7
if N == K:
    result = 1
    for i in range(K):
        result = result * A[i] % M
    print(result)
    exit()
minus = [i for i in A if i <= 0]
l_minus = len(minus)
plus = [i for i in A if i > 0]
l_plus = len(plus)
plus.sort(reverse=1)
minus.sort()
if len(plus) == 0 and K % 2 == 1:
    result = 1
    for i in range(K):
        result = result * minus[-i-1] % M
    print(result)
    exit()

array = []
if K%2 == 1:
    array.append(plus.pop(0))
    l_plus -= 1
    K -= 1
m_x = 0
p_x = 0
max_mm = -1
if (m_x+1) * 2 <= l_minus:
    max_mm = minus[m_x * 2] * minus[m_x * 2 + 1]
max_pp = -1
if (p_x+1) * 2 <= l_plus:
    max_pp = plus[p_x * 2] * plus[p_x * 2 + 1]
counter = 0
\
while counter * 2 + 1 < K:
    if max_pp > max_mm:
        array.append(plus[p_x * 2])
        array.append(plus[p_x * 2 + 1])
        p_x += 1
        if (p_x+1) * 2 <= l_plus:
            max_pp = plus[p_x * 2] * plus[p_x * 2 + 1]
        else:
            max_pp = -1
 
    else:
        array.append(minus[m_x * 2])
        array.append(minus[m_x * 2 + 1])
        m_x += 1
        if (m_x+1) * 2 <= l_minus:
            max_mm = minus[m_x * 2] * minus[m_x * 2 + 1]
        else:
            max_mm = -1
    counter += 1

result = 1
for each in array:
    result = result * each % M
print(result)

Submission status: Accepted

Solution code:
def sgn(x):
    if x>0:
        return 1
    elif x<0:
        return -1
    else:
        return 0
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
mod=10**9+7
if K==N:
    ans=1
    for i in range(N):
        ans=ans*A[i]
        ans%=mod
    print(ans)
    exit()
if max(A)<0 and K%2==1:
    ans=1
    A.sort()
    for i in range(K):
        ans=ans*A[-i-1]
        ans%=mod
    print(ans)
    exit()
A.sort(key=lambda x:abs(x),reverse=True)
P=1
Pfugou=1
for i in range(K):
    P=P*A[i]
    P%=mod
    Pfugou=Pfugou*sgn(A[i])
if Pfugou!=-1:
    print(P)
    exit()
X=[]
Y=[]
for i in range(N):
    if A[i]>=0:
        X.append(A[i])
    else:
        Y.append(-A[i])
X.sort()
Y.sort()
S=[]
while(len(S)<K):
    if len(S)==K-1:
        S.append(X[-1])
        X.pop()
    elif len(X)<=1 and len(Y)<=1:
        #選んでないのが2個以下
        #len(S)<K<=N-1
        #len(S)=N-len(X)-len(Y)>=N-2
        #よってlen(S)=N-2,K=N-1
        #前述で処理済み
        #なのでここでやることはない
        pass
    elif len(X)<=1:
        S.append(Y[-1])
        S.append(Y[-2])
        Y.pop()
        Y.pop()
    elif len(Y)<=1:
        S.append(X[-1])
        S.append(X[-2])
        X.pop()
        X.pop()
    else:
        if X[-1]*X[-2]>Y[-1]*Y[-2]:
            S.append(X[-1])
            X.pop()
        else:
            S.append(Y[-1])
            S.append(Y[-2])
            Y.pop()
            Y.pop()
ans=1
for i in S:
    ans=ans*i
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
N, K = map(int, input().split())
A = sorted([int(i) for i in input().split()])

B = []
plus, zero, minus = 0, 0, 0
for i in range(N):
    if A[i] >= 0:
        B.append((A[i], 1))
        plus += 1
    elif A[i] == 0:
        B.append((0, 0))
        zero += 1
    else:
        B.append((-A[i], -1))
        minus += 1


if plus >= K-(min(K, minus)//2*2):
    B = sorted(B, key=lambda x: x[0], reverse=True)

    c = 1
    for i in range(K):
        c *= B[i][1]

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

    else:
        ap, an = 1, 1
        skip = []
        for i in range(K-1, -1, -1):
            if B[i][1] == 1:
                ap *= B[i][0]
                skip.append(i)
                break
        else:
            skip.append(K-1)
            an = 0
        for i in range(K-1, -1, -1):
            if B[i][1] == -1:
                an *= B[i][0]
                skip.append(i)
                break
        else:
            skip.append(K-1)
            ap = 0
        for i in range(K, N):
            if B[i][1] == 1:
                ap *= B[i][0]
                break
        for i in range(K, N):
            if B[i][1] == -1:
                an *= B[i][0]
                break
        a = max(ap, an)

        ans = 1
        for i in range(K):
            if i not in skip:
                ans *= B[i][0]
                ans %= MOD
        ans *= a
        ans %= MOD

elif zero >= K-(min(K, minus)//2*2):
    print(0)
    exit()

else:
    B = sorted(B, key=lambda x: x[0], reverse=False)
    ans = 1
    for i in range(K):
        ans *= B[i][0]*B[i][1]
        ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
mod=1000000007
n,k=map(int, input().split())
lst=list(map(int, input().split()))
lst=sorted(lst)
p=1
if lst[-1]==0 and k%2!=0:
    print(0)
elif lst[-1]<0 and k%2!=0:
    for i in range(n-1,n-k-1,-1):
        #print(p)
        p=(p%mod*lst[i]%mod)%mod
    #print(p)
    print(p%mod)
else:
    j=n-1
    if k%2!=0:
        p*=lst[j]
        k-=1
        j-=1
    k=k//2
    i=0
    for x in range(k):
        if lst[i]*lst[i+1]>lst[j]*lst[j-1]:
            p=(p%mod*lst[i]%mod*lst[i+1]%mod)%mod
            i+=2
        else:
            p=(p%mod*lst[j]%mod*lst[j-1]%mod)%mod
            j-=2
    #print(p)
    print(p%mod)

Submission status: Accepted

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

def main():
  A_posi = []
  A_nega = []
  for a in A:
    if a > 0:
      A_posi.append(a)
    elif a < 0:
      A_nega.append(-a)

  len_posi = len(A_posi)
  len_nega = len(A_nega)
  
  if len_posi + len_nega < K:
    return 0

  if (len_nega % 2 == 1 and K == len_posi + len_nega) or (K % 2 == 1 and len_posi == 0):
    if len_posi + len_nega == N:
      A_posi.sort()
      A_nega.sort()
      answer = 1
      k = 0
      for a in A_nega:
        answer *= (- a) % DE
        answer %= DE
        k += 1
        if k >= K:
          break
      else:
        for a in A_posi:
          answer *= a % DE
          answer %= DE
          k += 1
          if k >= K:
            break
      return answer
    else:
      return 0
  A_posi.sort(reverse=True)
  A_nega.sort(reverse=True)
  posi = 0
  nega = 0
  answer = 1

  if K % 2 == 1:
    answer = A_posi[0] % DE
    posi = 1

  while posi + nega + 2 <= K:
    p = A_posi[posi] * A_posi[posi + 1] if posi + 1 < len_posi else 0
    n = A_nega[nega] * A_nega[nega + 1] if nega + 1 < len_nega else 0
    if p > n:
      answer *= p % DE
      answer %= DE
      posi += 2
    else:
      answer *= n % DE
      answer %= DE
      nega += 2

  return answer

print(main())

Submission status: Accepted

Solution code:
"""
9 5
-4 -3 -2 -1 0 1 2 3
"""

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
Am = []
Ap = []
for a in A:
    if a < 0:
        Am.append(a)
    else:
        Ap.append(a)

mod = 10**9 + 7

ans = 1

if N == K:
    for a in A:
        ans *= a
        ans %= mod

elif A[-1] < 0:
    if K % 2 == 1:
        for i in range(K):
            ans *= Am[-1-i]
            ans %= mod
    else:
        for i in range(K):
            ans *= Am[i]
            ans %= mod

else:
    if K%2 == 1:
        ans *= Ap[-1]
        ans %= mod
        K -= 1
        del Ap[-1]
    Amd = []     
    Apd = []
    for i in range(len(Ap)//2):
        Apd.append(Ap[-1-(2*i)]*Ap[-1-(2*i+1)])
    for i in range(len(Am)//2):
        Amd.append(Am[2*i]*Am[2*i+1])
    Apd.append(-1)
    Amd.append(-1)
    
    ip = 0
    im = 0
    while K > 0:
        if Apd[ip] >= Amd[im]:
            ans *= Apd[ip]
            ip += 1
        else:
            ans *= Amd[im]
            im += 1
        ans %= mod
        K -= 2


ans %= mod
print(ans)