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()))
mod = 10**9+7

ans = 1
sei = 0
for i in a:
    if i>0:
        sei += 1

if sei+(n-sei)//2>=k:
    b = sorted(a, key=lambda x: abs(x),reverse=True)
    buf = 0
    last = 1
    for i in range(n):
        if i<k:
            if b[i]>0:
                ans = ans*b[i]
                last = b[i]
            else:
                if buf==0:
                    buf = b[i]
                else:
                    ans = ans*b[i]*buf
                    buf = 0
        else:
            if buf!=0:
                if b[i]<0:
                    if ans//last*buf*b[i]>ans:
                        ans = ans//last*buf*b[i]
                        buf = 0
            else:
                break
        ans %= mod
else:
    b = sorted(a, key=lambda x: abs(x))
    for i in range(k):
        ans *= b[i]
    ans %= mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft



def main():
    n, k = map(int, input().split())
    a = sorted([(abs(i), (1 if i > 0 else -1)) for i in map(int, input().split())], reverse=True)
    if n == k:
        s = 1
        for x in a:
            s = s * x[0] * x[1] % mod
        print(s)
        return
    if len([i for i in a if i[1] == -1]) == n:
        if k % 2 == 0:
            s = 1
            for i in a[:k]:
                s = (s + i[0]) % mod
            print(s)
        else:
            s = 1
            for i in a[-k:]:
                s = (s * i[0]) % mod
            print((-s) % mod)
        return
    s = 1
    c = 1
    for i in range(k):
        s = s * a[i][0] % mod
        c *= a[i][1]
    if c == 1:
        print(s)
        return
    j = 0
    for i in range(k):
        if a[i][1] == -1:
            j = i
    s = (s - a[j][0]) % mod
    for i in range(k, n):
        if a[i][1] == 1:
            print(s * a[i][0] % mod)
            return

main()

Submission status: Wrong Answer

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

import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def solve(N: int, K: int, A: "List[int]"):
    nn = 0
    ns = []
    ps = []
    for a in A:
        if a <= 0:
            nn += 1
            ns.append(a)
        else:
            ps.append(a)
    pp = N - nn
    if N == K or nn == N:
        ret = 1
        for i in range(K):
            ret *= A[i]
            ret %= MOD
    elif pp < K: # pp > 0
        min_nn = K - pp
        if min_nn % 2:
            min_nn += 1
        ns.sort()
        ret = 1
        for i in range(min_nn):
            ret *= ns[i]
            ret %= MOD
        ps.sort(reverse=True)
        for i in range(K - min_nn):
            ret *= ps[i]
            ret %= MOD
    else:
        ret = 1
        A.sort(key=lambda x: abs(x), reverse=True)
        neg = []
        for i in range(K):
            if A[i] > 0:
                ret *= A[i]
                ret %= MOD
            else:
                neg.append(A[i])
        if len(neg) % 2 == 0:
            for ne in neg:
                ret *= ne
                ret %= MOD
        else:
            for ne in neg[:-1]:
                ret *= ne
                ret %= MOD
            ret *= A[K]
            ret %= MOD
    print(ret)
    return

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()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


mod = 10 ** 9 + 7

n, k = LI()
A = LI()
A = [[abs(a), a] for a in A]
ret = 1
flg = 0
z_flg = 0
A.sort(reverse=True)
for i in range(n):
    if A[i][1] >= 0:
        flg = 1
    if A[i][1] == 0:
        z_flg = 1

if flg == 0:
    A.reverse()


ret = 1
abs_max_minus = -INF
minus_flg1 = 0
plus_flg1 = 0
minus_flg2 = 0
plus_flg2 = 0
for i in range(k):
    ret = ret * A[i][1] % mod
    if A[i][1] < 0:
        abs_max_minus = max(abs_max_minus, A[i][1])
        minus_flg1 = 1
    if A[i][1] > 0:
        plus_flg1 = 1


