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: Wrong Answer

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

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

ans = 1
mod = 10 ** 9 + 7

minus_cnt = 0
for a in A:
    if a < 0:
        minus_cnt += 1

if K == 1:
    print(max(A))
elif K == N:
    for a in A:
        ans *= abs(a)
        ans %= mod
    if minus_cnt % 2 == 1:
        ans *= (-1)
    print(ans % mod)
else:
    minus_cnt = 0
    new_A = []
    select_ls = []

    for a in A:
        new_A.append([abs(a), 0 if a >= 0 else -1])
    new_A.sort(reverse=True)

    for i in range(K):
        select_ls.append(new_A[i])
        minus_cnt += new_A[i][1]

    if minus_cnt % 2 == 0:
        for s in select_ls:
            ans *= s[0]
            ans %= mod
        print(ans)
    else:
        ok = False
        for i in range(K, N):
            if new_A[i][1] == 0:
                ok = True
                ans *= new_A[i][0]
                select_ls.sort()
                for j in range(1, len(select_ls)):
                    ans *= select_ls[j][0]
                    ans %= mod
                break
        if not ok:
            if 0 in A:
                print(0)
                exit()
            new_A.sort()
            for i in range(K):
                ans *= new_A[i][0]
                ans %= mod
        print(mod - ans)

Submission status: Wrong Answer

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

mod = 10**9 + 7

Am, Ap = [], []
pm = [0, 0, 0]
Flag = True

for x in A:
  if x < 0:
    Am.append(-x)
    pm[0] += 1
  elif x == 0:
    pm[1] += 1
  else:
    Ap.append(x)
    pm[2] += 1

Am.sort()
Ap.sort()
ans = 1

if N-K < pm[1]:
  print(0)
  exit()

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

if K == 1:
  print(Ap[-1])
  exit()

Bm = sorted(zip(Am, [1]*pm[0]))
Bp = sorted(zip(Ap, [0]*pm[2]))

B = Bm + Bp
B.sort(reverse = True)
cnt = 0

for i in range(K):
  if i == K-1:
    cnt %= 2
    if cnt != B[i][1]:
      break
    else:
      ans *= B[i][0]
      ans %= mod
      print(ans)
      exit()
  else:
    ans *= B[i][0]
    ans %= mod
    cnt += B[i][1]

ans1 = ans
ans2 = ans * B[K-1][0] % mod

mcnt1 = 0
for i in range(K, N-pm[1]):
  if B[i][1] == cnt:
    mcnt1 += 1
    ans1 *= B[i][0]
    ans1 %= mod
    break

for i in range(K-2, -1, -1):
  if B[i][1] == cnt:
    r = pow(B[i][0], mod-2, mod)
    ans1 *= r
    ans1 %= mod
    break

if mcnt1 == 1:
  print(max(ans1, ans2))
else:
  print(ans2)

Submission status: Wrong Answer

Solution code:
from collections import Counter, deque

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

MOD = 10 ** 9 + 7

c = Counter()
for a in A:
    if a == 0:
        c['0'] += 1
    elif a < 0:
        c['-'] += 1
    else:
        c['+'] += 1

if c['-'] + c['+'] < K:
    print(0)
