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:
def main():

    N, K = map(int, input().split())
    A = sorted([int(i) for i in input().split()])
    MOD = 10 ** 9 + 7
    ans = 0

    start = 0
    end = N - 1
    k, m = divmod(K, 2)
    for i in range(k):
        start_sum = A[start] * A[start + 1]
        end_sum = A[end] * A[end - 1]
        # print(start_sum, end_sum, k)
        if start_sum >= end_sum:
            ans += start_sum % MOD
            ans %= MOD
            start += 2
        else:
            ans += end_sum % MOD
            ans %= MOD
            end -= 2

    if m:
        ans += A[start]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

mod = 10**9+7
n,k = na()
a = na()
a.sort()

ans = 1

if k == 1:
    print(a[-1])
    exit()

if a[-1] <= 0 and k%2==1:
    for i in range(n-k,n):
        ans = ans*a[i]%mod
    print(ans%mod)
    exit()

s = 0
e = -1

while k > 0:
    if k == 1:
        if a[s] > a[e]:
            ans = ans*a[s]%mod
        else:
            ans = ans*a[e]%mod
        break
    p = a[s]*a[s+1]
    q = a[e]*a[e-1]
    if p > q:
        ans = p%mod*ans%mod
        s+=2
    else:
        ans = q%mod*ans%mod
        e-=2
    k-=2

print(ans%mod)

Submission status: Wrong Answer

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

sei=[]
hu=[]
ans=1
preans=1

for num in list:
    if num>=0:
        sei.append(num)
    else:
        hu.append(num)

sei.sort(reverse=True)
hu.sort()


if len(sei)==0:
    if k%2==0:
        for i,num in enumerate(hu):
            if i==k:
                break
            ans=ans*num
    else:
        for i,num in enumerate(reversed(hu)):
            if i==k:
                break
            ans=ans*num

else:
    seisei=k
    while(True):
        preans=1
        if seisei>len(sei):
            seisei-=2
        else:
            for i,num in enumerate(sei):
                if i==seisei:
                    break
                preans=preans*num
            for i,num in enumerate(hu):
                if i==k-seisei:
                    break
                preans=preans*num
            if ans<preans:
                ans=preans
            seisei-=2
            if seisei<0:
                break

print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,K=map(int,input().split())

A=list(map(int,input().split()))
mod=10**9+7
Am=[-i for i in A if i<0]
Ap=[i for i in A if i>=0]

Am.sort()
Ap.sort()
Am=deque(Am)
Ap=deque(Ap)



if N-K==0 and len(Am)%2==0 or len(Ap)==0 and K%2:
    c=1
    while K and (Am or Ap) :
        if Am and Ap:
            if Am[0]<Ap[0]:
                c*=Am.popleft()
            else:
                c*=Ap.popleft()
        elif Am:
            c*=Am.popleft()
        elif Ap:
            c*=Ap.popleft()
        K-=1
        c=-c
        c%=mod
    #print("unko")

else:
    c=1
    h=0
    w=0
    a="unko"
    b="unko"
    while K and (Am or Ap) :
        if K==1 and len(Ap)==0:
            break
        while K and (Am or Ap) :
            if Am and Ap:
                if Am[0]>Ap[0]:

                    a=Am.pop()
                    c*=a
                    h+=1
                else:

                    b=Ap.pop()
                    c*=b

            elif Am:
                a=Am.pop()
                c*=a
                h+=1
            elif Ap:
                b=Ap.pop()
                c*=b
            K-=1
            c%=mod
    """if h%2==1:
        if Am and Ap:
            if Am[-1]*b>Ap[-1]*a:
                a=Am.pop()
                c*=a
                c*=pow(b,mod-2,mod)
            else:
                b=Ap.pop()
                c*=b
                c*=pow(a,mod-2,mod)
        if len(Am):
            a=Am.pop()
            c*=a
            c*=pow(b,mod-2,mod)
        else:
            b=Ap.pop()
            c*=b
            c*=pow(a,mod-2,mod)"""


