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
sys.setrecursionlimit(2147483647)
input=sys.stdin.readline

def fact(arr):
  ans = 1
  for s in arr:
    ans *= s
    ans = ans % (int(10e9+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:
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])

    if len(minus) % 2 == 1:
        tplus = deque()
        tminus = deque()
        if len(plus) > 0:
            tplus.append(plus.pop())
        tminus.append(minus.pop())

        for i in range(K, N):
            if A[i] >= 0 and len(tplus) < 2:
                tplus.append(A[i])
            if A[i] < 0 and len(tminus) < 2:
                tminus.append(A[i])
            if len(tplus) == len(tminus) == 2:
                break

        if len(tplus) != 2:
            while tplus:
                plus.append(tplus.popleft())
        elif len(tminus) != 2:
            while tminus:
                minus.append(tminus.popleft())
        elif tminus[-1] * tminus[-2] > tplus[-1] * tminus[-2]:
            while tminus:
                minus.append(tminus.popleft())
        else:
            while tplus:
                plus.append(tplus.popleft())

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

    print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
kk = K % 2
k2 = K // 2
if kk == 1:
    # case 1
    ip = 0
    im = N - 1
    p1 = A[ip]
    ip += 1
    for i in range(k2):
        pp = (p1 * A[ip] * A[ip + 1]) % (10**9 + 7)
        pm = (p1 * A[im] * A[im - 1]) % (10**9 + 7)
        if pp > pm:
            p1 = pp
            ip += 2
        else:
            p1 = pm
            im -= 2
    # case 2
    ip = 0
    im = N - 1
    p2 = A[im]
    im -= 1
    for i in range(k2):
        pp = (p2 * A[ip] * A[ip + 1]) % (10**9 + 7)
        pm = (p2 * A[im] * A[im - 1]) % (10**9 + 7)
        if pp > pm:
            p2 = pp
            ip += 2
        else:
            p2 = pm
            im -= 2
    p = max(p1, p2)
else:
    ip = 0
    im = N - 1
    p = 1
    for i in range(k2):
        pp = (p * A[ip] * A[ip + 1]) % (10**9 + 7)
        pm = (p * A[im] * A[im - 1]) % (10**9 + 7)
        if pp > pm:
            p = pp
            ip += 2
        else:
            p = pm
            im -= 2
print(p)

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

p=[]
m=[]
zero=False
cntm=0
cntp=0

for aa in a:
    if aa>0:
        p.append(aa)
        if cntp+cntm<K:
            cntp+=1
    elif aa<0:
        m.append(-aa)
        if cntp+cntm<K:
            cntm+=1
    
    if aa==0:
        zero=True

ans=1

if cntm%2==1:
    if cntm+1<=len(m) and cntm+1<=K and cntp+1<=len(p) and cntp+1<=K:
        if p[cntp]*p[cntp-1]>m[cntm]*m[cntm-1]:
            cntp+=1
            cntm-=1
        else:
            cntm+=1
            cntp-=1
    elif cntm+1<=len(m) and cntm+1<=K:
        cntm+=1
        cntp-=1
    elif cntp+1<=len(p) and cntp+1<=K:
        cntp+=1
        cntm-=1
    else:
        if zero:
            print(0)
            exit(0)
        
        for i in range(K):
            ans*=a[N-i-1]
            ans=(ans+mod*mod)%mod
        
        print(ans)
        exit(0)

for i in range(cntm):
    ans*=m[i]
    ans%=mod
for i in range(cntp):
    ans*=p[i]
    ans%=mod

print(ans)

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(neg_list[-1] * first_pos)
neg2 = abs(pos_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:
n , k = map(int, input().split())
a = list(map(int, input().split()))
neg = []
pos = []
mod = 10**9+7
for i in range(n):
    if a[i] > 0:
        pos.append(a[i])
    else:
        neg.append(a[i])
neg.sort()
pos.sort(reverse = True)
min_num = -1
good_num = 0
if len(pos) == 0 or n == k:
    ans = 1
    a.sort(reverse = True)
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans % mod)
else:
    #最大化するとき
    for i in range(0,k+1,2):
        #i個だけnegから取る。
        if i > len(neg) or k - i > len(pos):
            continue
        m = 0
        if i - 1 >= 0:
            m = abs(neg[i-1])
        if k-i-1 >= 0:
            m = min(m, pos[k-i-1])
        if m > min_num:
            min_num = m
            good_num = i
    ans = 1
    if good_num % 2 != 0:
        k = a / 0
    for i in range(good_num):
        ans *= neg[i]
        ans %= mod
    for i in range(k - good_num):
        ans *= pos[i]
        ans %= mod
    print(ans % mod)

