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:
n, k = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

A_p = []
A_m = []
for a in A:
  if a > 0:
    A_p.append(a)
  else:
    break
for a in A[::-1]:
  if a > 0:
    break
  A_m.append(a)

MOD = 10 ** 9 + 7
def modmul(a, b):
  return a % MOD * (b % MOD) % MOD

cnt = 0
i_m = 0
i_p = 0

a = 1
if k > len(A_p) and (k - len(A_p)) % 2 != 0:
  A_m = A_m[::-1]
  while k != 0:
    if len(A_p) - i_p > 0 and len(A_m) - i_m > 0:
      if abs(A_p[i_p]) < abs(A_m[i_m]):
        a = modmul(A_m[i_m], a)
        i_m += 1
      else:
        a = modmul(A_p[i_p], a)
        i_p += 1
    elif len(A_p) - i_p == 0:
      a = modmul(A_m[i_m], a)
      i_m += 1
    else:
      a = modmul(A_p[i_p], a)
      i_p += 1
    k -= 1
while k != 0:
  if k > 1:
    m = -1
    if len(A_m) - i_m > 1:
      m = A_m[i_m] * A_m[i_m+1]
    p = -1
    if len(A_p) - i_p > 1:
      p = A_p[i_p] * A_p[i_p+1]
  
    if len(A_p) - i_p > 1 and len(A_m) - i_m > 1:
      if m >= p:
        a = modmul(a, m%MOD)
        i_m += 2
        k -= 2
      else:
        a = modmul(a, A_p[i_p])
        i_p += 1
        k -= 1
      
    elif len(A_p) - i_p < 2 and len(A_m) - i_m > 1:
      a = modmul(modmul(a, A_m[i_m]), A_m[i_m+1])
      i_m += 2
      k -= 2
  
    elif len(A_p) -i_p > 0 and len(A_m) - i_m < 2:
      a = modmul(a, A_p[i_p])
      i_p += 1
      k -= 1
    
    else:
      a = modmul(a, A_m[i_m])
      i_m += 1
      k -= 1
  
  else:
    if len(A_p) - i_p > 0:
      a = modmul(a, A_p[i_p])
      k -= 1
    else:
      a = modmul(a,A_m[i_m])
      k -= 1

print(a)

Submission status: Wrong Answer

Solution code:
from logging import *
basicConfig(level=DEBUG, format='%(levelname)s: %(message)s')
# disable(CRITICAL)

MOD = 10**9 + 7
INF = MOD
def mmul(a, b): return a*b%MOD

n, k = map(int, input().split())
A = [*map(int, input().split())]
P, M = [], [] # plus, minus
for a in A:
    if a < 0: M.append(a)
    else: P.append(a)

debug('A {}'.format(sorted(A, reverse=True, key=lambda x:abs(x))))


def mix():
    P.sort(reverse=True); M.sort()
    len_p = len(P); len_m = len(M)
    P.append(-1); M.append( 1) # add endpoint

    debug('P {}'.format(P));debug('M {}'.format(M))

    pa, ma = [], []
    while len(pa) + len(ma) < k:
        if P[len(pa)] < -M[len(ma)]: ma.append(M[len(ma)])
        else: pa.append(P[len(pa)])

    debug('pa {}'.format(pa));debug('ma {}'.format(ma))
    if len(ma)%2 == 0: return pa + ma

    exist_pa = len(pa) > 0; exist_ma = len(ma) > 0
    remain_p = len_p - len(pa) > 0; remain_m = len_m - len(ma) > 0
    debug('exist_pa {}'.format(exist_pa));debug('exist_ma {}'.format(exist_ma))
    debug('remain_p {}'.format(remain_p));debug('remain_m {}'.format(remain_m))

    if exist_pa & exist_ma & remain_p & remain_m:
        p_in = pa[-1]; p_out = P[len(pa)]
        m_in = ma[-1]; m_out = M[len(ma)]
        if abs(p_in*p_out) < abs(m_in*m_out): pa.pop(); ma.append(m_out)
        else: ma.pop(); pa.append(p_out)
        debug('pa {}'.format(pa));debug('ma {}'.format(ma))
        return pa + ma

    if (not exist_pa) & exist_ma & remain_p & (not remain_m):
        m_in = ma[-1]; p_out = P[len(pa)]
        ma.pop(); pa.append(p_out)
        debug('pa {}'.format(pa));debug('ma {}'.format(ma))
        return pa + ma

    if exist_pa & (not exist_ma) & (not remain_p) & remain_m:
        p_in = pa[-1]; m_out = M[len(ma)]
        pa.pop(); ma.append(m_out)
        debug('pa {}'.format(pa));debug('ma {}'.format(ma))
        return pa + ma

    P.pop(); M.pop()
    P.sort(); M.sort(reverse=True)
    P.append(-1); M.append( 1) # add endpoint

    debug('P {}'.format(P));debug('M {}'.format(M))

    pa, ma = [], []
    while len(pa) + len(ma) < k:
        if P[len(pa)] < -M[len(ma)]: ma.append(M[len(ma)])
        # if P[len(pa)] >= -M[len(ma)]: ma.append(M[len(ma)])
        else: pa.append(P[len(pa)])

    debug('pa {}'.format(pa));debug('ma {}'.format(ma))
    if len(ma)%2 == 1: return pa + ma

    # return [0]
    return pa + ma


