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:
import sys
from heapq import heappop, heappush
from collections import deque

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    mod = 7 + 10 ** 9
    q = []
    for a in A:
        if a < 0: heappush(q, (a, -1))
        else: heappush(q, (-a, 1))

    qu = deque()
    minus = -1
    plus = 1
    plusFound = False
    mc = 0
    ans = 1
    for i in range(K):
        a, pm = heappop(q)
        if pm == 1:
            plusFound = True
            ans *= plus
            ans %= mod
            plus = -a
        else:
            if mc == 1:
                ans *= (minus * a) % mod
                ans %= mod
            else:
                minus = a
            mc ^= 1
        qu.append((a, pm))
    if mc == 1:
        stock = 1
        for i in range(K, N):
            a, pm = heappop(q)
            if pm == 1:
                if stock == 1:
                    ans *= (-a * plus) % mod
                else:
                    if -a * plus >= (minus * stock): ans *= (-a * plus) % mod
                    else: ans *= (minus * stock) % mod
                print(ans % mod)
                break
            elif plusFound and stock == 1:
                stock = a
            qu.append((a, pm))
        else: #ここまで来るのは0以上の数が一つもない場合かK以降plusが現れない
            if stock < 1:
                ans *= (minus * stock) % mod
                print(ans % mod)
                return 0

            ans = 1
            for i in range(K):
                a, pm = qu.pop()
                ans *= a
                ans %= mod
            print(ans)
    else: 
        print((ans * plus) % mod)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

mod = 10**9+7

cp = 0
cm = 0
for i in range(N):
    n = 1
    if A[i] < 0:
        n = -1
    elif A[i] == 0:
        n = 0
    A[i] = (abs(A[i]), n)
    if n > 0:
        cp += 1
    elif n < 0:
        cm += 1

f = -1
for i in range(0, K+1, 2):
    if i <= cm and K-i <= cp:
        f = 1
        break


if K > cp+cm:
    ans = 0
elif f == -1:
    A.sort()
    ans = 1
    for i in range(K):
        ans *= A[i][0]
        ans %= mod
    ans *= -1
    ans %= mod
else:
    A.sort(reverse=True)
    c1 = 0
    c2 = 0
    ans = 1
    for i in range(K):
        ans *= A[i][0]
        ans %= mod
        if A[i][1] < 0:
            c1 += 1
        elif A[i][1] > 0:
            c2 += 1

    if c1 % 2 == 1:
        a1 = 1
        if c1 < cm and c2 > 0:
            for i in range(K, N):
                if A[i][1] < 0:
                    a1 *= A[i][0]
                    break
            for i in range(K-1, -1, -1):
                if A[i][1] > 0:
                    a1 /= A[i][0]
                    break
        else:
            a1 = -1
        a2 = 1
        if c2 < cp and c1 > 0:
            for i in range(K, N):
                if A[i][1] > 0:
                    a2 *= A[i][0]
                    break
            for i in range(K-1, -1, -1):
                if A[i][1] < 0:
                    a2 /= A[i][0]
                    break
        else:
            a2 = 0
        if a1 > a2 >= 0:
            for i in range(K, N):
                if A[i][1] < 0:
                    ans *= A[i][0]
                    break
            for i in range(K-1, -1, -1):
                if A[i][1] > 0:
                    ans *= pow(A[i][0], mod-2, mod)
                    ans %= mod
                    break
        elif a2 > a1 >= 0:
            for i in range(K, N):
                if A[i][1] > 0:
                    ans *= A[i][0]
                    break
            for i in range(K-1, -1, -1):
                if A[i][1] < 0:
                    ans *= pow(A[i][0], mod-2, mod)
                    ans %= mod
                    break
        else:
            ans = 0

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 1_000_000_007
sort_by_abs_A = sorted(A, key=lambda x: abs(x), reverse=True)
A_neg = sorted(filter(lambda x: x < 0, A), reverse=True)
ans = 1
if len(A_neg) == 0:
    for a in sort_by_abs_A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