Submission status: Wrong Answer

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

z_num = sum(v == 0 for v in A)
p_num = sum(v > 0 for v in A)
m_num = sum(v < 0 for v in A)

if p_num + m_num < K:
    print(0)
    exit()
    
if m_num % 2 == 1 and p_num + m_num == K and z_num > 0:
    print(0)
    exit()

if p_num == 0 and m_num >= K and K % 2 == 1:
    if z_num > 0:
        print(0)
    else:
        x = sorted([v for v in A if v < 0], reverse=True)
        ans = 1
        n = len(x)
        for i in range(K):
            ans = ans * x[i] % MOD
        print(ans)
    exit()


x = sorted([(abs(v), v // abs(v)) for v in A if v != 0])
plus = []
minus = []
for i in range(K):
    v, s = x.pop()
    if s == 1:
        plus.append(v)
    else:
        minus.append(v)


if len(minus) % 2 != 0:
    p_cand = MOD
    m_cand = MOD
    while x:
        v, s = x.pop()
        if s == 1 and p_cand == MOD:
            p_cand = v
        elif s == -1 and m_cand == MOD:
            m_cand = v

    if p_cand == MOD and m_cand != MOD and plus:
        plus.pop()
        minus.append(m_cand)
    elif m_cand == MOD and p_cand != MOD and minus:
        minus.pop()
        plus.append(p_cand)
    elif p_cand != MOD and m_cand != MOD and plus and minus:
        p_org = plus.pop()
        m_org = minus.pop()
        if p_org * p_cand > m_org * m_cand:
            plus.append(p_org)
            plus.append(p_cand)
        else:
            minus.append(m_org)
            minus.append(m_cand)


ans = 1
for v in plus:
    ans = ans * v % MOD
for v in minus:
    ans = ans * (-v) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 1
pls = 1
mod = 10**9+7
a_minu = [i for i in a if i <0]
if k==len(a):
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)

elif len(a_minu)==len(a) and k%2==1:
    a.sort(reverse=True)
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)

else:
    tmp = 0
    tmp2  = 0
    alis = []
    lasim = -1
    lasip = -1
    for i in a:
        if i<0:
            alis.append([-i,-1])
        else:
            alis.append([i,1])
    alis.sort(key=lambda x:x[0], reverse=True)
    for i in range(k):
        if alis[i][1]==-1:
            lasim =  i
        else:
            lasip = i
        ans *= alis[i][0]
        ans %= mod
        pls *= alis[i][1]
    if pls ==1:
        print(ans)
    else:
        ju= 0
        jud = 0
        if lasim >= 0:
            tmp = ans*pow(alis[lasim][0],mod-2,mod)
            for i in range(k,n):
                if alis[i][1]==-1:
                    continue
                else:
                    #print(alis[i][0],tmp)
                    tmp *= alis[i][0]
                    ju = 1
                    break
            if ju==0:
                tmp = 0
        if lasip >= 0:
            tmp2 = ans*pow(alis[lasip][0],mod-2,mod)
            for i in range(k,n):
                if alis[i][1]==1:
                    continue
                else:
                    #print(alis[i][0],tmp2)
                    tmp2 *= alis[i][0]
                    jud = 1
                    break
            if jud==0:
                tmp2 = 0

        if tmp2>=tmp:
            print(tmp2%mod)
        else:
            print(tmp%mod)

Submission status: Wrong Answer

Solution code:
import sys
from math import log
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 ** -10

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

A1 = []
A2 = []
B1 = []
B2 = []
zero = 0
for a in A:
    if a > 0:
        A1.append(a)
        B1.append(log(a))
    elif a < 0:
        A2.append(-a)
        B2.append(log(-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 > mx:
            mx = sm
            idx1 = (i, j)
    else:
        sm = acc1[i] + acc2[j]
        if sm < mn:
            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:
n , k = map(int, input().split())
a = list(map(int, input().split()))
neg = []
pos = []
mod = 10**9+7
for i in range(n):
    if a[i] > 0:
        pos.append(a[i])
    else:
        neg.append(a[i])
neg.sort()
pos.sort(reverse = True)
min_num = -1
good_num = 0
if len(pos) == 0 or n == k:
    ans = 1
    a.sort(reverse = True)
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans % mod)
else:
    #最大化するとき
    for i in range(0,k+1,2):
        #i個だけnegから取る。
        if i > len(neg) or k - i > len(pos):
            continue
        m = 0
        if i - 1 >= 0:
            m = abs(neg[i-1])
        if k-i-1 >= 0:
            m = min(m, pos[k-i-1])
        if m > min_num:
            min_num = m
            good_num = i
    ans = 1
    for i in range(good_num):
        ans *= neg[i]
        ans %= mod
    for i in range(k - good_num):
        ans *= pos[i]
        ans %= mod
    print(ans % mod)

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:
      pick=pick[:-1]
      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:
# 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

    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
        max_ans = max(ans, max_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)
            max_ans = max(ans, max_ans)

    print(max_ans)

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
def main(A, n, k):
    MOD = int(1e9) + 7
    A.sort()
    ans = 1
    if A[n - 1] == 0 and (k & 1):
        ans = 0
    elif A[n - 1] <= 0 and (k & 1):
        for i in range(n - 1, n - k - 1, -1):
            ans = (ans*A[i]) % MOD
    else:
        i = 0
        j = n - 1
        if k & 1:
            ans = (ans*A[j]) % MOD
            j -= 1
            k -= 1
        k >>= 1
        for itr in range(k):
            left_product = (A[i] * A[i + 1]) % MOD
            right_product = (A[j] * A[j - 1]) % MOD
            if left_product > right_product:
                ans = (ans*left_product) % MOD
                i += 2
            else:
                ans = (ans*right_product) % MOD
                j -= 2

    print(ans % MOD)


if __name__ == "__main__":
    N, K = map(int, input().split(' '))
    A = list(map(int, input().split(' ')))
    main(A, N, K)

Submission status: Wrong Answer

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

z_num = sum(v == 0 for v in A)
p_num = sum(v > 0 for v in A)
m_num = sum(v < 0 for v in A)

if p_num + m_num < K:
    print(0)
    exit()
    
if m_num % 2 == 1 and p_num + m_num == K and z_num > 0:
    print(0)
    exit()
    
if p_num == 0 and m_num >= K and K % 2 == 1:
    if z_num > 0:
        print(0)
    else:
        x = sorted([v for v in A if v < 0], reverse=True)
        ans = 1
        n = len(x)
        for i in range(n - K, n):
            ans = ans * x[i] % MOD
        print(ans)
    exit()


x = sorted([(abs(v), v // abs(v)) for v in A if v != 0])
plus = []
minus = []
for i in range(K):
    v, s = x.pop()
    if s == 1:
        plus.append(v)
    else:
        minus.append(v)


if len(minus) % 2 != 0:
    p_cand = MOD
    m_cand = MOD
    while x:
        v, s = x.pop()
        if s == 1 and p_cand == MOD:
            p_cand = v
        elif s == -1 and m_cand == MOD:
            m_cand = v

    if p_cand == MOD and m_cand != MOD and plus:
        plus.pop()
        minus.append(m_cand)
    elif m_cand == MOD and p_cand != MOD and minus:
        minus.pop()
        plus.append(p_cand)
    elif p_cand != MOD and m_cand != MOD and plus and minus:
        p_org = plus.pop()
        m_org = minus.pop()
        if p_org * p_cand > m_org * m_cand:
            plus.append(p_org)
            plus.append(p_cand)
        else:
            minus.append(m_org)
            minus.append(m_cand)


ans = 1
for v in plus:
    ans = ans * v % MOD
for v in minus:
    ans = ans * (-v) % MOD
print(ans)

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

p=[]
m=[]
zero=False
cntm=0
cntp=0

for aa in a:
    if aa>0:
        p.append(aa)
        if cntp+cntm<K:
            cntp+=1
    elif aa<0:
        m.append(-aa)
        if cntp+cntm<K:
            cntm+=1
    
    if aa==0:
        zero=True

ans=1

if cntm%2==1:
    if cntm+1<=len(m) and cntm+1<=K and cntp+1<=len(p) and cntp+1<=K:
        if p[cntp]*p[cntp-1]>m[cntm]*m[cntm-1]:
            cntp+=1
            cntm-=1
        else:
            cntp+=1
            cntm-=1
    elif cntm+1<=len(m) and cntm+1<=K:
        cntm+=1
        cntp-=1
    elif cntp+1<=len(p) and cntp+1<=K:
        cntp+=1
        cntm-=1
    else:
        if zero:
            print(0)
            exit(0)
        
        for i in range(K):
            ans*=a[N-i-1]
            ans=(ans+mod*mod)%mod
        
        print(ans)
        exit(0)

for i in range(cntm):
    ans*=m[i]
    ans%=mod
for i in range(cntp):
    ans*=p[i]
    ans%=mod

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

MOD=10**9+7

ans=1
if L[-1]<=0:#全部負
    if K%2==1:
        #小さい方からKこ
        for l in L[-K:]:
            ans*=l
            ans%=MOD
    else:
        #大きい方からKこ
        for l in L[:K]:
            ans*=l
            ans%=MOD
elif L[0]>=0:#全部生
    for l in L[-K:]:
        ans*=l
        ans%=MOD
else:#生徒ふが入り混じり
    cand=[]
    poss=[]
    negs=[]
    replace=[]
    if K%2==1:#奇数個
        K-=1
        cand.append(L[-1])
        for l in L[:-1]:
            if l>0:
                heapq.heappush(poss,-l)
            else:
                heapq.heappush(negs,l)
    else:
        for l in L:
            if l>0:
                heapq.heappush(poss,-l)
            else:
                heapq.heappush(negs,l)

    added = len(cand) if cand else 0
    while added<K:
        if len(poss)>=2 and len(negs)>=2:
            pa = -heapq.heappop(poss)
            pb = -heapq.heappop(poss)

            na = heapq.heappop(negs)
            nb = heapq.heappop(negs)
            if pa*pb>na*nb:
                cand.append(pa*pb)
                added+=2
            else:
                cand.append(na*nb)
                added+=2
        elif len(poss)>=2:
            pa = -heapq.heappop(poss)
            pb = -heapq.heappop(poss)
            cand.append(pa*pb)
            added+=2
        elif len(negs)>=2:
            na = heapq.heappop(negs)
            nb = heapq.heappop(negs)
            cand.append(na*nb)
            added+=2
        else:
            break
    for c in cand:
        ans*=c
        ans%=MOD
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 1
pls = 1
mod = 10**9+7
a_minu = [i for i in a if i <0]
if k==len(a):
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)

elif len(a_minu)==len(a) and k%2==1:
    a.sort()
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)

else:
    tmp = 0
    tmp2  = 0
    alis = []
    lasim = -1
    lasip = -1
    for i in a:
        if i<0:
            alis.append([-i,-1])
        else:
            alis.append([i,1])
    alis.sort(key=lambda x:x[0], reverse=True)
    for i in range(k):
        if alis[i][1]==-1:
            lasim =  i
        else:
            lasip = i
        ans *= alis[i][0]
        ans %= mod
        pls *= alis[i][1]
    if pls ==1:
        print(ans)
    else:
        ju= 0
        jud = 0
        if lasim >= 0:
            tmp = ans*pow(alis[lasim][0],mod-2,mod)
            for i in range(k,n):
                if alis[i][1]==-1:
                    continue
                else:
                    #print(alis[i][0],tmp)
                    tmp *= alis[i][0]
                    ju = 1
                    break
            if ju==0:
                tmp = 0
        if lasip >= 0:
            tmp2 = ans*pow(alis[lasip][0],mod-2,mod)
            for i in range(k,n):
                if alis[i][1]==1:
                    continue
                else:
                    #print(alis[i][0],tmp2)
                    tmp2 *= alis[i][0]
                    jud = 1
                    break
            if jud==0:
                tmp2 = 0

        if tmp2>=tmp:
            print(tmp2%mod)
        else:
            print(tmp%mod)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from functools import total_ordering

MOD = 1000000007  # type: int


def solve(N: int, K: int, A: "List[int]"):
    B = [Num(A[i]) for i in range(N)]
    B.sort(reverse=True)
    sign = 1
    ret = 1
    if N == 1:
        print(B[0].getNum() % MOD)
        return
    for i in range(K):
        sign *= B[i].getSign()
        ret *= B[i].getNum() % MOD
        ret %= MOD
    if sign > 0:
        print(ret)
        return
    elif sign < 0:
        minP = -1
        minP_i = 0
        minM = 1
        minM_i = 0
        for i in range(K - 1, -1, -1):
            if B[i].getSign() > 0:
                minP = B[i].getNum()
                minP_i = i
                break
        # else:
        #     minP = 10 ** 10
        for i in range(K - 1, -1, -1):
            if B[i].getSign() < 0:
                minM = B[i].getNum()
                minM_i = i
                break
        # else:
        #     minM = 10 ** 10
        maxP = -1
        maxP_i = 0
        maxM = 1
        maxM_i = 0
        for i in range(K, N):
            if B[i].getSign() > 0:
                maxP = B[i].getNum()
                maxP_i = i
                break
        # else:
        #     maxP = 0
        for i in range(K, N):
            if B[i].getSign() < 0:
                maxM = B[i].getNum()
                maxM_i = i
                break
        # else:
        #     maxM = 0
        if minP > 0 and minM < 0 and maxP > 0 and maxM < 0:
            x = abs(maxM) / abs(minP)   
            y = abs(maxP) / abs(minM)
            ret_new = 1
            if x > y:
                for i in range(K):
                    if i != minP_i:
                        ret_new *= B[i].getNum() % MOD
                        ret_new %= MOD
                ret_new *= B[maxM_i].getNum() % MOD
                ret_new %= MOD
            else:
                for i in range(K):
                    if i != minM_i:
                        ret_new *= B[i].getNum() % MOD
                        ret_new %= MOD
                ret_new *= B[maxP_i].getNum() % MOD
                ret_new %= MOD
            print(ret_new)
        else:
            if minP < 0:
                # minMの交換を行う
                if maxP > 0:
                    # 行う
                    ret_new = 1
                    for i in range(K):
                        if i != minM_i:
                            ret_new *= B[i].getNum() % MOD
                            ret_new %= MOD
                    ret_new *= B[maxP_i].getNum() % MOD
                    ret_new %= MOD
                    print(ret_new)
                    return
                else:
                    # 行えない
                    # 絶対値が最小のものが答え
                    ret_new = 1
                    for i in range(N - 1, N - 1 - K, -1):
                        ret_new *= B[i].getNum() % MOD
                        ret_new %= MOD
                    print(ret_new)
                    return
            else:
                if maxP > 0:
                    # maxMが存在しない
                    # minMを交換
                    ret_new = 1
                    for i in range(K):
                        if i != minM_i:
                            ret_new *= B[i].getNum() % MOD
                            ret_new %= MOD
                    ret_new *= B[maxP_i].getNum() % MOD
                    ret_new %= MOD
                    print(ret_new)
                    return
                elif maxM < 0:
                    # maxPだけ存在しない
                    # minPを交換
                    ret_new = 1
                    for i in range(K):
                        if i != minP_i:
                            ret_new *= B[i].getNum() % MOD
                            ret_new %= MOD
                    ret_new *= B[maxM_i].getNum() % MOD
                    ret_new %= MOD
                    print(ret_new)
                    return
                else:
                    # maxPもmaxMも存在しない
                    # そのまま
                    if N == K:
                        print(ret)
                    else:
                        print(0)
                    return
    else:
        print(0)
        return


@total_ordering
class Num:
    def __init__(self, num):
        self.num = num
        self.sign = (num > 0) - (num < 0)
    
    def __eq__(self, value):
        return abs(self.num) == abs(value.num)
    
    def __lt__(self, value):
        return abs(self.num) < abs(value.num)

    def getNum(self):
        return self.num

    def getSign(self):
        return self.sign

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()