print(c%mod)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def main():
    from collections import Counter
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    posi = [a for a in A if a > 0]
    nega = [a for a in A if a < 0]
    posi.sort(reverse=True)
    nega.sort(reverse=True)
    A.sort(reverse=True, key=abs)
    if len(posi) + len(nega) < K:
        # 0を含まなければいけないとき
        return print(0)

    ans = modint(1)
    if K % 2 == 1 and len(posi) < K:
        # 結果が負数
        # 絶対値が小さいやつをK個取ってくる
        A.sort(key=abs)
        for a in A[:K]:
            ans *= a
    else:
        # 結果が正になるように注意しなければいけない
        # skipしてかけるものがなくなったらこわい
        # 負数がK以下の奇数個しかないとハマる
        if sum(a < 0 for a in A[:K]) % 2 == 0:
            for a in A[:K]:
                ans *= a
        else:
            ans1 = []  # 正を取り除く
            ans2 = []  # 負を取り除く
            posi = [a for a in A[:K] if a > 0]
            nega = [a for a in A[:K] if a < 0]
            p_remove = False
            for a in A[:K][::-1]:
                if a > 0 and not p_remove:
                    p_remove = True
                    continue
                ans1.append(a)
            n_remove = False
            for a in A[:K][::-1]:
                if a < 0 and not n_remove:
                    n_remove = True
                    continue
                ans2.append(a)
            mul1 = 0  # 一番大きい正
            mul2 = 0  # 　一番大きい負
            for a in A[K:]:
                if mul1 == 0 and a > 0:
                    mul1 = a
                if mul2 == 0 and a < 0:
                    mul2 = a
                if mul1 != 0 and mul2 != 0:
                    break
            ans1.append(mul2)
            ans2.append(mul1)
            s1 = 1
            for a in ans1[:min(K, 50)]:
                s1 *= abs(a)
            s2 = 1
            for a in ans2[:min(K, 50)]:
                s2 *= abs(a)

            if mul2 == 0:
                for a in ans2:
                    ans *= a
            elif mul1 == 0:
                for a in ans1:
                    ans *= a
            else:
                if s1 < s2:
                    for a in ans2:
                        ans *= a
                elif s1 > s2:
                    for a in ans1:
                        ans *= a
                else:
                    from random import randint
                    if randint(0, 1) == 0:
                        for a in ans2:
                            ans *= a
                    else:
                        for a in ans1:
                            ans *= a
    print(int(ans) % MOD)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True, key = lambda x: abs(x))
mod = 10**9+7
nega = 0
posi = 0
zero = 0
for i in range(n):
    if a[i] > 0:
        posi += 1
    elif a[i] == 0:
        zero += 1
    else:
        nega += 1

if n == k:
    ans = 1
    for i in range(n):
        ans *= abs(a[i])
        ans %= mod
    if nega%2 == 1:
        ans *= -1

elif posi == 0:

    if k % 2 == 0:
        ans = 1
        for i in range(k):
            ans *= abs(a[i])
            ans %= mod

    else:
        if a.count(0) > 0:
            ans = 0
        else:
            a.reverse()
            ans = 1
            for i in range(k):
                ans *= abs(a[i])
                ans %= mod

            ans *= -1


else:
    posi = 0
    nega = 0
    zero = 0
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod

    for i in range(k):
        if a[i] > 0:
            posi += 1
        elif a[i] < 0:
            nega += 1
        else:
            zero += 1
    if zero > 0:
        ans = 0

    elif nega % 2 != 0:
        minposi = 0
        minnega = 0
        for i in range(k-1, -1, -1):
            if a[i] > 0:
                if minposi == 0:
                    minposi = a[i]
            else:
                if minnega == 0:
                    minnega = a[i]

        maxposi = 0
        maxnega = 0
        for i in range(k, n):
            if a[i] > 0:
                if maxposi == 0:
                    maxposi = a[i]
            else:
                if maxnega == 0:
                    maxnega = a[i]

        if abs(minposi*maxposi) < abs(minnega*maxnega):
            ans *= pow(abs(minposi), mod-2, mod)
            ans *= abs(maxnega)
        else:
            ans *= pow(abs(minnega), mod-2, mod)
            ans *= abs(maxposi)

