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
INF = float('inf')
MOD = 10**9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 1
is_pos = 0
for ai in A:
    if ai > 0:
        is_pos += 1
if is_pos == 0 and K % 2 == 1:
    sortA = sorted(A, key=abs)    
    for ai in sortA[:K]:
        ans = (ans * ai) % MOD
    print(ans)
    sys.exit()
        
sortA = sorted(A, reverse=True, key=abs)
# print(sortA)

pos_list = [0]
neg_list = [0]


for ai in sortA[:K]:
    if ai < 0:
        neg_list += [ai]
    elif ai > 0:
        pos_list += [ai]
    else:
        print(0)
        sys.exit()
# first_pos = 0
# first_neg = 0
first_pos = INF
first_neg = INF
for i in range(K, N):
    if sortA[i] > 0 and first_pos == INF:
        first_pos = sortA[i]
    elif sortA[i] < 0 and first_neg == INF:
        first_neg = sortA[i]
len_pos = len(pos_list)
len_neg = len(neg_list)
if len_pos == 0:
    if len_neg % 2 == 1:
        for i in range(1, len_neg):
            ans = (ans * neg_list[i]) % MOD
    else:
        ans = ans * first_pos
        for i in range(1, len_neg-1):
            ans = (ans * neg_list[i]) % MOD
    print(ans)
    sys.exit()
if len_neg % 2 == 1 or K==N:
    for i in range(1, len_pos):
        ans = (ans * pos_list[i]) % MOD
    for i in range(1, len_neg):
        ans = (ans * neg_list[i]) % MOD
    print(ans)
    sys.exit()
# print(first_neg, first_pos)
if first_neg == INF and first_pos == INF:
    print(0)
    sys.exit()
if first_neg == INF:
    ans = (ans * first_pos) % MOD
    for i in range(1, len_pos):
        ans = (ans * pos_list[i]) % MOD
    for i in range(1, len_neg-1):
        ans = (ans * neg_list[i]) % MOD
    print(ans)
    sys.exit()
if first_pos == INF:
    ans = (ans * first_neg) % MOD
    for i in range(1, len_pos-1):
        ans = (ans * pos_list[i]) % MOD
    for i in range(1, len_neg):
        ans = (ans * neg_list[i]) % MOD
    print(ans)
    sys.exit()
pos2 = abs(pos_list[-1] * first_pos)
neg2 = abs(neg_list[-1] * first_neg)
if pos2 >= neg2:
    ans = (ans * first_pos) % MOD
    for i in range(1, len_pos):
        ans = (ans * pos_list[i]) % MOD
    for i in range(1, len_neg-1):
        ans = (ans * neg_list[i]) % MOD
else:
    ans = (ans * first_neg) % MOD
    for i in range(1, len_pos-1):
        ans = (ans * pos_list[i]) % MOD
    for i in range(1, len_neg):
        ans = (ans * neg_list[i]) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from math import log2
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -12

N, K = MAP()
A = LIST()

A1 = []
A2 = []
B1 = []
B2 = []
zero = 0
for a in A:
    if a > 0:
        A1.append(a)
        B1.append(log2(a))
    elif a < 0:
        A2.append(-a)
        B2.append(log2(-a))
    else:
        zero += 1

A1.sort()
A2.sort()
B1.sort()
B2.sort()
acc1 = [0] + list(accumulate(B1))
accrev1 = [0] + list(accumulate(B1[::-1]))
acc2 = [0] + list(accumulate(B2))
accrev2 = [0] + list(accumulate(B2[::-1]))
mx = -INF
mn = INF
idx1 = (-1, -1)
idx2 = (-1, -1)
for i in range(K+1):
    j = K - i
    if len(B1) < i or len(B2) < j:
        continue
    if j % 2 == 0:
        sm = accrev1[i] + accrev2[j]
        if sm - EPS > mx:
            mx = sm
            idx1 = (i, j)
    else:
        sm = acc1[i] + acc2[j]
        if sm < mn - EPS:
            mn = sm
            idx2 = (i, j)

if mx != -INF:
    ans = 1
    n, m = idx1
    A1.reverse()
    A2.reverse()
    for i in range(n):
        ans *= A1[i]
        ans %= MOD
    for i in range(m):
        ans *= -A2[i]
        ans %= MOD
    print(ans)
