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()))
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>0:
      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]
    if ans>0:
      ans %= (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

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 > 0:
    ans1 %= (10**9+7)
  if ans2 > 0:
    ans2 %= (10**9+7)

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 sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(key=lambda x: abs(x), reverse=True)
res = 1
cnt = 0
m1 = MOD
p2 = MOD
for a in A[:K]:
    res *= a
    res %= MOD
    if a < 0:
        m1 = a
        cnt ^= 1
    if a > 0:
        p2 = a
if cnt == 1:
    m2 = MOD
    p1 = MOD
    for a in A[K:]:
        if a >= 0 and p1 == MOD:
            p1 = a
        if a <= 0 and m2 == MOD:
            m2 = a
        if p1 != MOD and m2 != MOD:
            break
    f1 = (m1 != MOD) and (p1 != MOD)
    f2 = (m2 != MOD) and (p2 != MOD)
    if f1 and f2:
        if p1 * p2 > m1 * m2:
            res *= (pow(m1, MOD-2, MOD) * p1) % MOD
            res %= MOD
        else:
            res *= (pow(p2, MOD-2, MOD) * m2) % MOD
            res %= MOD
    elif f1:
        res *= (pow(m1, MOD-2, MOD) * p1) % MOD
        res %= MOD
    elif f2:
        res *= (pow(p2, MOD-2, MOD) * m2) % MOD
        res %= MOD
    else:
        res = 1
        for a in A[N-1:N-K-1:-1]:
            res *= a
            res %= MOD
print(res)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect


class ModInt(int):

    MOD = 10 ** 9 + 7

    def __add__(self, other):
        self = ModInt(int.__add__(self, other) % ModInt.MOD)
        return self

    def __mul__(self, other):
        self = ModInt(int.__mul__(self, other) % ModInt.MOD)
        return self

def solve_all(data):
    ans = ModInt(1)
    for d in data:
        ans *= ModInt(d)
    return ans

def solve_minus(ms, k):
    ms = list(reversed(ms))
    ans = ModInt(1)
    for i in range(k):
        ans *= ModInt(ms[i])
    return ans

def take_p(pk, mk):
    return pk + 1, mk

def take_m(pk, mk):
    return pk, mk + 1

def take(ps, pk, ms, mk):
    if not takable(ps, pk):
        return take_m(pk, mk)
    if not takable(ms, mk):
        return take_p(pk, mk)
    p = ps[pk]
    m = ms[mk]
    if p > -1 * m:
        return take_p(pk, mk)
    else:
        return take_m(pk, mk)

def ans_is_minus(mk):
    if mk % 2 == 0:
        return False
    else:
        return True

def factorize(ps, pk, ms, mk):
    ans = ModInt(1)
    for i in range(pk):
        ans *= ModInt(ps[i])
    for i in range(mk):
        ans *= ModInt(ms[i])
    return ans

def takable(s, k):
    if k < len(s):
        return True
    else:
        return False

def rm_m_add_p(pk, mk):
    return pk + 1, mk - 1

def rm_p_add_m(pk, mk):
    return pk - 1, mk + 1

def adjust(ps, pk, ms, mk):
    if not takable(ps, pk):
        return rm_p_add_m(pk, mk)
    if not takable(ms, mk):
        return rm_m_add_p(pk, mk)
    rm_p = ps[pk - 1]
    add_p = ps[pk]
    rm_m = ms[mk - 1]
    add_m = ms[mk]
    if add_p * rm_p > add_m * rm_m: # ans * add_p / abs(rm_m) > ans * abs(add_m) / rm_p
        return rm_m_add_p(pk, mk)
    else:
        return rm_p_add_m(pk, mk)


def solve_main(ps, ms, k):
    pk = 0
    mk = 0
    while k > 0:
        pk, mk = take(ps, pk, ms, mk)
        k -= 1
    if not ans_is_minus(mk):
        return factorize(ps, pk, ms, mk)
    pk, mk = adjust(ps, pk, ms, mk)
    return factorize(ps, pk, ms, mk)



def mysplit(data):
    ps = []
    ms = []
    for d in data:
        if d >= 0:
            ps.append(d)
        else:
            ms.append(d)
    ps = list(reversed(sorted(ps)))
    ms = sorted(ms)
    return ps, ms

def solve(data, k):
    if len(data) == k:
        return solve_all(data)
    ps, ms = mysplit(data)
    if len(ps) == 0 and k % 2 != 0:
        return solve_minus(ms, k)
    return solve_main(ps, ms, k)


if __name__ == '__main__':
    n, k = list(map(int, input().split()))
    data = list(map(int, input().split()))
    ans = solve(data, k)
    #print('ans') # debug
    print(ans)

    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Wrong Answer

Solution code:
import numpy as np
n, k = map(int, input().split())
A = tuple(map(int, input().split()))
A = np.array(A)
mod = 10**9+7
cz = np.sum(np.where(A == 0, 1, 0))
ap = np.sort(A[np.where(A > 0, True, False)])[::-1]
am = np.sort(A[np.where(A < 0, True, False)])
absa = sorted(A, key=lambda x: abs(x), reverse=True)

if n == k:
    ans = 1
    for a in A:
        ans *= a
        ans %= mod
    print(ans)

elif n == len(am):
    # 全てが負の場合
    if k%2 == 1:
        # kが奇数の場合積は負、絶対値が小さい方から選ぶ
        am = np.sort(am)[::-1]
        ans = am[:k].prod()
        print(ans%mod)
    else:
        # kが偶数の場合積は正、絶対値が大きい方から選ぶ
        am = np.sort(am)
        ans = am[:k].prod()
        print(ans%mod)
else:
    # kが奇数の場合積は、奇数個の正と偶数個の負で構成される
    ans = 1
    mi = -1
    pi = -1
    for i in range(k):
        ans *= absa[i]
        ans %= mod
        if absa[i] < 0:
            mi = i
        else:
            pi = i

    mans = ans
    pans = ans
    if ans < 0:
        if pi > 0 and any(map(a<0, absa[i:])):
            mans //= absa[pi]
            mans *= min(absa[i:])
            mans %= mod
        if mi > 0 and any(map(a>0, absa[i:])):
            pans //= absa[mi]
            pans *= max(absa[i:])
            pans %= mod
        ans = max(mans, pans)

    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect


class ModInt(int):

    MOD = 10 ** 9 + 7

    def __add__(self, other):
        self = ModInt(int.__add__(self, other) % ModInt.MOD)
        return self

    def __mul__(self, other):
        self = ModInt(int.__mul__(self, other) % ModInt.MOD)
        return self

def solve_all(data):
    ans = ModInt(1)
    for d in data:
        ans *= ModInt(d)
    return ans

def solve_minus(ms, k):
    ms = list(reversed(ms))
    ans = ModInt(1)
    for i in range(k):
        ans *= ModInt(ms[i])
    return ans

def take_p(pk, mk):
    return pk + 1, mk

def take_m(pk, mk):
    return pk, mk + 1

def take(ps, pk, ms, mk):
    if pk >= len(ps):
        return take_m(pk, mk)
    if mk >= len(ms):
        return take_p(pk, mk)
    p = ps[pk]
    m = ms[mk]
    if p > -1 * m:
        return take_p(pk, mk)
    else:
        return take_m(pk, mk)

def ans_is_minus(mk):
    if mk % 2 == 0:
        return False
    else:
        return True

def factorize(ps, pk, ms, mk):
    ans = ModInt(1)
    for i in range(pk):
        ans *= ModInt(ps[i])
    for i in range(mk):
        ans *= ModInt(ms[i])
    return ans

def takable(s, k):
    if k < len(s):
        return True
    else:
        return False

def rm_m_add_p(pk, mk):
    return pk + 1, mk - 1

def rm_p_add_m(pk, mk):
    return pk - 1, mk + 1

def adjust(ps, pk, ms, mk):
    if not takable(ps, pk):
        return rm_p_add_m(pk, mk)
    if not takable(ms, mk):
        return rm_m_add_p(pk, mk)
    rm_p = ps[pk - 1]
    add_p = ps[pk]
    rm_m = ms[mk - 1]
    add_m = ms[mk]
    if add_p * rm_p > add_m * rm_m: # ans * add_p / abs(rm_m) > ans * abs(add_m) / rm_p
        return rm_m_add_p(pk, mk)
    else:
        return rm_p_add_m(pk, mk)


def solve_main(ps, ms, k):
    pk = 0
    mk = 0
    while k > 0:
        pk, mk = take(ps, pk, ms, mk)
        k -= 1
    if not ans_is_minus(mk):
        return factorize(ps, pk, ms, mk)
    pk, mk = adjust(ps, pk, ms, mk)
    return factorize(ps, pk, ms, mk)



def mysplit(data):
    ps = []
    ms = []
    for d in data:
        if d >= 0:
            ps.append(d)
        else:
            ms.append(d)
    ps = list(reversed(sorted(ps)))
    ms = sorted(ms)
    return ps, ms

def solve(data, k):
    if len(data) == k:
        return solve_all(data)
    ps, ms = mysplit(data)
    if len(ps) == 0:
        return solve_minus(ms, k)
    return solve_main(ps, ms, k)


if __name__ == '__main__':
    n, k = list(map(int, input().split()))
    data = list(map(int, input().split()))
    ans = solve(data, k)
    #print('ans') # debug
    print(ans)

    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

MOD = int(1e9+7)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    q = []
    numneg = 0
    for a in A:
        if a < 0:
            heappush(q, [a, "n"])
            numneg += 1
        elif a >= 0:
            heappush(q, [-a, "p"])
    if K % 2 == 1 and numneg == N:
        ans = 1
        A.sort(reverse=True)
        for i in range(K):
            ans = (ans * A[i]) % MOD
        print(ans)
        return
    ans = 1
    is_positive = True
    prevneg = None
    prevpos = None
    for i in range(K):
        num, posneg = heappop(q)
        ans = (ans * -num) % MOD
        if posneg == "n":
            is_positive = not is_positive
            prevneg = num
        else:
            prevpos = num
    if ans != 0 and not is_positive:
        nextpos = None
        nextneg = None
        while len(q) and nextneg is None and nextpos is None:
            num, posneg = heappop(q)
            if posneg == "p" and nextpos is None:
                nextpos = num
            elif posneg == "n" and nextneg is None:
                nextneg = num
        # nextneg / prevpos < nextpos / prevneg
        if prevpos is None or nextneg is None:
            if prevneg is None or nextpos is None:
                print("error!")
                return
            ans = div(ans * nextpos, prevneg)
        elif prevneg is None or nextpos is None:
            ans = div(ans * nextneg, prevpos)
        else:
            if nextneg * prevneg < nextpos * prevpos:
                ans = div(ans * nextpos, prevneg)
            else:
                ans = div(ans * nextneg, prevpos)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
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>0:
      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])