ans = 1
if k==n:
    debug('k==n: {} == {} '.format(k,n))
    debug('A {}'.format(A))
    for a in A: ans = mmul(ans, a)
else:
    debug('k<n: {} < {} '.format(k,n))
    if len(P) == n:
        debug('n({}) all plus({})'.format(n,len(P)))
        P.sort(reverse=True)
        debug('P[:k] {}'.format(P[:k]))
        for a in P[:k]: ans = mmul(ans, a)
    elif len(M) == n:
        debug('n({}) all minus({})'.format(n,len(M)))
        if k%2:
            debug('k({}) is odd ({})'.format(k,k%2))
            M.sort(reverse=True)
        else:
            debug('k({}) is even ({})'.format(k,k%2))
            M.sort()
        debug('M[:k] {}'.format(M[:k]))
        for a in M[:k]: ans = mmul(ans, a)
    else:
        debug('n({}) mix plus({}):minus({})'.format(n,len(P),len(M)))
        for a in mix(): ans = mmul(ans, a)

ans += MOD; ans %= MOD
debug('ans {}'.format(ans))
print(ans)

Submission status: Wrong Answer

Solution code:
from logging import *
basicConfig(level=DEBUG, format='%(levelname)s: %(message)s')
disable(CRITICAL)

MOD = 10**9 + 7
INF = MOD
def mmul(a, b): return a*b%MOD

n, k = map(int, input().split())
A = [*map(int, input().split())]
P, M = [], [] # plus, minus
for a in A:
    if a < 0: M.append(a)
    else: P.append(a)

debug('A {}'.format(sorted(A, reverse=True, key=lambda x:abs(x))))

def mix():
    P.sort(reverse=True); M.sort()
    len_p = len(P); len_m = len(M)
    P.append(-1); M.append( 1) # add endpoint

    debug('P {}'.format(P));debug('M {}'.format(M))

    pa, ma = [], []
    while len(pa) + len(ma) < k:
        if P[len(pa)] < -M[len(ma)]: ma.append(M[len(ma)])
        else: pa.append(P[len(pa)])

    debug('pa {}'.format(pa));debug('ma {}'.format(ma))

    if len(ma)%2 == 0: return pa + ma

    exist_pa = len(pa) > 0; exist_ma = len(ma) > 0
    remain_p = len_p - len(pa) > 0; remain_m = len_m - len(ma) > 0
    debug('exist_pa {}'.format(exist_pa));debug('exist_ma {}'.format(exist_ma))
    debug('remain_p {}'.format(remain_p));debug('remain_m {}'.format(remain_m))

    if exist_pa & exist_ma & remain_p & remain_m:
        p_in = pa[-1]; p_out = P[len(pa)]
        m_in = ma[-1]; m_out = M[len(ma)]
        if abs(p_in*p_out) < abs(m_in*m_out): pa.pop(); ma.append(m_out)
        else: ma.pop(); pa.append(p_out)
        debug('pa {}'.format(pa));debug('ma {}'.format(ma))
        return pa + ma

    if (not exist_pa) & exist_ma & remain_p & (not remain_m):
        m_in = ma[-1]; p_out = P[len(pa)]
        ma.pop(); pa.append(p_out)
        debug('pa {}'.format(pa));debug('ma {}'.format(ma))
        return pa + ma

    if exist_pa & (not exist_ma) & (not remain_p) & remain_m:
        p_in = pa[-1]; m_out = M[len(ma)]
        pa.pop(); ma.append(m_out)
        debug('pa {}'.format(pa));debug('ma {}'.format(ma))
        return pa + ma

    P.pop(); M.pop()
    P.sort(); M.sort(reverse=True)
    P.append(-1); M.append( 1) # add endpoint

    debug('P {}'.format(P));debug('M {}'.format(M))

    pa, ma = [], []
    while len(pa) + len(ma) < k:
        if P[len(pa)] < -M[len(ma)]: ma.append(M[len(ma)])
        else: pa.append(P[len(pa)])

    debug('pa {}'.format(pa));debug('ma {}'.format(ma))

    if len(ma)%2 == 1: return pa + ma

    return [0]
    # return pa + ma