elif zero:
    print(0)
else:
    ans = 1
    n, m = idx2
    for i in range(n):
        ans *= A1[i]
        ans %= MOD
    for i in range(m):
        ans *= -A2[i]
        ans %= MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
input=sys.stdin.readline

def fact(arr):
  ans = 1
  for s in arr:
    ans *= s
    ans = ans % (int(10**9+7))
  return ans

def main():
  N, K = map(int, input().split(' '))
  A = list(map(int, input().split(' ')))
  Aplus = []
  Aminus = []
  for a in A:
    if(a >= 0):
      Aplus.append(a)
    else:
      Aminus.append(a)
  Aplus= sorted(Aplus, reverse=True)
  Aminus= sorted(Aminus)
  Aabs = sorted(A, key=lambda x:abs(x), reverse=True)
  plusnum=0
  minusnum=0
  for i in range(K):
    if(Aabs[i] >= 0):
      plusnum+=1
    else:
      minusnum += 1
  if(minusnum % 2 == 1):
    if(minusnum > 0 and plusnum > 0):
      if minusnum < len(Aminus):
        if (plusnum < len(Aplus)):
          if(abs(Aplus[plusnum] * Aminus[minusnum - 2]) > abs(Aplus[plusnum - 2] * Aminus[minusnum])):
            plusnum+=1
            minusnum-=1
          else:
            plusnum-=1
            minusnum+=1
        else:
          plusnum-=1
          minusnum+=1
      else:
        plusnum+=1
        minusnum-=1
  if(plusnum == 0):
    print(int(fact(Aminus[::-1][:minusnum])))
  else:    
    print(int(fact(Aplus[:plusnum]+Aminus[:minusnum])))

if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
import heapq
 
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
q=[]
cnt_plus=0
for i in range(n):
  if arr[i]>0:
    cnt_plus+=1
    heapq.heappush(q,(-arr[i],1))
  elif arr[i]<0:
    heapq.heappush(q,(arr[i],-1))
  else:
    heapq.heappush(q,(0,0))
pick=[]
prev_plus=0
prev_minus=0
cnt=0
for i in range(k):
  tmp,flag=heapq.heappop(q)
  tmp*=-1
  if flag==0:
    print(0)
    exit()
  if flag==1:
    pick.append(tmp)
    prev_plus=tmp
  if flag==-1:
    if cnt==0:
      prev_minus=tmp
      cnt+=1
    else:
      cnt=0
      pick.append(prev_minus)
      pick.append(tmp)
if cnt==0:
  ans=1
  for i in range(k):
    ans*=pick[i]
    ans%=mod
  print(ans%mod)
else:
  cand_plus=0
  cand_minus=0
  while len(q)!=0:
    tmp,flag=heapq.heappop(q)
    tmp*=-1
    if flag==1 and cand_plus==0:
      cand_plus=tmp
    if flag==-1 and cand_minus==0:
      cand_minus=tmp
  if (k%2==1 and cnt_plus==0) or (cand_plus==0 and cand_minus==0):
    if arr.count(0)!=0:
      print(0)
      exit()
    else:
      q=[]
      for i in range(n):
        heapq.heappush(q,abs(arr[i]))
      ans=1
      for _ in range(k):
        ans*=heapq.heappop(q)
        ans%=mod
      print((-ans)%mod)
  else:
    if prev_plus*cand_plus>=prev_minus*cand_minus:
      pick.append(cand_plus)
    else:
      if prev_plus!=0:
        pick.remove(prev_plus)
      pick.append(prev_minus)
      pick.append(cand_minus)
    ans=1
    for i in range(k):
      ans*=pick[i]
      ans%=mod
    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

a_plus = []
a_minus = []
cnt_0 = 0

for ai in a:
    if(ai==0):
        cnt_0 += 1
    elif(ai > 0):
        a_plus.append(ai)
    else:
        a_minus.append(ai)

a_plus.sort(reverse = True)
a_minus.sort()

cnt_p = len(a_plus)
cnt_m = len(a_minus)