abs_max_plus_remain = 0
for j in range(k, n):
    if A[j][1] > 0:
        abs_max_plus_remain = max(abs_max_plus_remain, A[j][1])
        plus_flg2 = 1
    elif A[j][1] < 0:
        minus_flg2 = 1


if n == k:
    print(ret)
    exit()

if ret < 0:
    if (plus_flg1 and minus_flg2) or (minus_flg1 and plus_flg2):
        ret //= abs_max_minus
        ret *= abs_max_plus_remain

if ret < 0 and z_flg:
    print(0)
else:
    print(ret % mod)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
mn = []
zr = 0
pl = []
t = []
for x in a:
  if x < 0:
    mn.append(-x)
    t.append((-x, 0))
  elif x == 0: zr += 1
  else:
    pl.append(x)
    t.append((x, 1))

if N - zr < K:
  print(0)
  exit(0)

t.sort(reverse = True)
c = 0
res = 1
lpl = -1
for x, cc in t[: K]:
  res *= x
  res %= mod
  c ^= (cc == 0)
  if cc: lpl = x
if c == 0:
  print(res)
  exit(0)
for x, cc in t[K: ]:
  if cc:
    res *= pow(lpl, mod - 2, mod)
    res %= mod
    res *= x
    res %= mod
    print(res)
    exit(0)
if zr:
  print(0)
  exit(0)
res = 1
t.reverse()
for x, _ in t[: K]:
  res *= x
  res %= mod
print(-res % mod)

Submission status: Wrong Answer

Solution code:
from sys import stdin
n,k = map(int,stdin.readline().split())
arr = sorted(list(map(int,stdin.readline().split())),key=lambda x:abs(x))
mod = 10**9+7
pos,neg = [],[]
for i in arr:
    if i>0:
        pos.append(i)
    else:
        neg.append(i)
if not len(pos):
    ans = 1
    if k%2:
        for i in range(k):
            ans *= neg[i]
            ans %= mod
    else:
        for i in range(k):
            ans *= neg[-1-i]
            ans %= mod
else:
    poi = len(pos)-1
    poi_n = len(neg)-1
    ans = 1
    for i in range(k-1):
        if arr[-1-i]>0:
            poi -= 1
        else:
            poi_n -= 1
        ans *= arr[-1-i]
        ans %= mod
    if (len(neg)-1-poi_n)%2:
        ans *= neg[poi_n]
        ans %= mod
    else:
        ans *= pos[poi]
        ans %= mod
print(ans)

Submission status: Wrong Answer

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

from collections import deque
a = list(map(int, input().split()))
a.sort()
minus, zero, plus = 0, 0, 0
for i in range(n):
    if a[i] < 0:
        minus += 1
    elif a[i] == 0:
        zero += 1
    else:
        plus += 1

que = deque(a)


#plus可能
if plus >= k:
    ans = 1
    cnt = 0 
    
    while cnt < k:
        if k - cnt >= 2:
            cnt += 2
            if que[0] * que[1] >= que[-1] * que[-2]:
                ans *= que.popleft()
                ans *= que.popleft()
                ans %= mod
            else:
                ans *= que.pop()
                ans *= que.pop()
                ans %= mod
        else:
            ans *= que.pop()
            ans %= mod
            cnt += 1

    print(ans)