elif (c['-'] == N and K % 2 == 1) or (N == K and c['-'] % 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])

    is_minus = False
    if len(minus) % 2 == 1:
        p = None
        m = None
        for i in range(K, N):
            if A[i] >= 0 and p is None:
                p = A[i]
            if A[i] < 0 and m is None:
                m = A[i]
            if p is not None and m is not None:
                break
        if m is None and p is None:
            pass
        elif len(plus) == 0:
            is_minus = True


            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)
        elif m is None and p is not None:
            minus.pop()
            plus.append(p)
        elif m is not None and 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

    if not is_minus:
        print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    n, k = i_map()
    num_list = i_list()

    plus_list = []
    minus_list = []
    zero_list = []

    for i in range(n):
        if num_list[i] == 0:
            zero_list.append(num_list[i])
        elif num_list[i] > 0:
            plus_list.append(num_list[i])
        else:
            minus_list.append(num_list[i])

    plus_list.sort(reverse=True)
    minus_list.sort(reverse=False)

    # print(plus_list)
    # print(minus_list)
    # print(zero_list)

    count = 1

    if len(minus_list) == 0:
        num_list.sort(reverse=True)
        for i in range(k):
            count *= num_list[i]
        print(count % MOD)
        exit()

    if len(plus_list) == 0:
        if k % 2 == 0:
            num_list.sort(reverse=False)
            for i in range(k):
                count *= num_list[i]
            print(count % MOD)
            exit()
        else:
            if num_list.count(0) >= 1:
                count = 0
            else:
                num_list.sort(reverse=True)
                for i in range(k):
                    count *= num_list[i]
            print(count % MOD)
            exit()

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    if n == k:
        ans = a[0]
        for i in a[1:]:
            ans *= i
            ans %= mod
        print(ans)
        return
    mi = []
    ma = []
    a.sort()
    for ai in a:
        if ai <= 0:
            heappush(mi, ai)
        else:
            heappush(ma, (-ai,1))
    X = []
    if not ma:
        ans = 1
        if k & 1:
            for i in range(k):
                ans *= a[-i - 1]
                ans %= mod
        else:
            for i in range(k):
                ans *= a[i]
                ans %= mod
        print(ans)
        return
    ans = 1
    while len(mi) >= 2:
        xx1 = heappop(mi)
        xy1 = heappop(mi)
        heappush(ma, (-xx1 * xy1, 2))
    t = 0

    while t < k and ma:
        tmp, xx = heappop(ma)
        if t + xx > k: continue
        ans *= -tmp
        t += xx
        ans %= mod

    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
# cook your dish here
b=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
ans=int(-1e18)
prod=1 
mod=int(1e9+7)
for i in range(0,b[1]): 
    prod*=a[i]
ans=max(prod,ans)
for i in range(0,b[0]-b[1]): 
    if a[i]:
        prod//=a[i]
    if prod==0:
        prod=1
    prod*=a[i+b[1]]
    ans=max(prod,ans)  
if ans<0:
    ans=(ans+mod)%mod 
else:
    ans%=mod 
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, bisect


if(__name__ == "__main__"):

    N, K = map( int, input().strip().split() )
    divisor = 10**9+7

    list_a = list( map(int, input().strip().split()) )

    """
    left, right側の2項の積で大きい方を選択
    選べるのが残り1項ならright側を選択
    """
    multiplies = 1

    if(N==K or N==1):
        for i in range(N):
            multiplies = multiplies * list_a[i] % divisor
        print(multiplies)
    else:
        list_a.sort()
        N_negative_numbers = bisect.bisect_left(list_a, 0)
        N_select_negatives = K + N_negative_numbers -N
        flag_overzero = True
        if(N_select_negatives > 0 and N_select_negatives % 2 != 0):
            flag_overzero = False
        if(flag_overzero == True):
            left = 0
            right = N-1

            multiply_right = list_a[right] * list_a[right-1]
            flag_left = True
            while(K>0):
                if(K>1):
                    K -= 2
                    if(flag_left==True):
                        multiply_left = list_a[left] * list_a[left+1]
                    else:
                        multiply_right = list_a[right] * list_a[right-1]

                    if(multiply_left > multiply_right):

                        multiply_left %= divisor
                        multiplies = multiplies * multiply_left % divisor
                        left += 2
                        flag_left=True

                    else:
                        multiply_right %= divisor
                        multiplies = multiplies * multiply_right % divisor
                        right -= 2
                        flag_left=False

                else:
                    multiplies = multiplies * list_a[right] % divisor
                    K =0
            print(multiplies)
        else:
            list_a = [ abs(list_a[i]) for i in range(N)]
            list_a.sort()
            for i in range(K-1):
                multiplies = multiplies * list_a[i] % divisor
            multiplies = (-1) * multiplies * list_a[K-1] % divisor

            print(multiplies)

Submission status: Wrong Answer

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

A.sort(reverse=True)