if(cnt_p + cnt_m < k):
    print(0)
    exit()


if(cnt_m == n)&(k%2==1):
    ans = 1
    for i in range(k):
        ans *= a_minus[cnt_m - 1 - i]
        ans %= mod
    print(ans)
    exit()
elif(cnt_p == 0)&(k%2==1):
    print(0)
    exit()

p_ind = 0
m_ind = 0

ans = 1

i = 0
while(i < k-1):
    tmp_p = 0
    tmp_m = 0
    if(p_ind + 2 <= cnt_p ):
        tmp_p = a_plus[p_ind] * a_plus[p_ind+1]

    if(m_ind + 2 <= cnt_m ):
        tmp_m = a_minus[m_ind] * a_minus[m_ind+1]

    if(tmp_p > tmp_m):
        ans *= a_plus[p_ind]
        i += 1
        p_ind += 1
    else:
        ans *= tmp_m
        i += 2
        m_ind += 2
    ans %= mod

if(i==k-1):
    ans *= a_plus[p_ind]

ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from math import log2
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -8

N, K = MAP()
A = LIST()

A1 = []
A2 = []
B1 = []
B2 = []
zero = 0
for a in A:
    if a > 0:
        A1.append(a)
        B1.append(log2(a))
    elif a < 0:
        A2.append(-a)
        B2.append(log2(-a))
    else:
        zero += 1

A1.sort()
A2.sort()
B1.sort()
B2.sort()
acc1 = [0] + list(accumulate(B1))
accrev1 = [0] + list(accumulate(B1[::-1]))
acc2 = [0] + list(accumulate(B2))
accrev2 = [0] + list(accumulate(B2[::-1]))
mx = -INF
mn = INF
idx1 = (-1, -1)
idx2 = (-1, -1)
for i in range(K+1):
    j = K - i
    if len(B1) < i or len(B2) < j:
        continue
    if j % 2 == 0:
        sm = accrev1[i] + accrev2[j]
        if sm - EPS > mx:
            mx = sm
            idx1 = (i, j)
    else:
        sm = acc1[i] + acc2[j]
        if sm < mn - EPS:
            mn = sm
            idx2 = (i, j)

if mx != -INF:
    ans = 1
    n, m = idx1
    A1.reverse()
    A2.reverse()
    for i in range(n):
        ans *= A1[i]
        ans %= MOD
    for i in range(m):
        ans *= -A2[i]
        ans %= MOD
    print(ans)
elif zero:
    print(0)
else:
    ans = 1
    n, m = idx2
    for i in range(n):
        ans *= A1[i]
        ans %= MOD
    for i in range(m):
        ans *= -A2[i]
        ans %= MOD
    print(ans)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
a = LI()
a.sort()
minus = []
m = 0
plus = []
p = 0
zero = 0
for i in range(n):
    if a[i] < 0:
        minus.append(a[i])
        m += 1
    elif a[i] > 0:
        plus.append(a[i])
        p += 1
    else:
        zero += 1

if p + m < k:
    print(0)
    quit()
elif p + m == k:
    if m % 2:
        print(0)
        quit()
    else:
        ans = 1
        cnt = 0
        for i in minus:
            ans *= (-i)
            ans %= mod
            cnt += 1
        for i in plus:
            ans *= i
            ans %= mod
        if cnt % 2:
            print((ans * (-1)) % mod)
        else:
            print(ans % mod)
        quit()
for i in range(p-1)[::-1]:
    plus[i] = plus[i] * plus[i+1]
    plus[i] %= mod
plus = [1] + plus[::-1]
minus = [1] + minus


tmp = 1
ans = -inf
cnt = 0
for i in range(m+1):
    if i != 0:
        tmp *= (-minus[i])
        tmp %= mod
        cnt += 1
    r = k - i
    if r > p:
        continue
    if r < 0:
        continue
    tmp2 = tmp * plus[r]
    tmp2 %= mod
    if cnt % 2:
        ans = max(ans, tmp2 * (-1))
    else:
        ans = max(ans, tmp2)