elif (minus // 2) * 2 + plus >= k:
    ans = 1
    cnt = 0 
    
    while cnt < k:
        if k - cnt >= 2:
            cnt += 2
            if que[0] * que[1] >= que[-1] * que[-2]:
                ans *= que.popleft()
                ans *= que.popleft()
                ans %= mod
            else:
                ans *= que.pop()
                ans *= que.pop()
                ans %= mod
        else:
            ans *= que.pop()
            ans %= mod
            cnt += 1

    print(ans)

#zero
elif zero > 0:
    print(0)

#minus
else:
    a = [abs(a[i]) for i in range(n)]
    a.sort()
    ans = 1
    for i in range(k):
        ans *= a[i]
        ans %= mod
    ans = -ans % mod
    print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
s=1
c=0
l=0
r=-1
while True:
    if k-c>=2:
        if a[r]*a[r-1]>=a[l]*a[l+1]:
            s*=a[r]*a[r-1]
            r-=2
            c+=2
        else:
            s*=a[l]*a[l+1]
            l+=2
            c+=2
    else:
        s*=a[r]
        c+=1
    s%=10**9+7
    if k==c:break
print(s)

Submission status: Wrong Answer

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

mod = 10**9+7

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

if K > cp+cm:
    ans = 0
elif (cp == 0 and K%2 == 1) or (K == N and cm > 0):
    if N > cp+cm:
        ans = 0
    else:
        A.sort()
        ans = 1
        for i in range(K):
            ans *= A[i][0]
            ans %= mod
        ans *= -1
        ans %= mod
else:
    A.sort(reverse=True)
    cnt = 0
    ans = 1
    for i in range(K):
        ans *= A[i][0]
        ans %= mod
        if A[i][1] < 0:
            cnt += 1

    if cnt % 2 == 1:
        for i in range(K, N):
            if A[i][1] < 0:
                ans *= A[i][0]
                ans %= mod
        for i in range(K-1, -1, -1):
            if A[i][0] < 0:
                ans *= pow(A[i][0], mod-2, mod)
                ans %= mod

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

if max(a)<0:
  if k%2==0:
    a.sort()
    ans=1
    for i in a[:k]:
      ans*=i
      ans%=mod
    print(ans)
  else:
    a.sort(reverse=1)
    ans=1
    for i in a[:k]:
      ans*=i
      ans%=mod
    print(ans)
  exit()
if n==k:
  ans=1
  for i in a:
    ans*=i
    ans%=mod
  print(ans)
  exit()
if k==1:
  print(max(a))
  exit()


p=[]
m=[]
for i in a:
  if i<0:m.append(i)
  elif i>0:p.append(i)

h=[]
for i in p:h.append((i*i,i,1))
for _ in range(a.count(0)):h.append((0,0,1))
m.sort()
if len(m)%2==1:m=m[:-1]
for i in range(0,len(m),2):
  t=m[i]*m[i+1]
  h.append((t,t,2))
h.sort(reverse=1)
ans=1
for _,t,c in h:
  if c>k:continue
  k-=c
  ans*=t
  ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


mod = 10 ** 9 + 7

n, k = LI()
A = LI()
A = [[abs(a), a] for a in A]
ret = 1
flg = 0
A.sort(reverse=True)
for i in range(n):
    if A[i][1] >= 0:
        flg = 1

if flg == 0:
    A.reverse()


ret = 1
abs_max_minus = -INF
minus_flg1 = 0
plus_flg1 = 0
minus_flg2 = 0
plus_flg2 = 0
for i in range(k):
    ret = ret * A[i][1] % mod
    if A[i][1] < 0:
        abs_max_minus = max(abs_max_minus, A[i][1])
        minus_flg1 = 1
    if A[i][1] > 0:
        plus_flg1 = 1


abs_max_plus_remain = 0
for j in range(k, n):
    if A[j][1] > 0:
        abs_max_plus_remain = max(abs_max_plus_remain, A[j][1])
        plus_flg2 = 1
    elif A[j][1] < 0:
        minus_flg2 = 1


if n == k:
    print(ret)
    exit()

if ret < 0:
    if (plus_flg1 and minus_flg2) or (minus_flg1 and plus_flg2):
        ret //= abs_max_minus
        ret *= abs_max_plus_remain


print(ret % mod)

Submission status: Wrong Answer

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

P = []
M = []
for i in A:
  if i < 0:
    M.append(abs(i))
  if i > 0:
    P.append(i)

if len(M) + len(P) < K:
  print(0)
  exit()
elif len(M) + len(P) == K:
  ans = 1
  for i in M:
    ans = ans * i % MOD
  for i in P:
    ans = ans * i % MOD
  if len(M) % 2 == 1:
    ans *= -1
    ans += MOD
  print(ans)
  exit()

M.sort(reverse = True)
P.sort(reverse = True)

if len(P) == 0:
  ans = 1
  if K % 2 == 0:
    for i in range(K):
      ans = ans * M[i] % MOD
  else:
    for i in range(K):
      ans = ans * M[-1 -i] % MOD
    ans *= -1
    while ans < 0:
      ans += MOD
  print(ans)
else:
  ans = 1
  pn = 0
  mn = 0
  if K % 2 == 1:
    K -= 1
    ans *= P[0]
    pn = 1
  for i in range(K // 2):
    if pn + 2 >= len(P):
      ans = ans * M[mn] * M[mn + 1] % MOD
      mn += 2
    elif mn + 2 >= len(M):
      ans = ans * P[pn] * P[pn + 1] % MOD
      pn += 2
    else:
      p = P[pn] * P[pn + 1]
      m = M[mn] * M[mn + 1]
      if p > m:
        ans = ans * p % MOD
        pn += 2
      else:
        ans = ans * m % MOD
        mn += 2
  print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
#pyrival orz
import os
import sys
from io import BytesIO, IOBase

"""
    for _ in range(int(input())):
    n,m=map(int,input().split())
    n=int(input())
    a = [int(x) for x in input().split()]
"""

def main():
    n,k=map(int,input().split())
    a = [int(x) for x in input().split()]
    mod=10**9+7
    a.sort(key=lambda v:-abs(v))
    # print(a)
    def solve(a,k):
        ans=1
        nv=1
        for x in a:
            if k==0:
                break
            if x>0:
                ans=(ans*x)%mod
                k-=1
            if x<0:
                if nv!=1 and k>1:
                    k-=2
                    ans=(ans*x*nv)%mod
                    nv=1
                elif nv==1:
                    nv=x
        # print(a,nv,k,ans)
        if k==1 and nv!=1:
            return (ans*nv%mod,True)
        if k:
            return (0,False)
        return (ans,False)
    ans=solve(a,k)
    if ans[1]:
        a=a[::-1]
        ans=solve(a,k)
    print(ans[0])

# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

#solve
def solve():
    n, k = LI()
    a = LI()
    if n == k:
        ans = a[0]
        for i in a[1:]:
            ans *= i
            ans %= mod
        print(ans)
        return
    mi = []
    ma = []
    a.sort()
    for ai in a:
        if ai <= 0:
            heappush(mi, ai)
        else:
            heappush(ma, -ai)
    if not ma:
        ans = 1
        if k & 1:
            for i in range(k):
                ans *= a[-i - 1]
                ans %= mod
        else:
            for i in range(k):
                ans *= a[i]
                ans %= mod
        print(ans)
        return
    ans = 1
    l = []
    t = 0
    for _ in range(k - 1):
        if len(mi) <= 1:
            ans *= -ma[0]
            ans %= mod
            heappop(ma)
        else:
            if len(ma) <= 1:
                ans *= mi[0]
                ans %= mod
                heappop(mi)
                t += 1
            else:
                x = mi[0]
                y = -ma[0]
                if abs(x) < abs(y):
                    ans *= y
                    heappop(ma)
                    ans %= mod
                else:
                    ans *= x
                    heappop(mi)
                    ans %= mod
                    t += 1
    if (t & 1 and mi):
        ans *= mi[0]
    else:
        ans *= -ma[0]
    print(ans%mod)
    return


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

Submission status: Wrong Answer

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

mod = 1000000007
n, k = m_in(int)
a = l_in(int)
for res in combinations(a, k):
    total = reduce(lambda x, y: x*y, res)
    if total > ans: ans = total
ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate
import operator as op
mod = int(1e9+7)
n,k = map(int,input().split())
L=list(map(int,input().split()))
L.sort()

l1 = list(accumulate(L[:k],op.mul))
l2 = list(accumulate(L[n-k:],op.mul))

val = max(l1[-1],l2[-1])
print(val%mod)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# Author: S Mahesh Raju
# Username: maheshraju2020
# Date: 05/07/2020

from sys import stdin,stdout
from math import gcd, ceil, sqrt
from collections import Counter
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
mod = 1000000007

n, k = iia()
arr = sorted(iia(), key=lambda x: abs(x), reverse=True)
res = []
first = last = None
neg = 0
for i in range(k):
    if arr[i] < 0 and first == None:
        first = last = i
        neg += 1
    elif arr[i] < 0:
        last = i
        neg += 1

m = None
for i in range(k, len(arr)):
    if m == None:
        m = arr[i]
    else:
        m = max(m, arr[i])

if neg % 2 != 0 and m != None:
    if m > 0:
        arr[last] = m
    else:
        arr[first] = m

res = arr[0]
for i in range(1, k):
    res *= arr[i]
    res %= mod
print(res % mod)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


mod = 10 ** 9 + 7

n, k = LI()
A = LI()
A = [[abs(a), a] for a in A]
ret = 1
flg = 0
A.sort(reverse=True)
if A[0][1] < 0:
    A.reverse()


ret = 1
abs_max_minus = -INF
minus_flg1 = 0
plus_flg1 = 0
minus_flg2 = 0
plus_flg2 = 0
for i in range(k):
    ret = ret * A[i][1] % mod
    if A[i][1] < 0:
        abs_max_minus = max(abs_max_minus, A[i][1])
        minus_flg1 = 1
    if A[i][1] > 0:
        plus_flg1 = 1


abs_max_plus_remain = 0
for j in range(k, n):
    if A[j][1] > 0:
        abs_max_plus_remain = max(abs_max_plus_remain, A[j][1])
        plus_flg2 = 1
    elif A[j][1] < 0:
        minus_flg2 = 1


if n == k:
    print(ret)
    exit()

if ret < 0:
    if (plus_flg1 and minus_flg2) or (minus_flg1 and plus_flg2):
        ret //= abs_max_minus
        ret *= abs_max_plus_remain


print(ret % mod)

Submission status: Wrong Answer

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

if max(a)<0:
  if k%2==0:
    a.sort()
    ans=1
    for i in a[:k]:
      ans*=i
      ans%=mod
    print(ans)
  else:
    a.sort(reverse=1)
    ans=1
    for i in a[:k]:
      ans*=i
      ans%=mod
    print(ans)
  exit()
if a.count(0)>n-k:exit(print(0))
if n==k:
  ans=1
  for i in a:
    ans*=i
    ans%=mod
  print(ans)
  exit()

p=[]
m=[]
for i in a:
  if i<0:m.append(i)
  elif i>0:p.append(i)
h=[]
for i in p:h.append((i*i,i,1))
for _ in range(a.count(0)):h.append((0,0,1))
m.sort()
if len(m)%2==1:m=m[:-1]
for i in range(0,len(m),2):
  t=m[i]*m[i+1]
  h.append((t,t,2))
h.sort(reverse=1)
ans=1
for _,t,c in h:
  if c>k:continue
  k-=c
  ans*=t
  ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n, k = na()
a = na()

neg = []
pos = []
for i in range(n):
    if a[i] < 0:
        neg.append(a[i])
    elif a[i] > 0:
        pos.append(a[i])
neg.sort()
pos.sort(reverse=True)

lpos = [0]
for i in range(len(pos)):
    lpos.append(lpos[-1] + math.log(pos[i]))

mx = -1
arg = -1
lall = 0
for i in range(0, len(neg)+1, 2):
    if 0 <= k-i < len(lpos):
        if lall + lpos[k-i] > mx:
            mx = lall + lpos[k-i]
            arg = i
    if i+1 < len(neg):
        lall += math.log(-neg[i]) + math.log(-neg[i+1])
    else:
        break

ans = 1
mod = 1000000007
if arg == -1:
    a.sort(reverse=True)
    for i in range(k):
        ans = ans * a[i] % mod
    print(ans)
else:
    for i in range(arg):
        ans = ans * neg[i] % mod
    for i in range(k-arg):
        ans = ans * pos[i] % mod
    print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
k=1000000007
l=list(map(int,input().split()))
l.sort()
m1,m2=1,1
f=0
e=n-1
for i in range(m):
  m1=l[f]*m1
  f=f+1
  m2=l[e]*m2
  e=e-1
m3=max(m1%k,m2%k)
print(m3)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
mod = 10**9+7
ma = -10**20


comb = combinations(a, k)


for c in comb:
	ans = 1
	for item in c:
		ans *= item
	ma = max(ma, ans)

print(ma%mod)

Submission status: Wrong Answer

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

a = list(map(int, input().split()))
if k % 2 == 0:
    a = list(map(abs , a))
    a = sorted(a , reverse=True)
    ans = a[0]

    for i in range(1,k):
        ans *= a[i]
else:
    a = sorted(a , reverse=True)
    ans = a[0]
    for i in range(1 , k):
        ans *= a[i]
print(ans % (10**9 + 7))

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7

N, K = map(int, input().split())
l = list(map(int, input().split()))
pos = []
neg = []
z = 0

for v in l:
    if v > 0:
        pos.append(v)
    elif v < 0:
        neg.append(v)
    else:
        z += 1
pos.sort()
neg.sort()

if N - z < K:
    print(0)
elif N - z == K:
    if len(neg) % 2:
        print(0)
    else:
        out = 1
        for v in neg + pos:
            out *= v
            out %= 10 ** 9 + 7
        print(out)
elif len(pos) == 0:
    if K % 2:
        if z:
            print(0)
        else:
            neg.reverse()
            out = 1
            for i in range(K):
                out *= neg[i]
                out %= 10 ** 9 + 7
            print(out)
    else:
        out = 1
        for i in range(K):
            out *= neg[i]
            out %= 10 ** 9 + 7
        print(out)
else:
    out = 1
    neg.reverse()
    if K % 2:
        out = pos.pop()
        K -= 1
    while K:
        if len(pos) >= 2:
            nP = pos[-1] * pos[-2]
        else:
            nP = 0

        if len(neg) >= 2:
            nN = neg[-1] * neg[-2]
        else:
            nN = 0

        if nP > nN:
            pos.pop()
            pos.pop()
            out *= nP
        else:
            neg.pop()
            neg.pop()
            out *= nN
        out %= MOD
        K -= 2
    print(out)

Submission status: Wrong Answer

Solution code:
import sys


def solve(n, k, aaa):
    pos = []
    neg = []
    MOD = 10 ** 9 + 7
    for a in aaa:
        if a > 0:
            pos.append(a)
        elif a < 0:
            neg.append(a)
    if len(pos) + len(neg) < k:
        return 0
    if len(pos) + len(neg) == k:
        if len(neg) % 2 == 1:
            return 0
        ans = 1
        for a in pos:
            ans = ans * a % MOD
        for a in neg:
            ans = ans * a % MOD
        return ans
    if len(pos) == 0 and k % 2 == 1:
        neg.sort(reverse=True)
        ans = 1
        for a in neg[:k]:
            ans = ans * a % MOD
        return ans

    pos.sort()
    neg.sort(reverse=True)

    ans = 1
    r = k
    while r >= 2:
        if len(pos) <= 1:
            ans = ans * neg.pop() * neg.pop() % MOD
        elif len(neg) <= 1:
            ans = ans * pos.pop() * pos.pop() % MOD
        else:
            pm = pos[-1] * pos[-2]
            nm = neg[-1] * neg[-2]
            if pm > nm:
                ans = ans * pm % MOD
                pos.pop()
                pos.pop()
            else:
                ans = ans * nm % MOD
                neg.pop()
                neg.pop()
        r -= 2

    if r == 1:
        ans = ans * pos[-1] % MOD

    return ans


n, k, *aaa = map(int, sys.stdin.buffer.read().split())
print(solve(n, k, aaa))