print(ans % mod)

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    N, K = in_nn()
    A = in_nl()
    mod = 10 ** 9 + 7

    Am = []
    Ap = []
    zero = False

    for i in range(N):
        if A[i] < 0:
            Am.append(A[i])
        elif A[i] > 0:
            Ap.append(A[i])
        elif A[i] == 0:
            zero = True

    Am = list(sorted(Am, reverse=True))
    Ap = list(sorted(Ap, reverse=True))

    Am_min = list(sorted(Am))
    Ap_min = list(sorted(Ap))

    NP = len(Ap)
    NM = len(Am)

    if NM + NP < K:
        print(0)
        exit()

    if NM == 0:
        ans = 1
        for i in range(K):
            ans *= Ap[i]
            ans %= mod
        print(ans)
        exit()

    if NP == 0:
        if zero:
            print(0)
            exit()
        else:
            if K % 2 == 0:
                ans = 1
                for i in range(K):
                    ans *= Am_min[i]
                    ans %= mod
                print(ans)
                exit()
            else:
                ans = 1
                for i in range(K):
                    ans *= Am[i]
                    ans %= mod
                print(ans)
                exit()

    if NM == 1:
        if NP >= K:
            ans = 1
            for i in range(K):
                ans *= Ap[i]
                ans %= mod
            print(ans)
            exit()
        if zero:
            print(0)
            exit()
        else:
            ans = Am[0]
            for i in range(NP):
                ans *= Ap[i]
                ans %= mod
            print(ans)
            exit()

    if K % 2 == 0:
        if NP % 2 == 0:
            pi = NP
            mi = 0
        else:
            pi = NP - 1
            mi = 2
    else:
        if NP % 2 == 0:
            pi = NP - 1
            mi = 2
        else:
            pi = NP
            mi = 0

    max_rate = 1
    max_i = (pi, mi)
    rate = 1

    #print(pi, mi)
    while True:
        pi -= 2
        mi += 2
        if pi < 0 or mi > NM:
            break
        else:
            rate *= (Am[mi - 2] * Am[mi - 1] / Ap[pi] / Ap[pi + 1])
            if max_rate < rate:
                max_rate = rate
                max_i = (pi, mi)

    ans = 1
    for i in range(max_i[0]):
        ans *= Ap[i]
        ans %= mod
    for i in range(max_i[1]):
        ans *= Am[i]
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy
mod=10**9+7
n,k=map(int,input().split())
K=copy.deepcopy(k)
A=list(map(int,input().split()))

plus,negative=[],[]
for i in A:
    if i>0:plus.append(i)
    else:negative.append(i)

plus.sort()
negative.sort()

B,C=[],[]
N,M=len(plus),len(negative)
for i in range(0,N,2):
    if i+1==N:B.append([plus[i],plus[i]])
    else:B.append([plus[i]*plus[i+1],plus[i],plus[i+1]])
for i in range(0,M,2):
    if i+1==M:C.append([negative[i],negative[i]])
    else:C.append([negative[i]*negative[i+1],negative[i],negative[i+1]])

B.sort(reverse=True)
C.sort(reverse=True)
D=copy.deepcopy(B)
E=copy.deepcopy(C)

B=deque(B)
C=deque(C)

ans,flag=1,0
while k!=0:
    if k==1:
        if ans>0:
            if len(B)>0:ans *=B.popleft()[-1]
            else:ans *=sorted(C.popleft())[0]
        else:
            if len(C)>0:ans *=sorted(C.popleft())[0]
            else:ans *=sorted(B.popleft())[0]
        if ans<0:flag=1
        ans %=mod
        break
    else:
        if 0<len(B) and 0<len(C):
            if B[0][0]<C[0][0]:num=C.popleft()
            else:num=B.popleft()
            k -=len(num)-1
        elif len(B)==0:
            num=C.popleft()
            k -=len(num)-1
        else:
            num=B.popleft()
            k -=len(num)-1
        if ans<0:flag=1
        ans *=num[0]
        ans %=mod