minus = [1] + minus[1:][::-1]
tmp = 1
cnt = 0
for i in range(m+1):
    if i != 0:
        tmp *= -minus[i]
        tmp %= mod
        cnt += 1
    r = k - i
    if r > p:
        continue
    if r < 0:
        continue
    tmp2 = tmp * plus[r]
    tmp2 %= mod
    #print(i, cnt, ans, tmp)
    if cnt % 2:
        ans = max(ans, (-1) * tmp2)
    else:
        ans = max(ans, tmp2)
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

a_plus = []
a_minus = []
cnt_0 = 0

for ai in a:
    if(ai==0):
        cnt_0 += 1
    elif(ai > 0):
        a_plus.append(ai)
    else:
        a_minus.append(ai)

a_plus.sort(reverse = True)
a_minus.sort()

cnt_p = len(a_plus)
cnt_m = len(a_minus)

if(cnt_p + cnt_m < k):
    print(0)
    exit()


if(cnt_m == n)&(k%2==1):
    ans = 1
    for i in range(k):
        ans *= a_minus[cnt_m - 1 - i]
        ans %= mod
    print(ans)
    exit()
elif(cnt_p == 0)&(k%2==1):
    print(0)
    exit()

p_ind = 0
m_ind = 0

ans = 1

i = 0
while(i < k-1):
    tmp_p = 0
    tmp_m = 0
    if(p_ind + 2 <= cnt_p ):
        tmp_p = a_plus[p_ind] * a_plus[p_ind+1]

    if(m_ind + 2 <= cnt_m ):
        tmp_m = a_minus[m_ind] * a_minus[m_ind+1]

    if(tmp_p > tmp_m):
        ans *= a_plus[p_ind]
        i += 1
        p_ind += 1
    else:
        ans *= tmp_m
        m_ind += 2
    ans %= mod

if(i==k-1):
    ans *= a_plus[p_ind]

ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
mod = 10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort(key=lambda x:-abs(x))
p = []
n = []
for i in range(K):
    a = A[i]
    if a>0:
        p.append(a)
    elif a<0:
        n.append(a)

if len(n)%2==0:
    ans = 1
    for a in n:
        ans *= a
        ans %= mod
    for a in p:
        ans *= a
        ans %= mod
else:
    ap = 0
    an = 0
    for i in range(K,N):
        if ap==0 and A[i]>0:
            ap = A[i]
        if an==0 and A[i]<0:
            an = -A[i]
    if len(p)>0:
        ap_ = p[-1]
    else:
        ap_ = 1
    an_ = -n[-1]
    if ap==0 and an==0:
        ans = 0
    else:
        if ap*ap_>an*an_:
            n.pop()
            p.append(ap)
        else:
            if p:
                p.pop()
                n.append(-an)
        ans = 1
        for a in n:
            ans *= a
            ans %= mod
        for a in p:
            ans *= a
            ans %= mod

if len(p)+len(n)<K:
    ans = 0
if len(p)==0 and len(n)==K and K%2==1:
    An = [A[i] for i in range(N) if A[i]<0]
    An.sort()
    An = An[::-1]
    ans = 1
    for i in range(K):
        ans *= An[i]
        ans %= mod
    if A[-1]==0:
        ans = 0
if N==K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True,key=lambda x : abs(x))
ans=1
plus1=-1
minus1=-1
for i in range(k):
    ans*=a[i]
    if a[i]>=0:
        plus1=i
    else:
        minus1=i
plus2=-1
for i in range(k,n):
    if a[i]>=0:
        plus2=i
        break
minus2=-1
for i in range(k,n):
    if a[i]<0:
        minus2=i
        break
if ans>=0:
    print(ans)
else:
    if (plus2>0 and minus1>0) or (minus2>0 and plus1>0):
        ans1=-1
        ans2=-1
        if plus2>0 and minus1>0:
            ans1=ans*a[plus2]//a[minus1]
        if minus2>0 and plus1>0:
            ans2=ans*a[minus2]//a[plus1]
        print(max(ans1,ans2))
    else:
        ans=1
        for i in range(0,k):
            ans*=a[-1-i]
        print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, k = MAP()

a = LIST()

pos = []
neg = []
zero = []

for el in a:
    if(el<0):
        neg.append(el)
    elif(el>0):
        pos.append(el)
    else:
        zero.append(el)

