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 = list(map(int, input().split()))

    plus = [A[i] for i in range(N) if A[i] >= 0]
    minus = [A[i] for i in range(N) if A[i] < 0]

    ans = 1

    id = 0
    id2 = 0
    P = len(plus)
    M = len(minus)
    plus.sort(reverse=True)

    mod = 10**9 + 7

    if P == 0:
        if K % 2 == 0:
            minus.sort()
            for i in range(K):
                ans *= minus[i]
                ans %= mod
        else:
            minus.sort(reverse=True)
            for i in range(K):
                ans *= minus[i]
                ans %= mod

    elif M == 0:
        for i in range(K):
            ans *= plus[i]
            ans %= mod
    elif K == 1:
        ans = plus[0]

    else:

        p = P // 2
        m = M // 2
        if K > (p+m)*2 and (K % 2 == 0 or (K % 2 == 1 and P % 2 == 0)):  # 絶対値が小さい方から貪欲
            A.sort(key=lambda x: abs(x))
            for i in range(K):
                ans *= A[i]
                ans %= mod

        else:  # 絶対値が大きい方から貪欲

            minus.sort()
            pp = [plus[i*2]*plus[i*2+1] for i in range(P // 2)]
            mm = [minus[i*2] * minus[i*2+1] for i in range(M//2)]

            id = 0
            id2 = 0

            pp.sort(reverse=True)
            mm.sort(reverse=True)
            pp.append(1)
            mm.append(1)
            for i in range((K // 2) - 1):
                if id == p - 1:
                    ans *= mm[id2]
                    id2 += 1
                elif id2 == m:
                    ans *= pp[id]
                    id += 1
                elif pp[id] >= mm[id2]:
                    ans *= pp[id]
                    id += 1
                else:
                    ans *= mm[id2]
                    id2 += 1

                ans %= mod

            if K % 2 == 1:
                if id >= p-1:
                    ans *= mm[id2]
                    ans *= plus[id*2]
                else:
                    ans *= pp[id]
                    id += 1
                    ans *= plus[id*2]
            else:
                if id >= p:
                    ans *= mm[id2]
                elif id2 >= m:
                    ans *= pp[id]
                elif pp[id] >= mm[id2]:
                    ans *= pp[id]
                else:
                    ans *= mm[id2]

    print(ans % mod)


main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations

def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    ans = -1
    limit = 10**9+7
    for i in combinations(a, k):
        c = 1
        for j in i:
            c *= j
            if c > 0:
                c %= limit
        ans = max(ans, c)
    print(ans % limit)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

l_pos=[]
l_neg=[]
for i in range(n):
  if l[i]<0:
    l_neg.append(l[i])
  else:
    l_pos.append(l[i])

l_neg.sort()
l_pos.sort()
a=len(l_neg)
b=len(l_pos)
a=a-1
b=b-1

if len(l_neg)==0:
  ans=1
  for i in range(k):
    ans*=l_pos[-1-i]
    ans=ans%mod

elif len(l_pos)==0:
  ans=1
  for j in range(k):
    ans*=l_neg[i]
    ans=ans%mod

elif k==n:
  ans=1
  for i in range(n):
    ans*=l[i]
    ans=ans%mod

else:
  ans=1
  cntodd=0
  while a>0 and b>0:
    if l_pos[b]>=abs(l_neg[a]):
      ans*=l_pos[b]
      ans=ans%mod
      b-=1
    
    elif l_pos[b]<abs(l_neg[a]):
      ans*=l_pos[b]
      ans=ans%mod
      a-=1
      cntodd+=1
    k-=1
    if k==1:
      break

  if cntodd%2==0 and k==1:
    ans*=l_pos[b]
    k-=1
  elif cntodd%2!=0 and k==1:
    if a+1<len(l_neg):
      a+=1
    ans=ans//l_neg[a]
    ans*=l_pos[b]
    k-=1
  
 
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, K = mi()
A = li()

d = defaultdict(int)
mod = 10**9+7
K_ = K

if N == K:
    ans = 1
    for num in A:
        ans *= num
        ans %= mod
    print(ans)
    exit()

for i in range(N):
    d[A[i]] += 1
    if A[i] < 0:
        A[i] *= -1

A = sorted(A, reverse=True)
l = []

for num in A:
    if d[-num] > 0:
        l.append(1)
        d[-num] -= 1
    else:
        l.append(0)
        d[num] -= 1

#print(l)
#print(sum(l[:K]))

if not sum(l[:K])%2:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= mod
    print(ans)

else:
    flag = False
    ans = 1
    for i in range(K, N):
        if not l[i]:
            flag = True
            ans *= A[i]
            ans %= mod
            break
    
    if flag:
        for i in reversed(range(K)):
            if flag and l[i]:
                flag = 0
                continue
            ans *= A[i]
            ans %= mod
        print(ans)
    
    else:
        if K%2:
            for i in range(N-K, N):
                ans *= A[i]
                ans %= mod
            ans *= -1
            ans %= mod
            print(ans)

        else:
            for i in range(N):
                if l[i]:
                    K -= 1
                    ans *= A[i]
                    ans %= mod
                if K == 0:
                    break

            else:
    
                ans = 1
                flag = True
                for i in reversed(range(K_)):
                    if flag and not l[i]:
                        flag = 0
                        continue
                    ans *= A[i]
                    ans %= mod
                ans *= A[K_]
                ans %= mod
                print(ans)
                exit()

            print(ans)

Submission status: Wrong Answer

Solution code:
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
a = sorted(a)
mod = 1000000007

if n == k:
    prod = 1
    for b in a:
        prod *= b
        prod %= mod
    print(prod)
    exit()

# negative prod
if k & 1 and a[-1] < 0:
    prod = 1
    for i in range(k):
        prod *= a[-1 - i]
        prod %= mod
    print(prod)
    exit()

A = []
for b in a:
    if b < 0:
        A.append((-b, True))
    else:
        A.append((b, False))
A = sorted(A)[::-1]

ans = 1
is_neg = False
last_neg = 1
last_nneg = -1

for i in range(k + 1):
    (b, neg) = A[i]
    if neg:
        ans *= -b
    else:
        ans *= b
    ans %= mod
    is_neg ^= neg
    if b == 0:
        print(0)
        exit()
    if i == k - 1:
        if not is_neg:
            print(ans)
            exit()
    if i <= k - 1:
        if neg:
            last_neg = -b
        else:
            last_nneg = b
    if i == k:
        if is_neg:
            assert last_neg != 1
            ans *= pow(last_neg, mod - 2, mod)
        else:
            if last_nneg != -1:
                ans *= pow(last_nneg, mod - 2, mod)
            else:
                ans *= pow(last_neg, mod - 2, mod)
                ans *= pow(-b, mod - 2, mod)
                for j in range(k + 1, n):
                    if not A[j][1]:
                        ans *= A[j][0]
                        break
        ans %= mod
        print(ans)
        exit()

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 - A.count(0) < K:
    print(0)
    exit(0)

plus = []
minus = []
for a in A:
    if a > 0:
        plus.append(a)
    elif a < 0:
        minus.append(a)
    else:
        plus.append(a)
        minus.append(a)


ans = 1
if K % 2 == 1 and len(plus) == 0:
    minus.sort(reverse=True)
    for i in range(K):
        ans *= minus[i]
        ans %= MOD
    print(ans)
    exit(0)
plus.append(0)
minus.append(0)
plus.append(0)
minus.append(0)

plus.sort(reverse=True)
minus.sort()

i = 0
j = 0

if K % 2 == 1 and len(plus) > 0:
    ans = plus[0]
    K -= 1
    plus = plus[1:]

for _ in range(K//2):
    if i+1 >= len(plus):
        ans *= (minus[j] * minus[j+1])
        ans %= MOD
        j += 2
        continue
    elif j+1 >= len(minus):
        ans *= (plus[i] * plus[i+1])
        ans %= MOD
        i += 2
        continue

    a = plus[i] * plus[i+1]
    b = minus[j] * minus[j+1]
    if a > b:
        ans *= a
        i += 2
    else:
        ans *= b
        j += 2
    ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7

n, k = [int(_) for _ in input().split()]

a = [int(_) for _ in input().split()]

m = list(filter(lambda x: x < 0, a))
p = list(filter(lambda x: x > 0, a))

m.sort()
p.sort(reverse=True)


if len(p)+len(m) < k:
    print(0)
    exit()

if len(p) == 0 and k % 2 == 1:
    ans = 1
    for i in range(k):
        ans = (ans*m[-i-1]) % MOD
    if 0 in a:
        ans *= 0
    print(ans)
    exit()


i, j = 0, 0
if k % 2 == 1:
    d = p.pop(-1)
m.append(0)
m.append(0)
p.append(0)
p.append(0)
# print(p, m)
ans = 1
for c in range(k//2):
    # print(i, j)
    if m[i]*m[i+1] >= p[j]*p[j+1]:
        ans = (ans*m[i]*m[i+1]) % MOD
        i += 2
    else:
        ans = (ans*p[j]*p[j+1]) % MOD
        j += 2

if k % 2 == 1:
    ans = (ans*max(p[j], d)) % MOD


if ans > MOD:
    ans -= MOD
if ans < 0:
    1/0
print(ans)

Submission status: Wrong Answer

Solution code:
# N, K = 10, 10
# A = [1000000000, 100000000, 10000000, 1000000, 100000, 10000, 1000, 100, 10, 1]
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

p = []
m = []

a = [[0, 0] for i in range(N)]
for i in range(N):
    if A[i] > 0:
        p.append(A[i])
        a[i] = [A[i], 1]
    elif A[i] < 0:
        m.append(-1 * A[i])
        a[i] = [-1 * A[i], -1]
p.sort(reverse=True)
m.sort(reverse=True)
a.sort(reverse=True, key=lambda x:x[0])
if len(p) + len(m) < K:
    ans = 0
else:
    b = a[0:K]
    n_m = 0
    for i in range(K):
        if b[i][1] == -1:
            n_m += 1
    if n_m % 2 == 0:
        mod = 10**9 + 7
        ans = 1
        for i in range(K):
            ans = ans * a[i][0] % mod
    else:
        for i in range(K):
            if b[i][1] == -1:
                idx = i
        n_p = K - (n_m - 1)
        if n_p <= len(p):
            ans = 1
            mod = 10**9 + 7
            for j in range(n_p):
                ans = ans * p[j] % mod
            for j in range(n_m - 1):
                ans = ans * m[j] % mod
        else:
            ans = 1
            mod = 10 ** 9 + 7
            for i in range(K):
                ans = ans * A[i] % mod

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True, 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(k):
        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, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n, k = inpl()
a = inpl()
data = [[abs(i), i < 0] for i in a]
all_minus = 0
for t in data:
    if t[1]:
        all_minus += 1
if all_minus == n:
    ans = 1
    data.sort()
    for i in range(k):
        ans = ans * data[i][0] % mod
    ans*=(-1)%mod
    print(ans % mod)
    exit()
data.sort(reverse=True)
last_minus = 0
last_plus = 0
ans = 1
minus_amount = 0
for i in range(k):
    elem, sign = data[i][0], data[i][1]
    if elem == 0:
        print(0)
        exit()
    ans = ans * elem % mod
    minus_amount += sign
    if sign:
        last_minus = elem
    else:
        last_plus = elem
if minus_amount % 2 == 0:
    print(ans%mod)
    exit()
if n==k:
    print(-ans % mod)
    exit()
tmp_plus = 0
tmp_minus = 0
for i in range(k, n):
    elem, sign = data[i][0], data[i][1]
    if last_plus and sign and not tmp_minus:
        tmp_minus = elem
    elif last_minus and not sign and not tmp_plus:
        tmp_plus = elem
if tmp_plus == 0 and tmp_minus == 0:
    ans = 0
elif last_plus == 0:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
elif last_minus == 0:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
elif tmp_plus * last_plus > tmp_minus * last_minus:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
else:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7

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

A_pos = [a for a in As if a >= 0]
A_pos.sort()
A_pos.reverse()

A_neg = [a for a in As if a < 0]
A_neg.sort()

ans = 1

pos_used = 0
neg_used = 0

pos_total = len(A_pos)
neg_total = len(A_neg)

# 答えが負になるかチェック
if pos_total < K and (K-pos_total)%2 == 1:
    # 小さい方から取る
    A_pos.reverse()
    A_neg.reverse()


k = K
# 二つずつペアで見てゆく
while (pos_used+neg_used) < K:
    # Kが1
    if K == 1:
        if N == 1:
            if pos_total == 1:
                ans = (ans * A_pos[0]) % MOD
            else:
                ans = (ans * A_neg[0]) % MOD
        else:
            if pos_total > 0:
                ans = (ans * A_pos[0]) % MOD
            else:
                ans = (ans * A_neg[0]) % MOD
        break

    # のこり2以上のとき
    if K-(pos_used+neg_used) >= 2:
        # 正の数，負の数とも二つ以上残っているとき
        if (pos_total-pos_used)>=2 and (neg_total-neg_used)>=2:
            if A_neg[neg_used]*A_neg[neg_used+1] >= A_pos[pos_used]*A_pos[pos_used+1]:
                ans = (ans * A_neg[neg_used] * A_neg[neg_used+1]) % MOD
                neg_used += 2
            else:
                ans = (ans * A_pos[pos_used] * A_pos[pos_used+1]) % MOD
                pos_used += 2

        # もう正の数しか残っていない時
        elif neg_total == neg_used:
            ans = (ans * A_pos[pos_used] * A_pos[pos_used+1]) % MOD
            pos_used += 2

        # もう負の数しか残っていない時
        elif pos_total == pos_used:
            ans = (ans * A_neg[neg_used] * A_neg[neg_used+1]) % MOD
            neg_used += 2

    # のこり一つのとき
    else:
        # もう正の数しか残っていない時
        if neg_total == neg_used:
            ans = (ans * A_pos[pos_used]) % MOD
            pos_used += 1

        # もう負の数しか残っていない時
        else:
            ans = (ans * A_neg[neg_used]) % MOD
            neg_used += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y/2)**2 % mod
    else            : return power(x, y/2)**2 * x % mod

def div(a, b):
    return mul(a, power(b, mod-2))

m = 10 ** 9 + 7

A,B = map(int,input().split())
L = list(map(int, input().split()))

l = []

for i in range(A):
  l.append(abs(L[i]))
  
S = sorted(L,reverse=True)

v = np.prod(S[:B])

print(v%m)

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
from collections import defaultdict, deque
from decimal import *
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

mod=1000000007
n,k=rm()
a=rl()
pos=[]
neg=[]
for i in a:
    if i>=0:
        pos.append(i)
    else:
        neg.append(i)
pos.sort(reverse=True)
neg.sort(reverse=True)
for i in range(1,len(pos)):
    pos[i]=(pos[i-1]*pos[i])%mod
for j in range(1,len(neg)):
    neg[j]=(neg[j-1]*neg[j])%mod

if len(pos)==0:
    print(neg[k-1]%mod)
elif len(neg)==0:
    print(pos[k-1]%mod)
else:
    maxi=-math.inf
    for i in range(0,k+1,2):
        if i==0:
            if k-i<=len(pos):
                maxi=max(maxi,pos[k-i-1]%mod)
        elif k-i==0:
            if i<=len(neg):
                maxi=max(maxi,neg[i-1]%mod)
        elif i<=len(neg) and k-i<=len(pos):
            maxi=max(maxi,(neg[i-1]*pos[k-i-1])%mod)
    print(maxi)

Submission status: Wrong Answer

Solution code:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s); sys.stdout.write('\n')
def wi(n): sys.stdout.write(str(n)); sys.stdout.write('\n')
def wia(a, sep=' '): sys.stdout.write(sep.join([str(x) for x in a])); sys.stdout.write('\n')


MOD = 10**9 + 7


def solve(n, k, a):
    a = sorted(a, reverse=True, key=lambda x: (abs(x), 1 if x >= 0 else -1))
    sign = 1
    for i in range(k):
        if a[i] < 0:
            sign = -sign
        if a[i] == 0:
            sign = 0

    if sign == 0:
        return 0

    if sign == 1:
        ans = 1
        for i in range(k):
            ans = (ans * abs(a[i])) % MOD
        return ans

    if sign == -1:
        cc = []

        more_neg = -1
        for i in range(k, n):
            if a[i] < 0:
                more_neg = i
                break

        more_pos = -1
        for i in range(k, n):
            if a[i] > 0:
                more_pos = i
                break

        taken_neg = -1
        for i in range(k-1, -1, -1):
            if a[i] < 0:
                taken_neg = i
                break

        taken_pos = -1
        for i in range(k - 1, -1, -1):
            if a[i] > 0:
                taken_pos = i
                break

        if more_neg >= 0 and taken_pos >= 0:
            cc.append((taken_pos, more_neg))
        if more_pos >= 0 and taken_neg >= 0:
            cc.append((taken_neg, more_pos))
        # cc = sorted(cc, key=lambda x: abs(a[x[1]] / a[x[0]]), reverse=True)

        if len(cc) > 0:
            ans = 1
            for i in range(k):
                if i != cc[0][0]:
                    ans = (ans * a[i]) % MOD
            ans = (ans * a[cc[0][1]]) % MOD
            return ans
        else:
            # product is negative, taking smallest
            ans = 1
            for i in range(k):
                ans = (ans * a[n-i-1]) % MOD
            return ans


import random


def gen():
    for n in range(2, 100):
        for k in range(2, n):
            for t in range(100):
                a = [random.randrange(100) - 100 for _ in range(n)]
                solve(n, k, a)
        wi(n)


def main():
    # gen()
    # return
    n, k = ria()
    a = ria()
    wi(solve(n, k, a))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

mod = 10**9 + 7

minus = []
plus = []
zero = []
new_ls = []
for i in ls:
    if i > 0:
        plus.append(i)
        new_ls.append(i)
    elif i < 0:
        minus.append(i)
        new_ls.append(-i)
    else:
        zero.append(i)
        new_ls.append(i)

ans = 1
new_ls.sort()
minus.sort()
plus.sort()
if (len(plus) == 0 and k%2 == 1) or (len(minus)%2 == 1 and k == n):
    if len(zero) != 0:
        ans = 0
    else:
        for i in range(k):
            ans *= new_ls[i]
            ans %= mod
        ans = mod - ans
elif k%2 == 0:
    m_ind = 0
    p_ind = 0
    for i in range(k//2):
        if m_ind+1 < len(minus) and p_ind+1 < len(plus):
            if minus[m_ind] * minus[m_ind+1] > plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]:
                ans *= minus[m_ind] * minus[m_ind+1]
                ans %= mod
                m_ind += 2
            else:
                ans *= plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]
                ans %= mod
                p_ind += 2
        elif m_ind+1 < len(minus):
            ans *= minus[m_ind] * minus[m_ind+1]
            ans %= mod
            m_ind += 2
        elif p_ind+1 < len(plus):
            ans *= plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]
            ans %= mod
            p_ind += 2
        #else:
else:
    m_ind = 0
    p_ind = 1
    ans *= plus[len(plus)-1]
    for i in range(k//2):
        if m_ind+1 < len(minus) and p_ind+1 < len(plus):
            if minus[m_ind] * minus[m_ind+1] > plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]:
                ans *= minus[m_ind] * minus[m_ind+1]
                ans %= mod
                m_ind += 2
            else:
                ans *= plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]
                ans %= mod
                p_ind += 2
        elif m_ind+1 < len(minus):
            ans *= minus[m_ind] * minus[m_ind+1]
            ans %= mod
            m_ind += 2
        elif p_ind+1 < len(plus):
            ans *= plus[len(plus)-p_ind-1]*plus[len(plus)-p_ind-2]
            ans %= mod
            p_ind += 2
        #else:
    ans %= mod

print(ans)

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
                print(ans)
            seisei-=2
            if seisei<0:
                break

print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

mod = 10 ** 9 + 7

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

if N == K:
    ans = 1
    for i in range(N):
        ans *= A[i]
        ans %= mod
    print(ans)
    sys.exit()

A = np.array(A)

plus = A[A>0]
minus = A[A<0]
zero = A[A==0]

if len(zero) > N - K:
    print(0)
    sys.exit()

if len(minus) == N:
    if K % 2 == 0:
        minus = np.sort(minus)
    else:
        minus = np.sort(minus)[::-1]
    ans = 1
    for i in range(K):
        ans *= minus[i]
        ans %= mod
    print(ans)
    sys.exit()

# plus = np.sort(plus)[::-1]
# minus *= -1
# minus = np.sort(minus)[::-1]

# if K % 2 == 1:
#     ans = plus[0]
#     K -= 1
#     p = (len(plus)-1) // 2
#     m = len(minus) // 2
    
#     n_p = [plus[2*i+1] * plus[2*i+2] for i in range(p)]
#     n_m = [minus[2*i] * minus[2*i+1] for i in range(m)]
# else:
#     ans = 1
#     p = len(plus) // 2
#     m = len(minus) // 2
    
#     n_p = [plus[2*i] * plus[2*i+1] for i in range(p)]
#     n_m = [minus[2*i] * minus[2*i+1] for i in range(m)]

# K //= 2

# p_index = 0
# m_index = 0
# for i in range(K):
#     if p_index == len(n_p):
#         ans *= n_m[m_index]
#         ans %= mod
#         m_index += 1
#     elif m_index == len(n_m):
#         ans *= n_p[p_index]
#         ans %= mod
#         p_index += 1
#     else:
#         if n_p[p_index] > n_m[m_index]:
#             ans *= n_p[p_index]
#             ans %= mod
#             p_index += 1
#         else:
#             ans *= n_m[m_index]
#             ans %= mod
#             m_index += 1
print(0)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
ans = 1
mod = 10**9+7
tmp_K = K
if min(A) > 0:
    A.sort(reverse=True)
    for i in A[:K]:
        ans = (ans*i)%mod
 
elif max(A) < 0:
 
    if K%2 == 0:
        A.sort()
        for i in A[:K]:
            ans = (ans*i)%mod
    else:
        A.sort(reverse=True)
        for i in A[:K]:
            ans = (ans*i)%mod

else:
    z = []
    p = []
    m = []
    for i in A:
        if i == 0:
            z.append([i,1])
        elif i > 0:
            p.append([i,1])
        else:
            m.append([i,1])
    m.sort()
    mm = []
    for i in range(0,len(m),2):
        try:
            mm.append([m[i][0]*m[i+1][0],2])
        except:
            pass
    
    tot = p+z+mm+m
 
    tot.sort(reverse=True)
    flag_m = False
    for v,cost in tot:
        if K <= 0:
            break
        if v < 0:
            flag_m = True
        if K - cost >= 0:
            ans = (ans*v)%mod
            K -= cost
        else:
            continue
    
    if flag_m and len(z) == 0:##値が負になる．絶対値の最小化を行う．
        b = sorted(list([[abs(i),i] for i in A]))
        bb = list(i for _,i in b)
        res = 1
        for i in range(tmp_K):
            res = (res*bb[i])%mod
        print(res%mod)
        exit()
print(ans%mod)

Submission status: Wrong Answer

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


N,K =(list(map(int,input().split())))
A = sorted((list(map(int,input().split()))),reverse = 1)

B = A[:K]
ans = 1
m = 1000000007
for i in range(len(B)):
    ans *= B[i]
print(ans%m)

Submission status: Wrong Answer

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

m=[]
p=[]
z=0
for i in range(n):
    if a[i]<0:
        m.append(-a[i])
    elif a[i]>0:
        p.append(a[i])
    else:
        z+=1
m=sorted(m,reverse=True)
p=sorted(p,reverse=True)

if k>len(m)+len(p):
    print(0)
    sys.exit()

if len(p)==0:
    ans=1
    if k%2==0:
        for i in range(k):
            ans*=m[i]
            ans%=mod
        print(ans)
        sys.exit()
    else:
        for i in range(k):
            if i==k-1:
                ans*=-m[-i-1]
                ans%=mod
            else:
                ans*=m[-i-1]
                ans%=mod
        print(ans)
        sys.exit()

if len(m)==0:
    ans=1
    for i in range(k):
        ans*=p[i]
        ans%=mod
    print(ans)
    sys.exit()



q=[]
if len(m)%2==0:
    for i in range(len(m)//2):
        q.append(m[2*i]*m[2*i+1])
else:
    for i in range(len(m)//2):
        q.append(m[2*i]*m[2*i+1])
    q.append(m[-1])

pp=0
qq=0
c=0
ans=1
if k%2==1:
    ans*=p[pp]
    pp+=1
    c+=1
while c<k:
    if pp<len(p)-1 and qq<len(q):
        if p[pp]*p[pp+1]>q[qq]:
            ans*=p[pp]*p[pp+1]
            pp+=2
        else:
            ans*=q[qq]
            qq+=1
        ans%=mod
        c+=2

    elif pp>=len(p)-1:
        ans*=q[qq]
        ans%=mod
    else:
        ans*=p[pp]*p[pp+1]
        ans%=mod

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = pow(10,9)+7

A.sort(reverse=True)

deque = deque()
for a in A:
    deque.append(a)

ans = 1
cnt = 0
if K%2 == 1:
    ans *= deque.popleft()
    cnt += 1
    
if ans <= 0:
    for i in range(K-1):
        ans *= deque.popleft()
        ans %= mod
else:
    while cnt < K:
        x1 = deque.popleft()
        x2 = deque.popleft()
        if deque:
            y1 = deque.pop()
        else:
            pop = 1
        if deque:
            y2 = deque.pop()
        else:
            pop = -pow(10,9)-1
        if x1*x2 < y1*y2:
            ans *= y1*y2
            ans %= mod
            deque.appendleft(x2)
            deque.appendleft(x1)
            cnt += 2
        else:
            ans *= x1*x2
            ans %= mod
            deque.append(y2)
            deque.append(y1)
            cnt += 2
            
print(ans)