for i in range(k-1):
  ans *= a_abs[i][0]
  if ans>0:
    ans %= (10**9+7)
  
if ans*a_abs[k-1][0] > 0:
  ans *= a_abs[k-1][0]
  ans %= (10**9+7)
  print(ans)
  exit()

for i in range(k, n):
  if ans*a_abs[i][0]>=0:
    ans *= a_abs[i][0]
    ans %= (10**9+7)
    print(ans)
    exit()

Submission status: Wrong Answer

Solution code:
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]
  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])

for i in range(k-1):
  ans *= a_abs[i][0]
  
if ans*a_abs[k-1][0] > 0:
  ans *= a_abs[k-1][0]
  ans %= (10**9+7)
  print(ans)
  exit()

for i in range(k, n):
  if ans*a_abs[i][0]>=0:
    ans *= a_abs[i][0]
    ans %= (10**9+7)
    print(ans)
    exit()

Submission status: Wrong Answer

Solution code:
import sys

MOD = 10**9+7

N,K = map(int, input().split())
A = [[abs(int(x)),1 if int(x)<0 else 0] for x in input().split()]
A.sort(key=lambda x: x[0],reverse=True)
prod = 1
pn = 0
lastn = -1
lastp = -1


for i in range(K):
    if A[i][1] == 1: lastn = i
    else: lastp = i
    pn = (pn + A[i][1]) % 2