pos = sorted(pos)[::-1]
neg = sorted(neg)[::-1]

ans = 1

if(k==n):
    for el in a:
        ans = (ans%mod*el%mod)%mod
else:

    if(len(pos)==0):
        if(k%2==0):
            temp = 0
            for i in range(len(neg)-1, -1, -1):
                if(temp==k):
                    break
                ans = (ans%mod*neg[i]%mod)%mod
                temp+=1
            if(temp<k):
                ans = 0
        else:
            temp = 0
            for i in range(len(neg) - 1):
                if (temp == k):
                    break
                ans = (ans%mod * neg[i]%mod) % mod
                temp += 1
            if (temp < k):
                ans = 0
    else:

        left = k

        i,j = 0, len(neg)-1

        while(left>1):
            temp, temp1 = 0, 0
            if(i<len(pos)-1):
                temp = pos[i]*pos[i+1]
                # i+=2
            if(j>=1):
                temp1 = neg[j]*neg[j-1]
                # j-=2
            if(temp==0 and temp1==0):
                break
            if(temp1>temp):
                ans = (ans*(temp1%mod))%mod
                j-=2
            else:
                ans = (ans*(temp%mod))%mod
                i+=2
            left -= 2
        # print(ans,i,j)
        if(left>1):
            ans = 0
        elif(left==1):
            if(i<len(pos)):
                ans = ((ans%mod)*pos[i])%mod
            else:
                ans1 = 1
                for b in range(i-1):
                    ans1 = (ans1%mod*(pos[b]))%mod
                for c in range(len(neg)-1, j-2,-1):
                    ans1 = (ans1%mod*neg[c])%mod
                ans = max(ans, ans1)
        if(k%2!=0):
            ans1 = 1
            if(i-2>=0 and j-2>=0 and i-2<=len(pos)-1 and j-2<=len(neg)-1):
                for b in range(i-1):
                    ans1 = (ans1%mod*(pos[b]))%mod
                for c in range(len(neg)-1, j-2,-1):
                    ans1 = (ans1%mod*neg[c])%mod
            # print(ans, ans1)
            ans = max(ans, ans1)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9+7
a.sort()
mi = []
pl = []
zero = 0
for i in a:
    if i < 0:
        mi.append(i)
    elif i == 0:
        zero += 1
    else:
        pl.append(i)
pl = pl[::-1]
if n-zero < k:
    print(0)
    exit()
if mi == []:
    ans = 1
    count = 0
    while count < k:
        ans *= a[-1-count]
        ans %= mod
        count += 1
    print(ans)
    
    exit()
if pl == []:
    if k%2:
        if zero:
            print(0)
        else:
            ans = 1
            count = 0
            while count < k:
                ans *= a[-1-count]
                ans %= mod
                count += 1
            print(ans)
            
    else:
        ans = 1
        count = 0
        while count < k:
            ans *= a[count]
            ans %= mod
            count += 1
        print(ans)
        
    exit()

ans = 0
ip = 0
im = 0
if k%2:
    count = pl[0]
    k -= 1
    ip += 1
else:
    count = 1
while k > 0:
    check1 = True
    check2 = True
    if ip+2 <= len(pl):
        x = pl[ip]*pl[ip+1]
        
    else:
        x = 1
        check1 = False
    if im+2 <= len(mi):
        y = mi[im]*mi[im+1]
    else:
        y = 1
        check2 = False
    if x >= y:
        if check1:
            ip += 2
        count = (x*count)%mod
    else:
        if check2:
            im += 2
        count = (y*count)%mod
    if check1 == False and check2 == False:
        break
    k -= 2
if k:
    print(0)
else:
    print(count%mod)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, K = map(int, input().split())
A = list(map(int, input().split()))
div = 10**9+7
a = sorted(A)
n_a = np.array(a)
plus = n_a[n_a >= 0]
ans = 1
if K % 2 != 0 and len(plus) == 0:
    while K > 0:
        ans *= a.pop(-1)
        ans %= div
        K -= 1
    print(ans)
    exit()