elif len(A_neg) == N:
    for a in sort_by_abs_A[-K:]:
        ans *= a
        ans %= MOD
    print(ans)
else:
    is_neg = False
    last_positive_idx = -1
    last_negative_idx = -1
    muls = []
    for i, a in enumerate(sort_by_abs_A[:K]):
        if a < 0:
            is_neg = not is_neg
            last_negative_idx = i
        elif a > 0:
            last_positive_idx = i
        else:
            print(0)
            exit()
        ans *= a
        ans %= MOD
    if is_neg:
        pos_candidate = 0
        for a in sort_by_abs_A[K:]:
            if a > 0:
                pos_candidate = a
                break
        neg_candidate = 0
        for a in sort_by_abs_A[K:]:
            if a < 0:
                neg_candidate = a
                break
        if (
            pos_candidate / sort_by_abs_A[last_negative_idx]
            > neg_candidate / sort_by_abs_A[last_negative_idx]
        ):
            ans *= pow(sort_by_abs_A[last_negative_idx], MOD - 2, MOD)
            ans %= MOD
            ans *= pos_candidate
            ans %= MOD
        else:
            ans *= pow(sort_by_abs_A[last_positive_idx], MOD - 2, MOD)
            ans %= MOD
            ans *= neg_candidate
            ans %= MOD
    print(ans)

Submission status: Wrong Answer

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

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

mod = 10**9 + 7

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

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

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

plus = []
minus = []
zero = []

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

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

plus = [1]+plus
minus = [1]+minus

ans = 0
s = 1 if K%2 else 0
p = -1
for i in range(s,len(plus)+1):
    p1 = i
    p2 = K-i
    if p < 0 and 0 <= p1 <= len(plus)-1 and 0 <= p2 <= len(minus)-1:
        p = i
    if 0 <= i <= len(plus)-1 and 0 <= i-1 <= len(plus)-1 and 0 <= K-i+1 <= len(minus)-1 and 0 <= K-i+2 <= len(minus)-1:
        if plus[i]*plus[i-1] > minus[K-i+1]*minus[K-i+2]:
            p = i
            continue
        else:
            break
    else:
        continue

if p >= 0:
    temp = 1
    for i in range(p):
        temp *= plus[i+1]
        temp %= mod
    for i in range(K-p):
        temp *= minus[i+1]
        temp %= mod

    if temp > ans:
        ans = temp

if ans > 0:
    print(ans)
    exit()

if len(zero):
    print(0)
    exit()

plus = list(reversed(plus))
plus.pop()
plus = [1] + plus
minus = list(reversed(minus))
minus.pop()
minus = [1] + minus

ans = 0
s = 0 if K%2 else 1
p = -1
for i in range(s,len(plus)+1):
    p1 = i
    p2 = K-i
    if p < 0 and 0 <= p1 <= len(plus)-1 and 0 <= p2 <= len(minus)-1:
        p = i
    if 0 <= i <= len(plus)-1 and 0 <= i-1 <= len(plus)-1 and 0 <= K-i+1 <= len(minus)-1 and 0 <= K-i+2 <= len(minus)-1:
        if plus[i]*plus[i-1] > minus[K-i+1]*minus[K-i+2]:
            p = i
            continue
    else:
        continue

temp = -1
for i in range(p):
    temp *= plus[i+1]
    temp %= mod
for i in range(K-p):
    temp *= minus[i+1]
    temp %= mod

print(temp%mod)

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
    LL = 0
    while t < k and ma:
        tmp, xx = heappop(ma)
        if xx == 1:
            LL = tmp
        if t + xx > k:
            while t < k and ma:
                tmp1, xx = heappop(ma)
                if xx == 1:
                    if tmp1 * LL >= tmp:
                        ans *= LL
                        ans %= mod
                        print(ans)
                        return
                    else:
                        ans *= pow(LL, mod - 2, mod)
                        ans *= tmp
                        ans %= mod
                        print(ans)
                        return
        ans *= -tmp
        t += xx
        ans %= mod

    print(ans)
    return


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

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7