if flag:
    k=K
    ans=1
    D.sort()
    E.sort()
    D=deque(D)
    E=deque(E)

    while k!=0:
        if k==1:
            if ans>0:
                if len(E)>0:ans *=sorted(E.popleft())[-2]
                else:ans *=sorted(D.popleft())[0]
            else:
                if len(D)>0:ans *=sorted(D.popleft())[0]
                else:ans *=sorted(E.popleft())[-2]
            ans %=mod
            break
        else:
            if 0<len(D) and 0<len(E):
                if D[0][0]<E[0][0]:
                    num=D.popleft()
                else:
                    num=E.popleft()
                k -=len(num)-1
            elif len(D)==0:
                num=E.popleft()
                k -=len(num)-1
            else:
                num=D.popleft()
                k -=len(num)-1
            ans *=num[0]
            ans %=mod
    print(ans%mod)
else:print(ans%mod)

Submission status: Wrong Answer

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

if sum(v == 0 for v in A) > N - K:
    print(0)
    exit()

p_num = sum(v > 0 for v in A)
z_num = sum(v == 0 for v in A)
m_num = sum(v < 0 for v in A)
if N - z_num - m_num < K and z_num > 0:
    print(0)
    exit()
if all(v <= 0 for v in A):
    if K % 2 == 1 and any(v == 0 for v in A):
        print(0)
        exit()
    x = sorted([v for v in A if v < 0])
    ans = 1
    if K % 2 == 0:
        for i in range(K):
            ans = ans * x[i] % MOD
    else:
        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:
MOD = 10 ** 9 + 7


def mod_mul(arr, mod):
    res = 1
    for elem in arr:
        res *= elem
        res %= mod
    return res


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(key=lambda x: abs(x), reverse=True)

    if all([e <= 0 for e in a]):
        print(mod_mul(a[n - k:], MOD))
        return

    if k == 1:
        print(max(a))
        return

    if k == n:
        print(mod_mul(a, MOD))
        return

    res = 1
    if sum(a[i] < 0 for i in range(k)) % 2 == 1:
        minus_flag = False
        for i in range(k - 1, -1, -1):
            if a[i] < 0:
                if not minus_flag:
                    res *= a[i]
                    res %= MOD
                    minus_flag = True
            else:
                res *= a[i]
                res %= MOD
        for i in range(k, n):
            if a[i] >= 0:
                res *= a[i]
                res %= MOD
                break
    else:
        for i in range(k):
            res *= a[i]
            res %= MOD

    print(res)


main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse = True)

n = 0
m = N-1
ans = 1
if A[n] <= 0:
  if K%2 == 1:
    for i in range(K):
      ans *= A[i]
  else:
    for i in reversed(range(N - K, N)):
      ans *= A[i]
elif A[m] >=0:
  for i in range(K):
    ans += A[i]
else:
  cnt = 0
  b = 0
  while cnt < K:
    if (A[n] * A[n+1] < A[m] * A[m-1]) & cnt+2 <= K:
      ans *= A[m] * A[m-1]
      m -= 2
      cnt += 2
    else:
      ans *= A[n]
      n += 1
      cnt += 1
print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
mod = 10**9 + 7
plus = []
minus = []
zlen = 0
for i in map(int, input().split()):
    if i > 0:
        plus.append(i)
    elif i < 0:
        minus.append(i)
    else:
        zlen += 1
plen = len(plus)
mlen = len(minus)
# if K > plen + mlen:
#     print(0)
#     import sys
#     sys.exit()
plus.sort(reverse=True)
minus.sort()
pp = [1]
mp = [1]
for p in plus:
    pp.append((pp[-1]*p)%mod)
for m in minus:
    mp.append((mp[-1]*(-m))%mod)
ppm = [1]
mpm = [1]
for p in plus[::-1]:
    ppm.append((ppm[-1]*p)%mod)
for m in minus[::-1]:
    mpm.append((mpm[-1]*(-m))%mod)
ans = -float("inf")
ans_m = float("inf")
# kこマイナスから選ぶ
for k in range(K+1):
    if mlen < k:
        continue
    if plen < K-k:
        continue
    # 最大を目指す
    if k % 2 == 0:
        tmp = mp[k] * pp[K-k]
        ans = max(ans, tmp)
    # 絶対値最小を目指す
    else:
        tmp = mpm[k] * ppm[K-k]
        ans_m = min(ans_m, tmp)
if ans == -float("inf"):
    ans = -ans_m
if ans < 0 and zlen > 0:
    print(0)
    import sys
    sys.exit()
print(ans%mod)