mod=(10**9+7)
p=1
t=0
for i in range(min([k//2,n-k])):
    if A[k-2*i]*A[k-2*i-1]<A[-2*i-1]*A[-2*i-2]:
        t+=1


for i in range(k-2*t):
    p=p*A[i]%mod
for i in range(2*t):
    p=p*A[-i-1]%mod


print(p)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
def l_in(type_): return list(map(type_, input().split()))
def i_in(): return int(input())
def m_in(type_): return map(type_, input().split())
def r_in(n, type_): return [type_(input()) for _ in range(n)]
ans = 0

mod = 1000000007
n, k = m_in(int)
a = l_in(int)
p = []
for res in combinations(a, k):
    total = 1
    for m in res: total *= m
    p.append(total)
ans = max(p)
ans %= mod

Submission status: Wrong Answer

Solution code:
from collections import deque
N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7
A=sorted(A)
if K==1:
    print(A[-1]%mod)
else:
    ans=1
    A=deque(A)
    if A[-1]<0 and K%2==1:
        for i in range(K):
            ans*=A[-1]
            A.pop()
    else:
        while K>=2:
            if A[0]*A[1]>=A[-1]*A[-2]:
                ans*= A[0]*A[1]
                K-=2
                A.popleft()
                A.popleft()
            else:
                ans*=A[-1]*A[-2]
                K-=2
                A.pop()
                A.pop()
        if N==1:
            if A[0]>=A[-1]:
                ans*=A[0]
            else:
                ans*=A[-1]
    
    print(ans%mod)

Submission status: Wrong Answer

Solution code:
def main():
    M=10**9+7
    n,k,*a=map(int,open(0).read().split())
    x,y=[],[]
    for i in a:
        if i>0:x.append(i)
        if i<0:y.append(i)
    if len(x)+len(y)<k or len(x)<k and (len(y)<k or not x) and (k-len(x))%2 and len(x)+len(y)<n:
        print(0)
        exit()
    if len(x)<k and (len(y)<k or not x) and (k-len(x))%2:
        x=sorted(x+[-i for i in y])[:k]
        x[0]*=-1
        c=1
        for i in x:
            c=c*i%M
        print(c)
        exit()
    x=sorted(x)[::-1][:k]
    y.sort()
    m=len(y)
    i=len(x)
    j=0
    if i<k:
        j=k-i
        x+=y[:j]
        j+=1
    while i>1 and j+1<m and x[i-1]*x[i-2]<y[j]*y[j+1]:
        x[i-1],x[i-2]=y[j],y[j+1]
        i-=2
        j+=2
    c=1
    for i in x:
        c=c*i%M
    print(c)
main()

Submission status: Wrong Answer

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

b=[]
c=[]
for i in range(n):
    b.append(abs(a[i]))
    if a[i]>0:
        c.append(1)
    else:
        c.append(-1)
d=zip(b,c)
e=sorted(d)

ans=1
for i in range(n-1,n-k-1,-1):
    ans*=b[i]*c[i]
    if i==n-k-1 and ans*a[i-1]<0:
        while(c[i]==1):
            i-=1
        if i==0 and c[i]<0:
            i=n-k-1
        ans*=b[i-1]*c[i-1]

temp=1
for i in range(k):
    temp*=b[i]*c[i]
ans=max(ans,temp)

print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
n, k = (int(x) for x in input().split())
A = list(int(x) for x in input().split())
MOD = 10**9 + 7
P = []
M = []
Z = []
for a in A:
    if a < 0:
        M.append(a)
    elif a > 0:
        P.append(a)
    else:
        Z.append(a)
P.sort()
M.sort(reverse=True)
lp = len(P)
lm = len(M)
lz = len(Z)

# どうしてもマイナスになるとき
if (lp + lm <= k and lm % 2 == 1) or (lp == 0 and k % 2 == 1):
    if lz > 0:
        print(0)
        exit()
    else:
        tmp = 1
        M.sort(reverse=True)
        count = 0
        for m in M:
            tmp *= m
            tmp %= MOD
            count += 1
            if count == k:
                break
        print(tmp % MOD)
        exit()

# プラスにできそうなとき
ans = 1
pindex = lp-1
mindex = lm-1
for _ in range(k // 2):
    if pindex > 0 and mindex > 0:
        p = P[pindex] * P[pindex - 1]
        m = M[mindex] * M[mindex - 1]
        if p > m:
            p %= MOD
            ans *= p
            ans %= MOD
            pindex -= 2
        else:
            m %= MOD
            ans *= m
            ans %= MOD
            mindex -= 2
    else:
        if pindex > 0:
            ans *= (P[pindex] * P[pindex - 1]) % MOD
            ans %= MOD
            pindex -= 2
        elif mindex > 0:
            ans *= (M[mindex] * M[mindex - 1]) % MOD
            ans %= MOD
            mindex -= 2
        else:
            print("ERROR!!!!")

if k % 2 == 0:
    print(ans)
    exit()
else:
    if pindex >= 0:
        ans *= P[pindex]
        ans %= MOD
        print(ans)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
def resolve():
    from bisect import bisect_left
    n,k=map(int,input().split())
    a=sorted(list(map(int,input().split())))
    m=bisect_left(a,0)
    MOD=10**9+7
    if m==0:
        ans=1
        for i in a[-k:]:
            ans=(ans*i)%MOD
    elif m==n:
        ans=1
        if k%2==0:
            for i in a[:k]:
                ans=(ans*i)%MOD
        else:
            for i in a[-k:]:
                ans=(ans*i)%MOD
    else:
        cal=1
        i=(m//2)*2
        for j in a[:i]:
            cal=(cal*j)%MOD
        if k-i>0:
            for j in a[-(k-i):]:
                cal=(cal*j)%MOD
        ans=cal
        for i in range((m//2)*2-2,-2,-2):
            if k-i>n-m:
                break
            for j in a[i-2:i]:
                cal=(cal*pow(j,MOD-2,MOD))%MOD
            if k-i>0:
                for j in a[-(k-i):-(k-i)+2]:
                    cal=(cal*j)%MOD
            ans=max(ans,cal)
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
N , K = map(int, input().split())
A =list(map(int, input().split()))
mod = 10**9 + 7
count =0
for k in range(len(A)):
    if A[k] == 0:
        count +=1
        A[k] = float("inf")
if N-count < K:
    print(0)
    exit()
A.sort()
A = A[:N-count]
A.sort(reverse=True)
#print(A)
ans = 1
plus = 0
minus = -1
countp = 0
countm = 0
if A[0] >0:
    for k in range(K):
        if abs(A[plus]) >= abs(A[minus]):
            ans = ans*A[plus]%mod
            plus+=1
        else:
            ans = ans*A[minus]%mod
            minus-=1
    if ans > 0:
        print(ans%mod)
    else:
        print(ans//A[minus+1]*A[plus]%mod)
else:
    for k in range(K):
        ans = ans*A[k]%mod
    print(ans%mod)

Submission status: Wrong Answer

Solution code:
import numpy as np
mod = 10 ** 9 + 7

n, k = map(int, input().split())
a = list(map(int, input().split()))
a_abs = list(map(abs, a))
a_sign = list(map(np.sign, a))
a_sort_idx = np.argsort(-np.array(a_abs))

plus = 0
minus = 0
zero = 0
for sign in a_sign:
    if sign == 0:
        zero += 1
    if sign == 1:
        plus += 1
    if sign == -1:
        minus += 1

def modinv(a):
    b = mod
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= mod
    if u < 0:
        u += m
    return u

def is_plus_possible():
    minus_div2 = minus // 2
    return (k - minus_div2 <= plus)

if is_plus_possible():
    flag = 1
    ans = 1
    last_sign_idx = [-1, -1]
    for i in range(k):
        flag *= a_sign[a_sort_idx[i]]
        ans = ans * a[a_sort_idx[i]] % mod
        if a_sign[a_sort_idx[i]] == 1:
            last_sign_idx[0] = i
        else:
            last_sign_idx[1] = i
    if flag == 1:
        print(ans)
        exit()
    else:
        last_sign = a_sign[a_sort_idx[k - 1]]
        rev_sign = last_sign * -1
        if last_sign == -1:
            if last_sign_idx[0] == -1:
                ans = ans * modinv(a[a_sort_idx[k - 1]]) % mod
                for i in range(k, n):
                    if a_sign[a_sort_idx[i]] == rev_sign:
                        ans = ans * a[a_sort_idx[i]] % mod
                        break
            print(ans)
            exit()
        else:
            big1 = a[a_sort_idx[k - 1]]
            big2 = a[a_sort_idx[last_sign_idx[0]]]
            small1, small2 = big1, big2
            for i in range(k, n):
                if a_sign[a_sort_idx[i]] == rev_sign:
                    small1 = a[a_sort_idx[i]]
                    break
            for i in range(k, n):
                if a_sign[a_sort_idx[i]] == last_sign:
                    small2 = a[a_sort_idx[i]]
                    break
            big, small = big1, small1
            if big1 / small1 >= big2 / small2:
                big, small = big2, small2
            ans = ans * modinv(big) % mod * small % mod
            print(ans)
            exit()
else:
    if zero > 0:
        print(0)
    else:
        a_abs.sort()
        ans = -1 % mod
        for i in range(k):
            ans = ans * a_abs[i] % mod
        print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    A_neg = [a for a in A if a < 0]
    A_zero = [a for a in A if a == 0]
    A_pos = [a for a in A if a > 0]

    A_neg.sort(reverse=True)
    A_pos.sort()

    if K > len(A_neg) + len(A_pos):
        print(0)
        return
    elif len(A_pos) == 0:
        if len(A_zero) > 0:
            print(0)
            return
        elif K % 2:
            ans = 1
            for a in A_neg[:K]:
                ans = (ans * a) % MOD
            print(ans)
            return
        else:
            ans = 1
            for a in A_neg[-K:]:
                ans = (ans * a) % MOD
            print(ans)
            return

    tmp_pos = []
    tmp_neg = []

    ans = 1
    neg = 0
    for i in range(K):
        if not A_neg:
            tmp_pos.append(A_pos[-1])
            ans = ans * A_pos.pop()
        elif not A_pos:
            tmp_neg.append(A_neg[-1])
            ans = ans * A_neg.pop()
            neg = 1 - neg
        elif -A_neg[-1] > A_pos[-1]:
            tmp_neg.append(A_neg[-1])
            ans = ans * A_neg.pop()
            neg = 1 - neg
        else:
            tmp_pos.append(A_pos[-1])
            ans = ans * A_pos.pop()

    if neg:
        if A_pos:
            ans = ans * pow(tmp_neg[-1], MOD - 2, MOD) * A_pos.pop() % MOD
        else:
            ans = ans * pow(tmp_pos[-1], MOD - 2, MOD) * A_neg.pop() % MOD

    print(ans % MOD)

    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

if K == 1:
    ans = max(A)
elif N == K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
elif max(A) <= 0 and K % 2 == 1:
    A.sort(reverse=True)
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
else:
    A.sort(key=abs)
    sign = 1
    ans = 1
    for _ in range(K - 2):
        a = A.pop()
        ans *= a
        ans %= MOD
        if a < 0:
            sign = -sign

    if sign < 0:
        A.sort()
        ans = ans * min(A[0] * A[1], A[-2] * A[-1], A[0] * A[-1])
    else:
        A.sort()
        ans = ans * max(A[0] * A[1], A[-2] * A[-1], A[0] * A[-1])

ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
minus_count=0
i=0
j=n-1
ans=1
count=0
MOD=(10**9)+7
#print(a)
while(count<k):
    if(count==k-1 and a[j]>0 and (abs(a[i]) > abs(a[j])) and minus_count%2==0 ):
        ans=((ans%MOD)*(a[j]%MOD))%MOD
        j-=1
    elif(a[i]==0 or a[j]==0):
        ans=0
        minus_count=0
        break
    elif(abs(a[i]) <= abs(a[j])):
        ans=((ans%MOD)*(a[j]%MOD))%MOD
        if(a[j]<0):
            minus_count+=1
        j-=1
    else:
        ans=((ans%MOD)*(a[i]%MOD))%MOD
        if(a[i]<0):
            minus_count+=1
        i+=1
#    print(i,j,ans)
    count+=1

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jul  5 21:33:15 2020

"""

N, K = map(int,input().split())
A = list(map(int, input().split())) 
A = sorted(A, key=abs, reverse=True)
mod = 10**9+7
ans = 1
lp = 10**6
lm = 10**6
lpflag = 0
lmflag = 0
rp = 10**6
rm = 10**6
rpflag = 0
rmflag = 0
ans1 = 0
ans2 = 0
minus = 0
flag0 = 0
for i in range(K):
    if A[i] < 0:
        minus = (minus+1)%2
    ans = ans * A[i] % mod
if not minus:
    print(ans)
else:
    for i in range(K-1,-1,-1):
        if lp < 10**6 and lm < 10**6:
            break
        if A[i] > 0 and lpflag == 0:
            lpflag = 1
            lp = i
        elif A[i] < 0 and lmflag == 0:
            lmflag = 1
            lm = i
    for i in range(K,N):
        if rp < 10**6 and rm < 10**6:
            break
        if A[i] > 0 and rpflag == 0:
            rpflag = 1
            rp = i
        elif A[i] < 0 and rmflag == 0:
            rmflag = 1
            rm = i
        elif A[i] == 0:
            flag0 = 1
    if lpflag*rmflag == 1:
        ans = 1
        for i in range(K):
            if not i == lp:
                ans = ans * A[i] % mod
        ans = ans * A[rm] % mod
        ans1 = ans
    if lmflag*rpflag == 1:
        ans = 1
        for i in range(K):
            if not i == lm:
                ans = ans * A[i] % mod
        ans = ans * A[rp] % mod    
        ans2 = ans
    if lpflag*rmflag == 0 and lmflag*rpflag == 0:
        ans = 1
        for i in range(N-1,N-1-K,-1):
            ans = ans * A[i] % mod
        if flag0:
            print(0)
        else:
            print(ans)

    else:
        if ans1 > 0 and ans2 > 0:
            if abs(A[rm]/A[lp]) > abs(A[rp]/A[lm]):
                print(ans1)
            else:
                print(ans2)
        else:
            print(max(ans1,ans2))

Submission status: Wrong Answer

Solution code:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
A.sort(key=lambda x: abs(x),reverse=True)
mod = 10**9+7
sign = 1
last_nega = -1
last_posi = -1

if N == 1:
    print(A[0]%mod)
else:
    if K == 1:
        print(max(A)%mod)
        exit()

    if all([a<0 for a in A]) and K%2:
        ans = 1
        for i in range(1,K+1):
            ans *= abs(A[-i])
            ans %= mod
        print(-ans%mod)
    else:
        for i in range(K):
            if A[i] < 0:
                last_nega = i
            elif 0 < A[i]:
                last_posi = i
            sign *= (1 if 0 < A[i] else (-1 if A[i] < 0 else 0))
        if sign == 0:
            print(0)
            exit()

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

            ans1 = -float('inf')
            ans2 = -float('inf')

            #Aが正負を一つずつもつならどっかに引っかかる(と思う)
            if last_nega != -1:
                ans1 = ans*pow(abs(A[last_nega]),mod-2,mod)
                ans1 %= mod
                for i in range(K,N):
                    if 0 <= A[i]:
                        ans1 *= A[i]
                        ans1 %= mod
                        break
                else:
                    ans1 = -float('inf')
            if last_posi != -1:
                ans2 = ans*pow(abs(A[last_posi]),mod-2,mod)
                ans2 %= mod
                for i in range(K,N):
                    if A[i] <= 0:
                        ans2 *= abs(A[i])
                        ans2 %= mod
                        break
                else:
                    ans2 = -float('inf')
            ans = max(ans1,ans2)
            print(ans%mod)

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9+7
a1 = []
a2 = []
cnt = 0
for i in a:
    if (i >= 0):
        a1.append(i)
    else:
        a2.append(-i)
a1.sort()
a2.sort()
#print(a1,a2)
if (k==1):
    print(max(a)%mod)
    exit()
if (n==k):
    ans = 1
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()
if (len(a1)==0):
    if (k%2==0):
        ans = 1
        for i in range(k):
            ans *= a2.pop()
            ans %= mod
        print(ans)
        exit()
    else:
        ans = 1
        for i in range(k):
            ans *= -a2[i]
            ans %= mod
        print(ans)
        exit()
elif (len(a2)==0):
    ans = 1
    for i in range(k):
        ans *= a1.pop()
        ans %= mod
    print(ans)
    exit()

bef1 = 10**10
bef2 = 10**10
index1 = 0
index2 = 0
ans = 1
for i in range(k):
    if (len(a1)==0):
        x = a2.pop()
        ans *= x
        ans %= mod
        index2 += 1
        cnt += 1
        continue
    if (len(a2)==0 or a1[-1]>=a2[-1]):
        x = a1.pop()
        ans *= x
        ans %= mod
        index1 += 1
        bef1 = x
    else:
        x = a2.pop()
        ans *= x
        ans %= mod
        index2 += 1
        cnt += 1
        bef2 = x
if (cnt%2==1):
    if len(a1)>0 and len(a2)>0:
        if (index1==0):
            ans *= a1[-1]
            ans *= pow(bef2,mod-2,mod)
            ans %= mod
        elif (index2==0):
            ans *= a2[-1]
            ans *= pow(bef1,mod-2,mod)
            ans %= mod
        else:
            A = a1[-1]/bef2
            B = a2[-1]/bef1
            if (A>=B):
                ans *= a1[-1]
                ans *= pow(bef2,mod-2,mod)
                ans %= mod
            else:
                ans *= a2[-1]
                ans *= pow(bef1,mod-2,mod)
                ans %= mod
    elif (len(a1)==0):
        ans *= a2[-1]
        ans *= pow(bef1,mod-2,mod)
        ans %= mod
    else:
        ans *= a1[-1]
        ans *= pow(bef2,mod-2,mod)
        ans %= mod
    
print(ans%mod)