positive = []
negative = []
zero = 0
for t in a:
    if t < 0:
        negative.append(t)
    elif t == 0:
        positive.append(0)
        zero += 1
    else:
        positive.append(t)
if n - zero < k:
    print(0)
    exit()

positive.sort()
negative.sort(reverse=True)

if not positive:
    ans = 1
    if k % 2 == 1:
        if zero != 0:
            print(0)
            exit()
        for i in range(k):
            ans *= negative[i]
            ans %= mod
    else:
        for i in range(k):
            ans *= negative.pop()
            ans %= mod
    print(ans)
    exit()

ans = 1
# negative 処理
check = []
if len(negative) % 2 == 1:
    negative = negative[1:]
while negative:
    check.append(negative.pop() * negative.pop())

# positive
if k % 2 == 1:
    ans *= positive.pop()
    k -= 1

if len(positive) % 2 == 1:
    positive = positive[1:]
while positive:
    check.append(positive.pop() * positive.pop())
check.sort()


for i in range(k//2):
    if check:
        ans *= check.pop()
    else:
        print(0)
        exit()
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, k = map(int, input().split())
a = list( map(int, input().split()))
p = 10**9+7

a.sort()

from bisect import bisect_left, bisect_right
# A = [1, 2, 3, 3, 3, 4, 4, 6, 6, 6, 6]
zerostart = bisect_left(a, 0) # 2 最も左(前)の挿入箇所が返ってきている
posstart = bisect_right(a, 0) # 5

aneg = a[:zerostart]
cntzero = posstart - zerostart
apos = a[posstart:]


cntneg = len(aneg)
cntpos = len(apos)

# 答えが0になる時
if k > n-cntzero:
    print(0)
    exit()

cntneg = len(aneg)
cntpos = len(apos)

mix = [(-neg,-1) for neg in aneg] + [(pos,1) for pos in apos]
mix.sort(key=lambda x:x[0],reverse=True)



# 答えが正になる時
if k <= cntpos or (k%2==0 and  k <= (cntneg//2)*2 + cntpos) or (k%2==1 and cntpos%2==1 and k <= (cntneg//2)*2 + cntpos-1):
    pos_pair_mix=[]
    apos.sort(reverse=True)
    for i in range(cntpos//2):
        pos_pair_mix.append((apos[2*i]*apos[2*i+1],+1,i))

    for i in range(cntneg//2):
        pos_pair_mix.append((aneg[2*i]*aneg[2*i+1],-1,i))

    pos_pair_mix.sort(key=lambda x:x[0],reverse=True)

    ans = 1
    last_apos=0

    for i in range(k//2):
        ans*=pos_pair_mix[i][0]%p
        ans%=p
        if pos_pair_mix[i][1]==1:
            last_apos = pos_pair_mix[i][2]+1
    if k%2==0:
        print(ans)
        exit()
    else:
        print((ans*apos[last_apos])%p)
        exit()

# 答えが負になる時
mix = [(neg,-neg,-1) for neg in aneg] + [(pos,1) for pos in apos]
mix.sort(key=lambda x:x[1])

ans = 1
for i in range(k-cntzero):
    ans*=mix[i][0]
    ans%=p

if ans <0 and cntzero>0:
    ans = 0

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a, key = abs)[::-1]
ans = 1
hold = 0

if max(a) < 0:
    a = sorted(a)[::-1]
    for i in range(k):
        ans = ans*a[i]%(10**9 + 7)
    print(ans)
    exit()



for i in range(k - 1):
    if a[i] > 0:
        ans = ans*a[i]%(10**9 + 7)
    else:
        if hold == 0:
            hold = a[i]
        else:
            ans = ans*a[i]*hold%(10**9 + 7)
            hold = 0

for j in range(k - 1, n):
    if a[j] < 0 and hold != 0:
        ans = ans*a[j]*hold%(10**9 + 7)
        print(ans)
        exit()
    elif a[j] > 0:
        ans = ans*a[j]%(10**9 + 7)
        print(ans)
        exit()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import os
from sys import stdin, stdout

MOD = int(1e9+7)

def solve(tc):
    n, k = map(int, stdin.readline().split())
    seq = list(map(int, stdin.readline().split()))

    seq = sorted(seq, key=lambda x: abs(x), reverse=True)

    contain_zero = False
    last_plus = -1
    last_minus = -1
    mul_minus = False

    arr = []
    p = 0
    while p < n and len(arr) < k:
        if seq[p] == 0:
            contain_zero = True
            p += 1
            continue

        if seq[p] < 0:
            last_minus = len(arr)
            mul_minus ^= True
        elif seq[p] > 0:
            last_plus = len(arr)

        arr.append(seq[p])
        p += 1

    # should contain zeros
    if p == n and len(arr)<k:
        print(0)
        return

    # found maximal
    if not mul_minus:
        ans = 1
        for num in arr:
            ans *= num
            ans %= MOD
        print(ans)
        return

    first_plus = -1
    first_minus = -1
    while p < n:
        if seq[p]==0:
            contain_zero = True
            p += 1
            continue

        if seq[p] < 0:
            if first_minus < 0:
                first_minus = p
        elif seq[p] > 0:
            if first_plus < 0:
                first_plus = p
        p += 1

    if last_plus < 0 and first_plus < 0:
        if contain_zero:
            print(0)
        else:
            ans = 1
            for i in range(n-1, n-k-1, -1):
                ans *= seq[i]
                ans %= MOD
            print(ans)
        return

    if first_minus < 0:
        arr[last_minus] = seq[first_plus]
    elif first_plus < 0:
        arr[last_plus] = seq[first_minus]
    else:
        if seq[first_plus]*arr[last_plus] < seq[first_minus]*arr[last_minus]:
            arr[last_plus] = seq[first_minus]
        else:
            arr[last_minus] = seq[first_plus]

    ans = 1
    for num in arr:
        ans *= num
        ans %= MOD
    print(ans)


tcs = 1
tc = 1
while tc <= tcs:
    solve(tc)
    tc += 1

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
#import numba

def run():
    N, K = list(map(int, input().split()))
    A = list(map(int, sysread().split()))
    mod = 10 ** 9 + 7
    INF = mod

    plus = [a for a in A if a >= 0]
    minus = [-a for a in A if a < 0]

    plus = sorted(plus, reverse=True)
    minus = sorted(minus, reverse=True)

    P, M  = [1], [1]
    for p in plus:
        P.append((P[-1] * p) % mod)
    for m in minus:
        M.append((M[-1] * m) % mod)
    #print(P, M)


    max_ans = -1
    for i in range(0, K+1, 2):
        if i >= len(M) or K - i >= len(P):continue
        ans = M[i] * P[K-i] % mod
        if max_ans < ans:
            max_ans = ans
        #else:
        #    break

    if max_ans == -1:
        P, M = [1], [1]
        for p in plus[::-1]:
            P.append((P[-1] * p) % mod)
        for m in minus[::-1]:
            M.append((M[-1] * m) % mod)
        #print(P, M)

        for i in range(1, K + 1, 2):
            #print(i)
            if i >= len(M) or K - i >= len(P): continue
            ans = (-M[i] * P[K - i]) % mod
            #print(ans)
            if max_ans < ans:
                max_ans = ans

    print(max_ans)






if __name__ == "__main__":
    run()

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
p = []
m = []
ans = 1
for i in a:
    if i < 0:
        m.append(-i)
    else:
        p.append(i)
cp = len(p)
cm = len(m)
m.append(0)
m.append(0)
p.append(0)
p.append(0)
p.sort()
m.sort()
p = deque(p)
m = deque(m)
if cp>=k or (k-cp)%2 == 0:
    f = 0
else:
    f = 1 
if f == 0:
    while k:
        # print(k,cm,m)
        if k%2 == 1 and cp:
            p1 = deque.pop(p)
            ans *= p1
            k -= 1
            cp -= 1
        elif f == 0 and m[-1] * m[-2] > p[-1] * p[-2] and cm > 1 and k>1:
            m1 = deque.pop(m)
            m2 = deque.pop(m)
            ans *= m1 * m2
            cm -= 2
            k -= 2
        elif cp > 0:
            p1 = deque.pop(p)
            ans *= p1
            k -= 1
            cp -= 1
        else:
            
            ans *= -m[2]
            m1 = deque.popleft(m)
            m2 = deque.popleft(m)
            m3 = deque.popleft(m)
            deque.appendleft(m,m1)
            deque.appendleft(m,m2)
            cm -= 1
            k -= 1
        ans %= mod
else:
    m1 = deque.popleft(m)
    m2 = deque.popleft(m)
    m1 = deque.popleft(p)
    m2 = deque.popleft(p)
    deque.append(m,10**10)
    deque.append(p,10**10)
    while k:
        k-=1
        # print(p,m)
        if p[0] < m[0]:
            ans *= deque.popleft(p)
        else:
            ans *= -deque.popleft(m)
        ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2000)

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

mod = 10**9 + 7

als = []
test = True
for i in an:
    if i > 0:
        test = False
    als.append([abs(i), i])
if test and k % 2 == 1:
    an.sort(reverse=True)
    ans = 1
    for i in range(k):
        ans = ans * an[i] % mod
    print(ans)
    exit()

als.sort(reverse=True)

ans = 1
min_p = 10**9 + 1
min_m = - 10**9 + 1
cnt = 0
for i in range(k):
    x, y = als[i]
    ans = ans * x % mod
    if y > 0:
        min_p = y
    if y < 0:
        min_m = y
        cnt += 1

if cnt % 2 == 0:
    print(ans)
    exit()

max_p = 0
max_m = 0
for j in range(k, n):
    if als[j][1] > 0:
        max_p = max(max_p, als[j][0])
    if als[j][1] < 0:
        max_m = max(max_m, als[j][0])
    if max_p != 0 and max_m != 0:
        break

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y/2)**2 % mod
    else            : return power(x, y/2)**2 * x % mod

if max_m == 0 or max_p / min_m >= max_m / min_p:
    print(ans * max_p * power(min_m, mod-2) % mod)
else:
    print(ans * max_m * power(min_p, mod-2) % mod)

Submission status: Wrong Answer

Solution code:
def resolve():
    import bisect
    mod = 10**9 + 7
    N, K = [int(i) for i in input().split()]
    A = sorted([int(i) for i in input().split()])
    l = bisect.bisect_left(A, 0)
    Aneg = A[:l]
    Apos = A[l:]
    ans = []
    if N == K:
        ans = A
    elif len(Apos) == 0:
        if K % 2 == 0:
            ans = Aneg[:K]
        else:
            ans = Aneg[N - K:]
    elif len(Aneg) == 0:
        ans = Apos[N - K:]
    else:
        prt = 1 % mod
        if (K - len(Apos)) % 2 == 1:
            ni, pi = len(Aneg) - 1, 0
            cnt = 0
            while K - cnt > 0:
                if K - cnt < 2:
                    if ni >= 0:
                        prt *= (Aneg[ni] % mod)
                        cnt += 1
                    else:
                        # TODO:?
                        prt *= (Apos[-1] % mod)
                        cnt += 1
                else:
                    if pi < (len(Apos) - 1) and (ni <
                                                 1 or (Apos[pi] * Apos[pi + 1] < Aneg[ni] * Aneg[ni - 1])):
                        prt *= (Apos[pi] % mod)
                        prt *= (Apos[pi + 1] % mod)
                        pi += 2
                        cnt += 2
                    elif ni > 0:
                        prt *= (Aneg[ni] % mod)
                        prt *= (Aneg[ni - 1] % mod)
                        ni -= 2
                        cnt += 2
                    else:
                        pass
        else:
            ni, pi = 0, len(Apos) - 1
            cnt = 0
            while K - cnt > 0:
                if K - cnt < 2:
                    if pi >= 0:
                        prt *= (Apos[pi] % mod)
                        cnt += 1
                    else:
                        # TODO:?
                        prt *= (Aneg[-1] % mod)
                        cnt += 1
                else:
                    if ni < (len(Aneg) - 1) and (pi <
                                                 1 or (Aneg[ni] * Aneg[ni + 1] > Apos[pi] * Apos[pi - 1])):
                        prt *= (Aneg[ni] % mod)
                        prt *= (Aneg[ni + 1] % mod)
                        ni += 2
                        cnt += 2
                    elif pi > 0:
                        prt *= (Apos[pi] % mod)
                        prt *= (Apos[pi - 1] % mod)
                        pi -= 2
                        cnt += 2
                    else:
                        pass
            # cnt += 1
            # ni += 1
            # pi -= 1
            # ni < len(Aneg)
            # pi >= 0
        print(prt % mod)
        return
    prt = 1 % mod
    for a in ans:
        prt *= (a % mod)
    print(prt % mod)


resolve()

Submission status: Wrong Answer

Solution code:
def main():
    N, K = input_ints()
    A = input_int_list_in_line()

    Ap = []
    An = []
    Az = []
    for a in A:
        if a == 0:
            Az.append(a)
        elif a > 0:
            Ap.append(a)
        else:
            An.append(a)

    if len(An) == N and K % 2 == 1:
        An.sort(reverse=True)
        prod = 1
        for i in An[:K]:
            prod *= i

        print_ans(prod)
        exit()

    if len(Ap) == 0 and K % 2 == 1:
        print(0)
        exit()

    if N - len(Az) < K:
        print(0)
        exit()

    if N == K:
        prod = 1
        for i in A:
            prod *= i

        print_ans(prod)
        exit()

    if K == 1:
        print_ans(max(A))
        exit()

    prod = 1

    An.sort(reverse=False)

    if len(An) % 2 == 1:
        An.pop(-1)

    An2 = []

    for i in range(len(An) // 2):
        An2.append(An[i*2] * An[i*2 + 1])

    i = 0
    j = 0

    while K > 0:
        if j not in range(len(An2)):
            prod = (prod * Ap[i])
            i += 1
            K -= 1
            continue

        if i not in range(len(Ap)):
            prod = (prod * An2[j])
            j += 1
            K -= 2
            continue

        if K >= 2 and Ap[i] < An2[j]:
            prod = (prod * An2[j])
            j += 1
            K -= 2
            continue
        else:
            prod = (prod * Ap[i])
            i += 1
            K -= 1
            continue

    print_ans(prod)


def print_ans(n: int):
    print(n % (10**9 + 7))


def input_ints():
    line_list = input().split()

    if len(line_list) == 1:
        return int(line_list[0])
    else:
        return map(int, line_list)


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


def input_int_tuple_list(n: int):
    return [tuple(map(int, input().split())) for _ in range(n)]


main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split(' '))
A = sorted(list(map(int, input().split(' '))))
mod = 10 ** 9 + 7
p = 0
for i in range(N):
    if A[i] >= 0:
        break
p = i
if (p == N - 1 and K % 2 != 0):
    ans = 1
    for i in range(K):
        ans *= A[-1 - i]
        ans %= mod
    print(ans%mod)
    exit()
minus = A[:p]
plus = sorted(A[p:],reverse=True)
len_m = len(minus)
len_p = len(plus)
m = 0
p = 0
ans = 1
while K > 0:
    if K >= 2 and m <= len_m - 2 and p <= len_p - 2:
        if minus[m] * minus[m] > plus[p] * plus[p + 1]:
            ans *= minus[m] * minus[m + 1]
            ans %= mod
            m += 2
        else:
            ans *= plus[p] * plus[p + 1]
            ans %= mod
            p += 2
        K -= 2
    elif K >= 2 and m <= len_m - 2:
        ans *= minus[m] * minus[m + 1]
        ans %= mod
        m += 2
        K -= 2
    elif K >= 2 and p <= len_p - 2:
        ans *= plus[p] * plus[p + 1]
        ans %= mod
        p += 2
        K -= 2
    elif p <= len_p - 1:
        ans *= plus[p]
        ans %= mod
        p += 1
        K -= 1
    else:
        ans *= minus[m]
        ans %= mod
        m += 1
        K -= 1
print(ans%mod)

Submission status: Wrong Answer

Solution code:
def resolve():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    pls = [i for i in A if i > 0]
    ms = [i for i in A if i <0]
    pls.sort(reverse=True)
    ms.sort(reverse=False)
    A.sort(key = lambda x : abs(x),reverse=True)
    if len(pls)+len(ms) < K:
        print(0)
        return
    if len(pls) == 0 and K %2 == 1:
        if len(ms) != N:
            print(0)
            return
        x=1
        for i in list(reversed(ms))[:K]:
            x*= abs(i)
            x%= 10**9+7

        print((-x)%(10**9+7))
        return
    if len(pls)+len(ms) == K and K %2==1:
        print(0)
        return

    pc = 0
    mc = 0
    for i in range(K):
        if pc >= len(pls):
            mc+=1
        elif mc >= len(ms):
            pc+=1
        elif pls[pc] > abs(ms[mc]):
            pc +=1
        else:
            mc +=1

    if mc%2  !=0:
        aplan=0
        bplan=0
        if mc < len(ms)-1:
            aplan = abs(ms[mc] *ms[mc-1])
        if pc < len(pls)-1:
            bplan = abs(pls[pc]*pls[pc-1])
        
        if aplan>bplan:
            pc -=1
            mc +=1
        else:
            pc +=1
            mc -=1
    result=1
    for i in pls[:pc]:
        result*=i
        result%=10**9+7
    for i in ms[:mc]:
        result*=abs(i)
        result%=10**9+7
    print(result)


resolve()

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7

N, K = map(int, input().split())
A = list(map(int, input().split()))
negatives = []
num_zero = 0
positives = []
for a in A:
    if a < 0:
        negatives.append(a)
    elif a == 0:
        num_zero += 1
    else:
        positives.append(a)
negatives.sort(reverse=True)
positives.sort(reverse=True)

n = 0
while n + 2 <= len(negatives) and n + 2 <= K:
    n += 2
answer_is_positive = K - n <= len(positives)
if answer_is_positive:
    others = []
    if K <= len(positives):
        nums = positives[-K:]
    else:
        if (K - len(positives)) % 2 == 0:
            nums = positives[:]
        else:
            nums = positives[:-1]
        while len(nums) + len(others) < K:
            n1 = negatives.pop()
            n2 = negatives.pop()
            others.extend([n1, n2])

    while True:
        if not (2 <= len(negatives) and 2 <= len(positives) and 2 <= len(nums)):
            break
        p1, p2 = nums[-1], nums[-2]
        n1, n2 = negatives.pop(), negatives.pop()
        if n1 * n2 <= p1 * p2:
            break
        others.extend([n1, n2])
        nums.pop()
        nums.pop()
    ans = 1
    for x in nums + others:
        ans = ans * x % MOD
elif K <= len(negatives) + len(positives):
    negatives.sort()
    nums = [negatives.pop()]
    while 2 <= len(negatives) and len(nums) + 2 <= K:
        nums.extend([negatives.pop(), negatives.pop()])
    nums.sort()
    others = []
    while len(nums) < K and positives:
        others.append(positives.pop())

    while True:
        if not (2 <= len(nums) and 2 <= len(positives)):
            break
        p1, p2 = positives[-1], positives[-2]
        n1, n2 = nums[-1], nums[-2]
        if n1 * n2 <= p1 * p2:
            break
        others.extend([p1, p2])
        nums.pop()
        nums.pop()
    ans = 1
    for x in nums + others:
        ans = ans * x % MOD
else:
    ans = 0

if 0 < num_zero and ans < 0:
    ans = 0
print(ans)