if pn == 0:
    if K == N and [0,0] in A:
        print(0)
        sys.exit()
    for i in range(K):
        prod = prod * A[i][0] % MOD
    print(prod)
    sys.exit()

elif pn == 1:
    if K == N:
        if [0,0] in A:
            print(0)
            sys.exit(0)
        for i in range(N):
            prod = prod * A[i][0] % MOD
            prod = prod * (-1) % MOD
        print(prod)
        sys.exit()
    indp = K
    indn = K
    while indp < N and A[indp][1] == 1:
        indp += 1
    while indn < N and A[indn][1] == 0:
        indn += 1
    if lastp == -1 and indp == N:
        for i in range(K):
            prod = prod * A[-1-i][0] % MOD
            prod = prod * (-1) % MOD
    elif indp == N:
        for i in range(K):
            if i == lastp:
                prod = prod * A[indn][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    elif lastp == -1 or indn == N:
        for i in range(K):
            if i == lastn:
                prod = prod * A[indp][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    else:
        prod = 1
        for i in range(K):
            if A[indp][0] * A[lastp][0] > A[indn][0] * A[lastn][0]:
                if i == lastn:
                    prod = prod * A[indp][0] % MOD
                else: prod = prod * A[i][0] % MOD
            else:
                if i == lastp:
                    prod = prod * A[indn][0] % MOD
                else:
                    prod = prod * A[i][0] % MOD
    print(prod)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     

def pow(x, n):
    ans = 1
    while(n > 0):
        if(bin(n & 1) == bin(1)):
            ans = ans*x
            ans %= mod
        x = x*x
        x %= mod
        n = n >> 1
    return ans

def gyaku(n):
    return pow(n, mod-2)

def main():
    N, K = LI()
    A = LI()
    sort_A = []
    for a in A:
        sort_A.append((abs(a), a))
    sort_A = sorted(sort_A, key=lambda x: x[0])[::-1]
    all_neg = True
    for a in A:
        if a >= 0:
            all_neg = False
            break
    if K % 2 == 1:
        if all_neg:
            ans = 1
            for a in A[:K]:
                ans *= a
                ans %= mod
            print(ans)
            return

    ans = 1
    plus = True
    for pair in sort_A[:K]:
        if pair[1] < 0:
            plus = not plus
        ans *= pair[0]
        ans %= mod
    if plus:
        print(ans)
        return

    pright = -inf
    nright = -inf
    pleft = -inf
    nleft = -inf

    for i in range(K, N):
        e = sort_A[i][1]
        if e >= 0:
            pright = e
            break

    for i in range(K, N):
        e = sort_A[i][1]
        if e < 0:
            nright = e
            break

    for i in range(K)[::-1]:
        e = sort_A[i][1]
        if e < 0:
            nleft = e
            break

    for i in range(K)[::-1]:
        e = sort_A[i][1]
        if e >= 0:
            pleft = e
            break

    # print('pright: {}, pleft: {}, nright: {}, nleft: {}'.format(pright, pleft, nright, nleft))
    c1, c2 = -inf, -inf
    if nright != -inf and pleft != -inf:
        c1 = ans
        c1 *= gyaku(pleft)
        c1 %= mod
        c1 *= abs(nright)
        c1 %= mod

    if nleft != -inf and pright != -inf:
        c2 = ans
        c2 *= gyaku(abs(nleft))
        c2 %= mod
        c2 *= pright
        c2 %= mod
    else:
        pass
    c = max(c1, c2)
    if c1 == -inf and c2 == -inf:
        c = ans
    print(c % mod)

main()

Submission status: Wrong Answer

Solution code:
import sys

MOD = 10**9+7

N,K = map(int, input().split())
A = [[abs(int(x)),1 if int(x)<0 else 0] for x in input().split()]
A.sort(key=lambda x: x[0],reverse=True)
prod = 1
pn = 0
lastn = -1
lastp = -1


for i in range(K):
    if A[i][1] == 1: lastn = i
    else: lastp = i
    pn = (pn + A[i][1]) % 2


if pn == 0:
    if K == N and [0,0] in A:
        print(0)
        sys.exit()
    for i in range(K):
        prod = prod * A[i][0] % MOD
    print(prod)
    sys.exit()

elif pn == 1:
    if K == N:
        if [0,0] in A:
            print(0)
            sys.exit(0)
        for i in range(N):
            prod = prod * A[i][0] % MOD
            prod = prod * (-1) % MOD
        print(prod)
        sys.exit()
    indp = K
    indn = K
    while indp < N and A[indp][1] == 1:
        indp += 1
    while indn < N and A[indn][1] == 0:
        indn += 1
    if lastp == -1 and indp == N:
        for i in range(K):
            prod = prod * A[-1-i][0] % MOD
            prod = prod * (-1) % MOD
    elif indp == N:
        for i in range(K):
            if i == lastp:
                prod = prod * A[indn][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    elif lastp == -1 or indn == N:
        for i in range(K):
            if i == lastn:
                prod = prod * A[indp][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    else:
        prod1 = 1
        prod2 = 1
        for i in range(K):
            if i == lastn:
                prod1 = prod1 * A[indp][0] #% MOD
                prod2 = prod2 * A[i][0] #% MOD
            elif i == lastp:
                prod1 = prod1 * A[i][0] #% MOD
                prod2 = prod2 * A[indn][0] #% MOD
            else:
                prod1 = prod1 * A[i][0] #% MOD
                prod2 = prod2 * A[i][0] #% MOD
        prod = max(prod1,prod2) % MOD
    print(prod)

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
z=-1
p=-1
mod=10**9+7
ans=1
for i in range(n):
    if a[i]==0:
        z=i
    elif a[i]>0:
        p=i
        break
a_abs=sorted(a,key=abs,reverse=True)
if p==-1 or n==k:
    for i in range(k):
        ans*=a[n-1-i]
        ans%=mod
    print(ans%mod)
    exit()
else:
    lp=-1
    lm=-1
    f=0
    for i in range(k):
        if a_abs[i]>=0:
            lp=i
        else:
            lm=i
            f+=1
    if f%2==0:
        for i in range(k):
          ans*=a_abs[i]
          ans%=mod
        print(ans)
    else:
        fp=-1
        fm=-1
        check_p=False
        check_m=False
        for i in range(k,n):
            if not check_p and a_abs[i]>=0:
                fp=i
                check_p=True
            elif not check_m and a_abs[i]<0:
                fm=i
                check_m=True
            if check_m and check_p:
                break
        if lp!=-1:
            if fp==-1:
              for i in range(k):
                if i==lp:
                  continue
                ans*=a_abs[i]
                ans%=mod
              ans*=a_abs[fm]
              ans%=mod
            elif fm==-1:
              for i in range(k):
                if i==lm:
                  continue
                ans*=a_abs[i]
                ans%=mod
              ans*=a_abs[fp]
              ans%=mod

            else:
                if a_abs[fm]*a_abs[lm]>=a_abs[fp]*a_abs[lp]:
                  for i in range(k):
                    if i==lp:
                      continue
                    ans*=a_abs[i]
                    ans%=mod
                  ans*=a_abs[fm]
                  ans%=mod
                else:
                  for i in range(k):
                    if i==lm:
                      continue
               	    ans*=a_abs[i]
                    ans%=mod
                  ans*=a_abs[fp]
                  ans%=mod
        else:
          for i in range(k):
            if i==lm:
              continue
            ans*=a_abs[i]
            ans%=mod
          ans*=a_abs[fp]
          ans%=mod
        print(ans%mod)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = []
c = []
for i in range(n):
  if a[i]>=0:
    b.append(a[i])
  else:
    c.append(a[i])

ans = 1
if max(0, k-len(b)) % 2 == 0:
  b = sorted(b)[::-1] + [0, 0]
  c = sorted(c) + [0]
  b_i = 0
  c_i = 0
  while b_i+c_i<k:
    if k-(b_i+c_i)>2 and c_i!=len(c)-1 and c[c_i]*c[c_i + 1]>b[b_i]:
      ans *= (c[c_i] * c[c_i+1])
      ans %= (10**9+7)
      c_i += 2
    else:
      ans *= b[b_i]
      ans %= (10**9+7)
      b_i += 1
else:
  b = sorted(b)
  c = sorted(c)[::-1]
  b_i = 0
  c_i = 0
  while b_i+c_i<k:
    if b_i==len(b):
      ans *= c[c_i]
      ans %= (10**9+7)
      c_i += 1
    elif c_i==len(c):
      ans *= b[b_i]
      b_i += 1
    else:
      if b[b_i] < c[c_i]:
        ans *= b[b_i]
        ans %= (10**9+7)
        b_i += 1
      else:
        ans *= c[c_i]
        ans %= (10**9+7)
        c_i += 1


ans %= (10**9+7)
if ans<0:
  ans -= (10**9+7)
print(abs(ans))

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
z=-1
p=-1
mod=10**9+7
ans=1
for i in range(n):
    if a[i]==0:
        z=i
    elif a[i]>0:
        p=i
        break
a_abs=sorted(a,key=abs,reverse=True)
if p==-1 or n==k:
    for i in range(k):
        ans*=a[n-1-i]%mod
    print(ans%mod)
else:
    lp=-1
    lm=-1
    f=0
    for i in range(k):
        if a_abs[i]>=0:
            lp=i
        else:
            lm=i
            f+=1
    if f%2==0:
        print(ans%mod)
    else:
        fp=-1
        fm=-1
        check_p=False
        check_m=False
        for i in range(k,n):
            if not check_p and a_abs[i]>=0:
                fp=i
                check_p=True
            elif not check_m and a_abs[i]<0:
                fm=i
                check_m=True
            if check_m and check_p:
                break
        if lp!=-1:
            if fp==-1:
              for i in range(k):
                if i==lp:
                  continue
                ans*=a_abs[i]%mod
              ans*=a_abs[fm]%mod
            elif fm==-1:
              for i in range(k):
                if i==lm:
                  continue
                ans*=a_abs[i]%mod
              ans*=a_abs[fp]%mod

            else:
                if a_abs[fm]*a_abs[lm]>=a_abs[fp]*a_abs[lp]:
                  for i in range(k):
                    if i==lp:
                      continue
                    ans*=a_abs[i]%mod
                  ans*=a_abs[fm]%mod
                else:
                  for i in range(k):
                    if i==lm:
                      continue
               	    ans*=a_abs[i]%mod
                  ans*=a_abs[fp]%mod
        else:
          for i in range(k):
            if i==lm:
              continue
            ans*=a_abs[i]%mod
          ans*=a_abs[fp]%mod
        print(ans%mod)

Submission status: Wrong Answer

Solution code:

INF = 10 ** 9 + 7
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

if K == 1:
    print(a[0])
    exit()

if K == N:
    ans = 1
    for i in a:
        ans *= i
        ans %= INF
    print(ans)
    exit()

if a[0] < 0:
    ans = 1
    if K % 2 == 1:
        for i in range(K):
            ans *= a[i]
            ans %= INF
    else:
        for i in range(K):
            ans *= a[-i - 1]
            ans %= INF
    print(ans)
    exit()

sei = []
hu = []
for i in a:
    if i >= 0:
        sei.append(i)
    else:
        hu.append(i)

seis = []
hus = []
total = []
ans = 1
if K % 2 != 0:
    ans = sei[0] % INF
    for i in range(2, len(sei), 2):
        seis.append(sei[i] * sei[i - 1])
else:
    for i in range(1, len(sei), 2):
        seis.append(sei[i] * sei[i - 1])
for i in range(1, len(hu), 2):
    hus.append(hu[i] * hu[i - 1])

total = seis + hus
total.sort(reverse=True)

for i in range(K // 2):
    ans *= total[i]
    ans %= INF

print(ans)

Submission status: Wrong Answer

Solution code:
def calc(arr):
    res = 1
    for a in arr:
        res *= a
        res %= MOD
    return res

import sys
input = sys.stdin.readline

MOD = 10 ** 9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(key=lambda x: abs(x), reverse=True)
cnt = sum(1 if a <= 0 else 0 for a in A)
if cnt == N:
    if K % 2 == 0:
        res = calc(A[:N])
    else:
        res = calc(A[N-1:N-K-1:-1])
else:
    plus = 0
    minus = 0
    cnt = 0
    tmp = [0] * K
    for i, a in enumerate(A[:K]):
        tmp[i] = a
        if a > 0:
            plus = i
        else:
            cnt += 1
            minus = i
    if cnt % 2 == 1:
        p = -1
        m = 1
        for a in A[K:]:
            if a >= 0 and p < 0:
                p = a
            if a < 0 and m > 0:
                m = a
            if p >= 0 and m < 0:
                break
        if tmp[plus] * p < tmp[minus] * m:
            tmp[plus] = m
        else:
            tmp[minus] = p
    res = calc(tmp)
print(res)

Submission status: Wrong Answer

Solution code:
n,k=map(int, input().split())
a = list(map(int, input().split()))
mod=10**9+7
if n==k:
    ans=1
    for i in range(k):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()
minus=[i for i in a if i<0]
plus=[i for i in a if i>=0]
from collections import deque
minus=deque(sorted(minus))
plus=deque(sorted(plus,reverse=True))

n_minus=len(minus)
n_plus=len(plus)
if n_minus==n:
    ans=1
    if k%2==0:
        for i in range(k):
            ans*=minus.popleft()
            ans+=mod
            ans%=mod
        print(ans)
        exit()
    else:
        for i in range(k):
            ans*=minus.pop()
            ans+=mod
            ans%=mod
        print(ans)
        exit()

ans=1
while k>1:
    if n_minus>1 and n_plus>1 and k!=3:
        if minus[0]*minus[1]>=plus[0]*plus[1]:
            n_minus-=2
            k-=2
            for _ in range(2):
                ans*=minus.popleft()
                ans%=mod
        else:
            n_plus-=2
            k-=2
            for _ in range(2):
                ans*=plus.popleft()
                ans%=mod
    elif n_minus>1 and n_plus>2 and k==3:
        ans*=max(minus[0]*minus[1]*plus[0],plus[0]*plus[1]*plus[2])
        k-=3
    elif n_minus>1:
        n_minus-=2
        k-=2
        for _ in range(2):
            ans*=minus.popleft()
            ans%=mod
    elif n_plus>1:
        n_plus-=2
        k-=2
        for _ in range(2):
            ans*=plus.popleft()
            ans%=mod

if k==1:
    if plus:
        ans*=plus.popleft()
        ans%=mod

print(ans)

Submission status: Wrong Answer

Solution code:

INF = 10 ** 9 + 7
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

if K == 1:
    print(a[0])
    exit()

if K == N:
    ans = 1
    for i in a:
        ans *= i
        ans %= INF
    print(ans)
    exit()

if a[0] < 0:
    ans = 1
    if K % 2 == 1:
        for i in range(K):
            ans *= a[i]
            ans %= INF
    else:
        for i in range(K):
            ans *= a[-i - 1]
            ans %= INF
    print(ans)
    exit()

sei = []
hu = []
for i in a:
    if i >= 0:
        sei.append(i)
    else:
        hu.append(i)

seis = []
hus = []
total = []
ans = 1
if K % 2 != 0 and len(hus) > 1:
    ans = sei[0] % INF
    for i in range(2, len(sei), 2):
        seis.append(sei[i] * sei[i - 1])
else:
    for i in range(1, len(sei), 2):
        seis.append(sei[i] * sei[i - 1])
for i in range(1, len(hu), 2):
    hus.append(hu[i] * hu[i - 1])

total = seis + hus
total.sort(reverse=True)

for i in range(K // 2):
    ans *= total[i]
    ans %= INF

print(ans)

Submission status: Wrong Answer

Solution code:
def calc(arr):
    res = 1
    for a in arr:
        res *= a
        res %= MOD
    return res

import sys
input = sys.stdin.readline

MOD = 10 ** 9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(key=lambda x: abs(x), reverse=True)
cnt = sum(1 if a <= 0 else 0 for a in A)
if cnt == N:
    if K % 2 == 0:
        res = calc(A[:N])
    else:
        res = calc(A[N-1:N-K-1:-1])
else:
    plus = MOD
    minus = -MOD
    cnt = 0
    tmp = [0] * K
    for i, a in enumerate(A[:K]):
        tmp[i] = a
        if a > 0:
            plus = i
        else:
            cnt += 1
            minus = i
    if cnt % 2 == 1:
        p = -1
        m = 1
        for a in A[K:]:
            if a >= 0 and p < 0:
                p = a
            if a < 0 and m > 0:
                m = a
            if p >= 0 and m < 0:
                break
        if plus * p < minus * m:
            tmp[plus] = m
        else:
            tmp[minus] = p
    res = calc(tmp)
print(res)