while K > 0:
    if K >= 2:
        if a[0] * a[1] > a[-1] * a[-2]:
            ans *= a.pop(0)
            ans %= div
            ans *= a.pop(0)
            ans %= div
        else:
            ans *= a.pop(-1)
            ans %= div
            ans *= a.pop(-1)
            ans %= div
        K -= 2
    else:
        ans *= a.pop(-1)
        ans %= div
        K -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

mod = 10**9 + 7

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().strip().split()))

# 0も入れておく
pos_list = []
neg_list = []
for a_i in A:
    if a_i >= 0:
        pos_list.append(a_i)
    else:
        neg_list.append(a_i)

pos_list.sort(reverse=True)
neg_list_reverse = sorted(neg_list, reverse=True)
neg_list.sort()


lp = len(pos_list)
ln = len(neg_list)

# 前計算
pos_values = []
tmp = 1
for i in range(N):
    if i == lp:
        break
    tmp *= pos_list[i]
    tmp %= mod
    pos_values.append(tmp)

neg_values = []
tmp = 1
for i in range(N):
    if i == ln:
        break
    tmp *= neg_list[i] * (-1)
    tmp %= mod
    neg_values.append(tmp)

neg_rev_values = []
tmp = 1
for i in range(N):
    if i == ln:
        break
    tmp *= neg_list_reverse[i] * (-1)
    tmp %= mod
    neg_rev_values.append(tmp)

# print("pos", len(pos_values))
# print("neg", len(neg_values))
# print("neg_rev", len(neg_rev_values))

ans = -float("inf")
# 最大の正の場合
for NK in range(0, K+1, 2):
    tmp = 1
    if NK > ln:
        break
    if K - NK > lp:
        continue

    if NK > 0:
        tmp *= neg_values[NK-1]
    if K-NK > 0:
        tmp *= pos_values[K-NK-1]
    # print(neg_values[NK-1], pos_values[K-NK-1])
    ans = max(ans, tmp % mod)
if ans != -float("inf"):
    print(ans)
    sys.exit()

# 最大がマイナスになる場合
for NK in range(1, K+1, 2):
    tmp = 1
    if NK > ln:
        break
    if K - NK > lp:
        continue
    if NK > 0:
        tmp *= neg_rev_values[NK-1]
    if K-NK > 0:
        tmp *= pos_values[K-NK-1]
    ans = max(ans, -1 * tmp % mod)

print(ans)

Submission status: Wrong Answer

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a=sorted(a)
    a2=[]
    minus=0
    for i in range(n):
        if a[i]<0:
            a2.append([abs(a[i]),i,1])
            minus+=1
        else:
            a2.append([abs(a[i]), i,0])
    a2=sorted(a2,reverse=True)
    temp=1
    m2=0
    ans=1
    for i in range(k):
        m2+=a2[i][2]
    if m2%2==0 or n==k:
        for i in range(k):
            ans*=a2[i][0]
            ans=ans%MOD
    elif minus-m2<=0 and n>k:
        for i in reversed((range(k))):
            if a2[i][2]==1:
                a2[i][0]=a2[k][0]
        for i in range(k):
            ans*=a2[i][0]
            ans=ans%MOD
    else:
        temp1p = -1
        temp1m = -1
        paru1 = 0
        maru1 = 0
        for i in reversed((range(k))):
            if a2[i][2]==0:
                temp1p=max(i,temp1p)
                paru1=1
            else:
                temp1m=max(i,temp1m)
                maru1=1
        temp2p=INFI
        temp2m=INFI
        paru2=0
        maru2=0
        for i in range(k,n):
            if a2[i][2]==0:
                temp2p=min(i,temp2p)
                paru2=1
            else:
                temp2m=min(i,temp2m)
                maru2=1
        if paru1==0 and paru2==0:
            pass
        elif paru1==0 or maru2==0:
            a2[temp1m][0]=a2[temp2p][0]
        elif maru1==0 or paru2==0:
            a2[temp1p][0]=a2[temp2m][0]
        else:
            tem2=a2[temp2p][0]*a2[temp1p][0]
            tem3=a2[temp1m][0]*a2[temp2m][0]
            if tem2>=tem3:
                a2[temp1m][0]=a2[temp2p][0]
            else:
                a2[temp1p][0]=a2[temp2m][0]
        if paru1 == 0 and paru2 == 0:
            for i in range(k):
                ans*=a[-(i+1)]
                ans=ans%MOD
        else:
            for i in range(k):
                ans*=a2[i][0]
                ans=ans%MOD

    print(ans)