ans = 1
if k==n:
    debug('k==n: {} == {} '.format(k,n))
    debug('A {}'.format(A))
    for a in A: ans = mmul(ans, a)
else:
    debug('k<n: {} < {} '.format(k,n))
    if len(P) == n:
        debug('n({}) all plus({})'.format(n,len(P)))
        P.sort(reverse=True)
        debug('P[:k] {}'.format(P[:k]))
        for a in P[:k]: ans = mmul(ans, a)
    elif len(M) == n:
        debug('n({}) all minus({})'.format(n,len(M)))
        if k%2:
            debug('k({}) is odd ({})'.format(k,k%2))
            M.sort(reverse=True)
        else:
            debug('k({}) is even ({})'.format(k,k%2))
            M.sort()
        debug('M[:k] {}'.format(M[:k]))
        for a in M[:k]: ans = mmul(ans, a)
    else:
        debug('n({}) mix plus({}):minus({})'.format(n,len(P),len(M)))
        for a in mix(): ans = mmul(ans, a)

ans += MOD; ans %= MOD
debug('ans {}'.format(ans))
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a=sorted(a,reverse=True)
mod=10**9+7
x=1
y=0
z=n-1
if k%2 == 1:
  q = k//2
  a0 = a[0]
  for i in range(q):
    L = a[x]*a[x+1]
    R = a[z]*a[z-1]
    if L>R:
      a0 *= L
      x += 2
      print(a0%mod)
    else:
      a0 *= R
      z -= 2
      print(a0%mod)
      
else:
  q = k//2
  one = 1
  for i in range(q):
    L = a[y]*a[y+1]
    R = a[z]*a[z-1]
    if L>R:    
      one *= L
      y += 2
      print(one%mod)
    else:
      one *= R
      z -=2
      print(one%mod)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
#%%
Nega = []
Posi = []
for a in A:
    if a<0:
        Nega.append(a)
    else:
        Posi.append(a)

Ln = len(Nega)
Lp = len(Posi)
MOD = 10**9+7