if __name__ == "__main__":

    main()

Submission status: Wrong Answer

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

if n == k:
    ans = 1
    for x in a:
        ans *= x
    print(ans % (10**9 + 7))
    exit()

p = []
m = []
zero = 0

for x in a:
    if x == 0:
        zero += 1
    if x > 0:
        p.append(x)
    else:
        m.append(x)

if len(p) + len(m) < k:
    print(0)
    exit()

if len(m) == n:
    m.sort(reverse=True)
    ans = 1
    for i in range(k):
        ans *= m[i]
    print(ans % (10**9 + 7))
    exit()

p.sort(reverse=True)
m.sort()

sp = []
sm = []
for i in range(1, len(p), 2):
    sp.append(p[i] * p[i-1])

for i in range(1, len(m), 2):
    sm.append(m[i] * m[i-1])


ans = 1
while k > 1:
    k -= 2
    if sp == []:
        ans *= sm[0]
        sm.pop(0)
        m.pop(-1)
        m.pop(-1)
    elif sm == []:
        ans *= sp[0]
        sp.pop(0)
        p.pop(-1)
        p.pop(-1)
    elif sp[0] > sm[0]:
        ans *= sp[0]
        sp.pop(0)
        p.pop(-1)
        p.pop(-1)
    else:
        ans *= sm[0]
        sm.pop(0)
        m.pop(-1)
        m.pop(-1)

if k == 1:
    if p != []:
        ans *= p[0]
    elif zero > 0:
        ans = 0
    else:
        ans *= m[0]

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

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
li_a = list(map(int, input().split()))
mod = 10**9+7
li = []
lll = 0
for i in li_a:
    if i < 0:
        li.append((abs(i), -1))
        lll += 1
    else:
        li.append((i, 1))
li.sort()
if lll == n:
    ans = 1
    if k %2 ==1:
        for i in range(k):
            ans *= -li[i][0]
            ans %= mod
        print(ans)
        exit()
    else:
        for i in range(k):
            ans *= li[i][0]
            ans %= mod
        print(ans)
        exit()
ans = 1
guki = 1
for i in range(n-1, n-k-1, -1):
    ans *= li[i][0]
    ans %= mod
    guki *= li[i][1]
if guki > 0:
    print(ans)
else:
    P, M, p, m = 10**6, 1000000, 1000000, 1000000
    P1, M1, p1, m1 = True, True, True, True
    for i in range(n-k, n):
        if li[i][1] > 0:
            Plus = li[i][0]
            P = i
            P1 = False
            break
    for i in range(n-k, n):
        if li[i][1] < 0:
            Mini = li[i][0]
            M = i
            M1 = False
            break
    if n-k-1 >= 0:
        for i in range(n-k-1, -1, -1):
            if li[i][1] > 0:
                plus = li[i][0]
                p = i
                p1 = False
                break
        for i in range(n-k-1, -1, -1):
            if li[i][1] < 0:
                mini = li[i][0]
                m = i
                m1 = False
                break
    ans1 = 1
    ans2 = 1
    if (not P1) and (not m1):
        for i in range(n-1, n-k-1, -1):
            if i == P:
                continue
            ans1 *= li[i][0]
            ans1 %= mod
        ans1 *= li[m][0]
        ans1 %= mod
    if (not p1) and (not M1):
        for i in range(n-1, n-k-1, -1):
            if i == M:
                continue
            ans2 *= li[i][0]
            ans2 %= mod
        ans2 *= li[p][0]
        ans2 %= mod
    if (not p1) and (not P1) and (not M1) and (not m1):
        if mini/Plus > plus/Mini:
            print(ans1)
        else:
            print(ans2)
    elif (not p1) and (not M1):
        print(ans2)
    elif (not m1) and (not P1):
        print(ans1)
    else:
        ans = 1
        for i in range(k):
            ans *= -li[i][0]
            ans %= mod
        print(ans)