import sys
#絶対負になる場合は，絶対値の小さい順にとればOK
if K-2*(min(Ln,K)//2)>Lp:
    A.sort(key = lambda x:abs(x))
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans = (ans+MOD)%MOD
    print(ans)
    sys.exit()

INF = 10**10
A.sort(key = lambda x:abs(x), reverse=True)
sign = 0
idx_min_nega = -1
idx_min_posi = -1
minnega=INF
minposi=INF
ans = 1
for i in range(K):
    if A[i]<0:
        sign ^= 1
        if abs(A[i])<minnega:
            minnega = abs(A[i])
            idx_min_nega = i
    else:
        if abs(A[i])<minposi:
            minposi = abs(A[i])
            idx_min_posi = i
    ans *= abs(A[i])
    ans %= MOD

if sign==0:
    print(ans)
    sys.exit()

idx_max_nega = -1
idx_max_posi = -1
for i in range(K,N):
    if A[i]<0 and idx_max_nega==-1:
        idx_max_nega = i
    elif A[i]>=0 and idx_max_posi==-1:
        idx_max_posi = i
    elif idx_max_nega!=0 and idx_max_posi!=-1:
        break

if (idx_max_nega==-1 and idx_max_posi!=-1) or idx_min_nega==-1:
    ans *= pow(abs(A[idx_min_nega]), MOD-2, MOD)
    ans *= abs(A[idx_max_posi])
    ans %= MOD
elif (idx_max_nega!=-1 and idx_max_posi==-1) or idx_min_posi==-1:
    ans *= pow(A[idx_min_posi], MOD-2, MOD)
    ans *= abs(A[idx_max_nega])
    ans %= MOD
elif abs(A[idx_max_nega])*abs(A[idx_min_nega])>abs(A[idx_min_nega])*abs(A[idx_max_posi]):
    ans *= pow(A[idx_min_posi], MOD-2, MOD)
    ans *= abs(A[idx_max_nega])
    ans %= MOD
else:
    ans *= pow(abs(A[idx_min_nega]), MOD-2, MOD)
    ans *= abs(A[idx_max_posi])
    ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
#%%
Nega = []
Posi = []
for a in A:
    if a<0:
        Nega.append(a)
    else:
        Posi.append(a)

Ln = len(Nega)
Lp = len(Posi)
MOD = 10**9+7

import sys
#絶対負になる場合は，絶対値の小さい順にとればOK
if K-2*(min(Ln,K)//2)>Lp:
    A.sort(key = lambda x:abs(x))
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans = (ans+MOD)%MOD
    print(ans)
    sys.exit()

INF = 10**10
A.sort(key = lambda x:abs(x), reverse=True)
sign = 0
idx_min_nega = 0
idx_min_posi = 0
minnega=INF
minposi=INF
ans = 1
for i in range(K):
    if A[i]<0:
        sign ^= 1
        if abs(A[i])<minnega:
            minnega = abs(A[i])
            idx_min_nega = i
    else:
        if abs(A[i])<minposi:
            minposi = abs(A[i])
            idx_min_posi = i
    ans *= abs(A[i])
    ans %= MOD

if sign==0:
    print(ans)
    sys.exit()

idx_max_nega = -1
idx_max_posi = -1
for i in range(K,N):
    if A[i]<0 and idx_max_nega==-1:
        idx_max_nega = i
    elif A[i]>=0 and idx_max_posi==-1:
        idx_max_posi = i
    elif idx_max_nega!=0 and idx_max_posi!=-1:
        break

if idx_max_nega==-1 and idx_max_posi!=-1:
    ans *= pow(abs(A[idx_min_nega]), MOD-2, MOD)
    ans *= abs(A[idx_max_posi])
    ans %= MOD
elif idx_max_nega!=-1 and idx_max_posi==-1:
    ans *= pow(A[idx_min_posi], MOD-2, MOD)
    ans *= abs(A[idx_max_nega])
    ans %= MOD
elif abs(A[idx_max_nega])*abs(A[idx_min_nega])>abs(A[idx_min_nega])*abs(A[idx_max_posi]):
    ans *= pow(A[idx_min_posi], MOD-2, MOD)
    ans *= abs(A[idx_max_nega])
    ans %= MOD
else:
    ans *= pow(abs(A[idx_min_nega]), MOD-2, MOD)
    ans *= abs(A[idx_max_posi])
    ans %= MOD

print(ans)

Submission status: Wrong Answer

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

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
b = 10**9 + 7
ans = 1
for i in range(K):
    ans = (ans * A[i]) % b
print(ans)

Submission status: Wrong Answer

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

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
b = 10**9 + 7
ans = 1
for i in range(K):
    ans = ans * (A[i] % b)
print(ans)

Submission status: Wrong Answer

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

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
b = 10**9 + 7
ans = 1
for i in range(K):
    ans = ans * A[i] % b
    ans = ans % b
print(ans)

Submission status: Wrong Answer

Solution code:
# import sys
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# N, M = map(int, input().split())
# As = list(map(int, input().split()))
# queries = (input() for _ in range(N))

from bisect import bisect_left


def solve():
    N, K = map(int, input().split())

    As = list(map(int, input().split()))

    As.sort()
    index = bisect_left(As, 0)

    # neg = As[:index]
    # pos = As[index:]
    # pos = pos[bisect_left(pos, 1):]
    # pos.sort(reverse=True)
    # print(pos, neg)

    pos = sorted(As, reverse=True)
    ans = 1
    mod = 10 ** 9 + 7

    if N == K:
        for p in pos:
            ans *= p
            ans %= mod
        return ans

    if index == N and K % 2:
        for p in pos[:K]:
            ans *= p
            ans %= mod
        return ans

    pl = 0
    pr = N - 1
    
    if K % 2:
        ans *= pos[pr]
        pr -= 1

    for i in range(K//2):
        left = pos[pl] * pos[pl+1]
        right = pos[pr] * pos[pr-1]

        if left > right:
            ans *= left
            ans %= mod
            pl += 2
        else:
            ans *= right
            ans %= mod
            pr -= 2

    return ans


def main():
    print(solve())


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# import sys
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# N, M = map(int, input().split())
# As = list(map(int, input().split()))
# queries = (input() for _ in range(N))

from bisect import bisect_left


def solve():
    N, K = map(int, input().split())

    As = list(map(int, input().split()))

    As.sort()
    index = bisect_left(As, 0)

    # neg = As[:index]
    # pos = As[index:]
    # pos = pos[bisect_left(pos, 1):]
    # pos.sort(reverse=True)
    # print(pos, neg)

    pos = sorted(As, reverse=True)
    ans = 1
    mod = 10 ** 9 + 7

    if N == K:
        for p in pos:
            ans *= p
            ans %= mod
        return ans

    if index == N and K % 2:
        for p in pos[:K]:
            ans *= p
            ans %= mod
        return ans

    pl = 0
    pr = N - 1

    for i in range(K//2):
        left = pos[pl] * pos[pl+1]
        right = pos[pr] * pos[pr-1]

        if left > right:
            ans *= left
            ans %= mod
            pl += 2
        else:
            ans *= right
            ans %= mod
            pr -= 2

    if K % 2:
        ans *= max(pos[pl], pos[pr])
        ans %= mod

    return ans


def main():
    print(solve())


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

if n == 1:exit(print(a[0]%mod))

import bisect, heapq

def cr(x,z):
  ans = 1
  if z <= 1:
    for i in range(1,k+1):
      ans *= x[-i]
    return ans
  elif z == n:
    for i in range(1,k+1):
      if k%2 == 0:
        ans *= x[i-1]
      else:
        ans *= x[-i]
    return ans
  else:
    cnt = 0
    thr = x[-k]
    while cnt < min(z,k)//2*2:
      f = heapq.heappop(x)
      s = heapq.heappop(x)
      p = f*s
      if p > thr:
        heapq.heappush(x, f*s)
        cnt += 2
      else:break
    x.sort()
    K = k - cnt//2
    for i in range(1,K+1):
      ans *= x[-i]
    return ans

a.sort()
z = bisect.bisect(a,0)

print(cr(a,z)%mod)

Submission status: Wrong Answer

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

if n == 1:exit(print(a[0]%mod))

import bisect, heapq

def cr(x,z):
  ans = 1
  if z <= 1:
    for i in range(1,k+1):
      ans *= x[-i]
    return ans
  elif z == n:
    for i in range(1,k+1):
      if k%2 == 0:
        ans *= x[i-1]
      else:
        ans *= x[-i]
    return ans
  else:
    cnt = 0
    thr = x[-k]
    while cnt < min(z,k)//2*2:
      f = heapq.heappop(x)
      s = heapq.heappop(x)
      p = bisect.bisect(x, f*s)
      if p > thr:
        heapq.heappush(x, f*s)
        cnt += 2
      else:break
    x.sort()
    K = k - cnt//2
    for i in range(1,K+1):
      ans *= x[-i]
    return ans

a.sort()
z = bisect.bisect(a,0)

print(cr(a,z)%mod)

Submission status: Wrong Answer

Solution code:
import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 1
if max(a)==0:
  print(0)
  exit()
elif max(a)<0 and k%2==1:
  a = sorted(a)[::-1]
  for i in range(k):
    ans *= a[i] % (10**9+7)
    ans %= (10**9+7)
  ans %= (10**9+7)
  print(abs(ans))
  exit()

a_abs = [[a_, abs(a_)] for a_ in a]
a_abs = sorted(a_abs, key=lambda x: -x[-1])

cnt = 0
for i in range(k):
  if a_abs[i][0]<0:
    cnt += 1

if cnt%2==0:
  for i in range(k):
    ans *= a_abs[i][0] % (10**9+7)
    ans %= (10**9+7)
  print(ans)
  exit()
  
p1 = -1
p2 = -1
for i in range(k-1,-1,-1):
  if p1==-1 and a_abs[i][0] > 0:
    p1 = i
  elif p2==-1 and a_abs[i][0] < 0:
    p2 = i
  elif p1!=-1 and p2!=-1:
    break

p3 = -1
p4 = -1
for i in range(k, n):
  if p3==-1 and a_abs[i][0] < 0:
    p3 = i
  elif p4==-1 and a_abs[i][0] > 0:
    p4 = i
  elif p3!=-1 and p4!=-1:
    break

if a_abs[p3][1]*a_abs[p2][1]>a_abs[p4][1]*a_abs[p1][1]:
  for i in range(k-1):
    if i==p1:
      continue
    ans *= a_abs[i][0] % (10**9+7)
    ans %= (10**9+7)
  ans *= a_abs[p3][0]
  ans %= (10**9+7)
else:
  for i in range(k-1):
    if i==p2:
      continue
    ans *= a_abs[i][0] % (10**9+7)
    ans %= (10**9+7)
  ans *= a_abs[p4][0]
  ans %= (10**9+7)

print(ans)

Submission status: Wrong Answer

Solution code:
import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 1
if max(a)==0:
  print(0)
  exit()
elif max(a)<0 and k%2==1:
  a = sorted(a)[::-1]
  for i in range(k):
    ans *= a[i]
    if ans>(10**9+7):
      ans %= (10**9+7)
    elif ans<(10**9+7):
      ans += math.ceil(ans * (10**9+7)) * (-1)
  ans %= (10**9+7)
  print(abs(ans))
  exit()

a_abs = [[a_, abs(a_)] for a_ in a]
a_abs = sorted(a_abs, key=lambda x: -x[-1])

cnt = 0
for i in range(k):
  if a_abs[i][0]<0:
    cnt += 1

if cnt%2==0:
  for i in range(k):
    ans *= a_abs[i][0]
    if ans>(10**9+7):
      ans %= (10**9+7)
    elif ans<(10**9+7):
      ans += math.ceil(ans * (10**9+7)) * (-1)
  ans %= (10**9+7)
  print(ans)
  exit()
  
p1 = -1
p2 = -1
for i in range(k-1,-1,-1):
  if p1==-1 and a_abs[i][0] > 0:
    p1 = i
  elif p2==-1 and a_abs[i][0] < 0:
    p2 = i
  elif p1!=-1 and p2!=-1:
    break

p3 = -1
p4 = -1
for i in range(k, n):
  if p3==-1 and a_abs[i][0] < 0:
    p3 = i
  elif p4==-1 and a_abs[i][0] > 0:
    p4 = i
  elif p3!=-1 and p4!=-1:
    break

if a_abs[p3][1]*a_abs[p2][1]>a_abs[p4][1]*a_abs[p1][1]:
  for i in range(k-1):
    if i==p1:
      continue
    ans *= a_abs[i][0]
    if ans>(10**9+7):
      ans %= (10**9+7)
    elif ans<(10**9+7):
        ans += math.ceil(ans * (10**9+7)) * (-1)
  ans *= a_abs[p3][0]
  ans %= (10**9+7)
else:
  for i in range(k-1):
    if i==p2:
      continue
    ans *= a_abs[i][0]
    if ans>(10**9+7):
      ans %= (10**9+7)
    elif ans<(10**9+7):
        ans += math.ceil(ans * (10**9+7)) * (-1)
  ans *= a_abs[p4][0]
  ans %= (10**9+7)

print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
A.sort(key=lambda x:-abs(x))
mod=10**9+7

ans=1
if max(A)<=0 or n==k:
    for i in range(k):
        ans=ans*A[n-1-i]%mod
else:
    mi=0
    pl=0
    flg=1
    for i in range(k):
        ans=ans*A[i]%mod
        if A[i]>0:
            pl=A[i]
        if A[i]<0:
            mi=A[i]
            flg*=-1
    if ans==0:
        pass
    elif flg==-1:
        mi2=None
        pl2=None
        for i in range(k,n):
            if A[i]>=0:
                pl2=A[i]
                break
        for i in range(k,n):
            if A[i]<=0:
                mi2=A[i]
                break
        can=0
        if mi!=0 and pl2 is not None and pl!=0 and mi2 is not None:
            if pl2*pl < mi2*mi:
                can = pow(mi,-1,mod)*pl2%mod
            else:
                can = pow(pl,-1,mod)*mi2%mod
        elif mi!=0 and pl2 is not None:
            can = pow(mi,-1,mod)*pl2%mod
        elif pl!=0 and mi2 is not None:
            can = pow(pl,-1,mod)*mi2%mod 
        ans=ans*can%mod

print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
A.sort(key=lambda x:-abs(x))
mod=10**9+7

ans=1
if max(A)<=0 or n==k:
    for i in range(k):
        ans=ans*A[n-1-i]%mod
else:
    mi=0
    pl=0
    flg=1
    for i in range(k):
        ans=ans*A[i]%mod
        if A[i]>0:
            pl=A[i]
        if A[i]<0:
            mi=A[i]
            flg*=-1
    if ans==0:
        pass
    elif flg==-1:
        mi2=None
        pl2=None
        for i in range(k,n):
            if A[i]>=0:
                pl2=A[i]
                break
        for i in range(k,n):
            if A[i]<=0:
                mi2=A[i]
                break
        can=0
        if mi!=0 and pl2 is not None and pl!=0 and mi2 is not None:
            if pl2*pl > mi2*mi:
                can = pow(mi,-1,mod)*pl2%mod
            else:
                can = pow(pl,-1,mod)*mi2%mod
        elif mi!=0 and pl2 is not None:
            can = pow(mi,-1,mod)*pl2%mod
        elif pl!=0 and mi2 is not None:
            can = pow(pl,-1,mod)*mi2%mod 
        ans=ans*can%mod

print(ans)

Submission status: Wrong Answer

Solution code:
import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 1
if max(a)==0:
  print(0)
  exit()
elif max(a)<0 and k%2==1:
  a = sorted(a)[::-1]
  for i in range(k):
    ans *= a[i]
    if ans>(10**9+7):
      ans %= (10**9+7)
    elif ans<(10**9+7):
      ans += math.ceil(ans * (10**9+7)) * (-1)
  ans %= (10**9+7)
  print(abs(ans))
  exit()

a_abs = [[a_, abs(a_)] for a_ in a]
a_abs = sorted(a_abs, key=lambda x: -x[-1])

cnt = 0
for i in range(k):
  if a_abs[i][0]<0:
    cnt += 1

if cnt%2==0:
  for i in range(k):
    ans *= a_abs[i][0]
    if ans>(10**9+7):
      ans %= (10**9+7)
    elif ans<(10**9+7):
      ans += math.ceil(ans * (10**9+7)) * (-1)
  ans %= (10**9+7)
  print(ans)
  exit()
  
p1 = -1
p2 = -1
for i in range(k-1,-1,-1):
  if p1==-1 and a_abs[i][0] > 0:
    p1 = i
  elif p2==-1 and a_abs[i][0] < 0:
    p2 = i
  elif p1!=-1 and p2!=-1:
    break

ans1 = 1
ans2 = -1
for i in range(k):
  if i!=p1:
    ans1 *= a_abs[i][0]
  if i!=p2:
    ans2 *= a_abs[i][0]
  if ans1>(10**9+7):
    ans1 %= (10**9+7)
  elif ans1<(10**9+7):
      ans1 += math.ceil(ans1 * (10**9+7)) * (-1)
  if ans2>(10**9+7):
    ans2 %= (10**9+7)
  elif ans2<(10**9+7):
      ans2 += math.ceil(ans2 * (10**9+7)) * (-1)

flag1 = 0
flag2 = 0
for i in range(k, n):
  if flag1==0 and a_abs[i][0]<0:
    ans1 *= a_abs[i][0]
    ans1 %= (10**9+7)
    flag1 = 1
  if flag2==0 and a_abs[i][0]>0:
    ans2 *= a_abs[i][0]
    ans2 %= (10**9+7)
    flag2 = 1
  if flag1==1 and flag2==1:
    break

print(max(ans1, ans2))

Submission status: Wrong Answer

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

A.sort()
S=sorted(A)

Min=[]

for i in A:
  if(i<0):
    Min.append(S.pop(0))
  else:
    break


S.sort(reverse=True)

print(Min,S,A)

ans=int(1)

if( len(S)==0 and K%2==1 ):
  for i in range(K):
    ans *= Min[len(Min)-i-1]

elif(N==K):
  for i in A:
    ans *= i

else:
  while(K>0):
    if(K==1):
      ans*=S.pop(0)
      K -=1
    elif(len(S)<=1):
      ans *= Min.pop(0)
      ans *= Min.pop(0)
      K -= 2
    elif(len(Min)<=1):
      ans *= S.pop(0)
      ans *= S.pop(0)
      K -=2
    elif(S[0]*S[1]<Min[0]*Min[1]):
      ans *= Min.pop(0)
      ans *= Min.pop(0)
      K -= 2
    else:
      ans *= S.pop(0)
      ans *= S.pop(0)
      K -=2

print(ans)

Submission status: Wrong Answer

Solution code:
## necessary imports
import sys
input = sys.stdin.readline
# from math import ceil, floor, factorial;

def ceil(x):
    if x != int(x):
        x = int(x) + 1;
    return x;
    
# swap_array function
def swaparr(arr, a,b):
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp

## gcd function
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b, a % b);

## nCr function efficient using Binomial Cofficient
def nCr(n, k): 
    if(k > n - k): 
        k = n - k 
    res = 1
    for i in range(k): 
        res = res * (n - i) 
        res = res / (i + 1) 
    return int(res) 

## upper bound function code -- such that e in a[:i] e < x;
def upper_bound(a, x, lo=0, hi = None):
    if hi == None:
        hi = len(a);
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x:
            lo = mid+1
        else:
            hi = mid
    return lo

## prime factorization
def primefs(n):
    ## if n == 1    ## calculating primes
    primes = {}
    while(n%2 == 0 and n > 0):
        primes[2] = primes.get(2, 0) + 1
        n = n//2
    for i in range(3, int(n**0.5)+2, 2):
        while(n%i == 0 and n > 0):
            primes[i] = primes.get(i, 0) + 1
            n = n//i
    if n > 2:
        primes[n] = primes.get(n, 0) + 1
    ## prime factoriazation of n is stored in dictionary
    ## primes and can be accesed. O(sqrt n)
    return primes

## MODULAR EXPONENTIATION FUNCTION
def power(x, y, p): 
    res = 1
    x = x % p  
    if (x == 0) : 
        return 0
    while (y > 0) : 
        if ((y & 1) == 1) : 
            res = (res * x) % p 
        y = y >> 1      
        x = (x * x) % p 
    return res 

## DISJOINT SET UNINON FUNCTIONS
def swap(a,b):
    temp = a
    a = b
    b = temp
    return a,b

# find function with path compression included (recursive)
# def find(x, link):
#     if link[x] == x:
#         return x
#     link[x] = find(link[x], link);
#     return link[x];

# find function with path compression (ITERATIVE)
def find(x, link):
    p = x;
    while( p != link[p]):
        p = link[p];
    
    while( x != p):
        nex = link[x];
        link[x] = p;
        x = nex;
    return p;


# the union function which makes union(x,y)
# of two nodes x and y
def union(x, y, link, size):
    x = find(x, link)
    y = find(y, link)
    if size[x] < size[y]:
        x,y = swap(x,y)
    if x != y:
        size[x] += size[y]
        link[y] = x

## returns an array of boolean if primes or not USING SIEVE OF ERATOSTHANES
def sieve(n): 
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
    return prime

#### PRIME FACTORIZATION IN O(log n) using Sieve ####
MAXN = int(1e5 + 5)
def spf_sieve():
    spf[1] = 1;
    for i in range(2, MAXN):
        spf[i] = i;
    for i in range(4, MAXN, 2):
        spf[i] = 2;
    for i in range(3, ceil(MAXN ** 0.5), 2):
        if spf[i] == i:
            for j in range(i*i, MAXN, i):
                if spf[j] == j:
                    spf[j] = i;
    ## function for storing smallest prime factors (spf) in the array

################## un-comment below 2 lines when using factorization #################
# spf = [0 for i in range(MAXN)]
# spf_sieve();
def factoriazation(x):
    ret = {};
    while x != 1:
        ret[spf[x]] = ret.get(spf[x], 0) + 1;
        x = x//spf[x]
    return ret
    ## this function is useful for multiple queries only, o/w use
    ## primefs function above. complexity O(log n)

## taking integer array input
def int_array():
    return list(map(int, input().strip().split()))
## taking string array input
def str_array():
    return input().strip().split();

#defining a couple constants
MOD = int(1e9)+7;
CMOD = 998244353;
INF = float('inf'); NINF = -float('inf');

################### ---------------- TEMPLATE ENDS HERE ---------------- ###################

n, k = int_array(); a = int_array();

## Case 1
if k == n:
    ans = 1;
    for i in a:
        ans = (ans * i) % MOD;
    print(ans % MOD); exit();

## Case 2 (ALl Negative)
negs = 0;
for i in a:
    if i < 0:
        negs += 1;
if negs == n:
    if k & 1:
        a.sort(reverse = 1); ans = 1;
        for i in range(k):
            ans = (ans * a[i]) % MOD;
        print(ans % MOD);
    else:
        a.sort(); ans = 1;
        for i in range(k):
            ans = (ans * a[i]) % MOD;
        print(ans % MOD);
    exit();

## Case 3 (some positive and some negative);
a.sort(reverse = 1, key = lambda x: abs(x)); ans = 1;
for i in range(k):
    ans = (ans * a[i]) % MOD;
if ans > 0:
    print(ans % MOD); exit();

mine = a[:k].copy(); not_mine = a[k:].copy();
amine = mine.copy(); anot_mine = not_mine.copy();

xmx = INF;
for i in mine:
    if i > 0:
        xmx = min(xmx, i);
xmn = INF;
for i in not_mine:
    if i < 0:
        xmn = min(xmn, i);
answer1 = 1; answer2 = 1;
if xmx != INF and xmn != INF:
    mine.remove(xmx); mine.append(xmn);
    for i in mine:
        answer1 = (answer1 * i) % MOD;
    answer1 %= MOD;
xmx = NINF;
for i in amine:
    if i < 0:
        xmx = max(xmx, i);
xmn = NINF;
for i in anot_mine:
    if i > 0:
        xmn = max(xmn, i);
if xmx != NINF and xmn != NINF:
    amine.remove(xmx); amine.append(xmn);
    for i in amine:
        answer2 = (answer2 * i) % MOD;
    answer2 %= MOD;
print(max(answer1, answer2));