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:
import collections

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


#N=Kで選択肢ないとき
if(N == K):
    ans = 1
    for A in As:
        ans *= A
    print(ans % (10**9 + 7))
    exit()

#ansが負となる時
if(max(As) < 0 and K % 2 == 1):
    ans = 1
    for A in As[(N-K):]:
        ans *= A
    
    print(ans %(10**9 + 7))
    exit()

#2つを組み合わせたリスト作成
calc_list = []
As_que = collections.deque(As)

ans = 1
#Nが奇数のとき、最大の値を別途抽出
if(K % 2 == 1):
    ans *= As_que.pop()

while(len(As_que) > 1):
    calc_list.append(As_que.popleft() * As_que.popleft())
#    print(calc_list)

#print(calc_list)

calc_list.sort(reverse=True)
#print(calc_list)

for i in range(N // 2 - 1):
    ans *= calc_list[i]
    #print(i)

print(ans % (10**9+7))

Submission status: Wrong Answer

Solution code:
import collections

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


#N=Kで選択肢ないとき
if(N == K):
    ans = 1
    for A in As:
        ans *= A
    print(ans % (10**9 + 7))
    exit()

#ansが負となる時
if(max(As) < 0 and K % 2 == 1):
    ans = 1
    for A in As[(N-K):]:
        ans *= A
    
    print(ans %(10**9 + 7))
    exit()

#Nの値が3以下の時
if(N < 4):
    if(K == 1):
        print(max(As) % (10**9+7))
        exit()
    
    elif(N == 3 and K == 2):
        ans = max(As[0] * As[1], As[1] * As[2])
        print(ans % 10 ** 9 + 7)
        exit()

#王道ルート
As_que = collections.deque(As)
#print(As_que)

ans = 1
if(K % 2 == 1):
    ans *= As_que.pop()

left_pop = As_que.popleft() * As_que.popleft()
right_pop = As_que.pop() * As_que.pop()

#rint(left_pop,right_pop)
for _ in range((N // 2 - 1)):
    if(right_pop >= left_pop):
        ans *= right_pop
        if(len(As_que) > 1):
            right_pop = As_que.pop() * As_que.pop()
    
    else:
        ans *= left_pop
        if(len(As_que) > 1):
            left_pop = As_que.popleft() * As_que.popleft()

print(ans %(10**9 + 7))

Submission status: Wrong Answer

Solution code:
import itertools
import heapq
import sys
import functools
import operator
import numpy as np
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
comb = itertools.combinations(a,k)
comb = list(comb)
comb_list = [comb[_] for _ in range(len(comb))]  
comb_list_array = np.array(comb_list)
l_mat = np.prod(comb_list_array,axis=1)
l_max = max(l_mat)
waru = 10**9 + 7
print(l_max % waru)

Submission status: Wrong Answer

Solution code:
import itertools
import heapq
import sys
import functools
import operator
import numpy as np
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
comb = itertools.combinations(a,k)  
l = [list(_) for _ in comb]  
l_array = np.array(l)
l_mat = np.prod(l_array,axis=1)
l_max = max(l_mat)
waru = 10**9 + 7
print(l_max % waru)

Submission status: Wrong Answer

Solution code:
import itertools
import heapq
import sys
import functools
import operator
import numpy as np
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
b = np.abs(a)
b = sorted(a,reverse = True)
b_k = b[k-1] 
a_new = [a[_] for _ in range(len(a)) if np.abs(a)[_] >= b_k]
 
comb = itertools.combinations(a_new,k)  
l = [list(_) for _ in comb]  
l_array = np.array(l)
l_mat = np.prod(l_array,axis=1)
l_max = max(l_mat)
waru = 10**9 + 7
print(l_max % waru)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
inlist = list(map(int, input().split()))
inlist.sort(reverse=True)
poslist=list()
neglist=list()
pindex=0
nindex=N-1
if inlist[0]<0 and K%2==1:
  for i in range(K):
    neglist.append(inlist[i])
else:
  for i in range(K):
    if abs(inlist[pindex])>=abs(inlist[nindex]):
      poslist.append(inlist[pindex])
      pindex+=1
    else:
      neglist.append(inlist[nindex])
      nindex-=1
  if len(neglist)%2 !=0 and K < N:
    if len(poslist)>0 and len(neglist)>0:# check 
      if poslist[-1]*inlist[pindex] < neglist[-1]*inlist[nindex]:
        poslist.pop()
        neglist.append(inlist[nindex])
      else:
        neglist.pop()
        poslist.append(inlist[pindex])
    elif len(poslist)==0 and inlist[0]>=0:
      neglist.pop()
      poslist.append(inlist[pindex])
    
mult=1
poslist.extend(neglist)
for i in range(K):
  mult = mult * poslist[i]
  mult = mult%1000000007
print(mult)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

n, k = map(int, input().split())
nums = list(map(int, input().split()))

combo = combinations(nums, k)

prod_list = []
for tup in combo:
  prod = 1
  for j in tup:
    prod = prod * j
  prod_list.append(prod)
prod_list.sort(reverse=True)
print(prod_list[0] % 1000000000 + 7)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr.sort(reverse=True)
n=len(arr)
l=0
r=n-1
ans=1
if k%2==1:
    ans=arr[0]
    l=1
m=10**9+7
if ans<0:
    for i in range(k):
        ans*=arr[i]
        ans%=m
    print(ans)
    quit()
for i in range(k//2):
    po=arr[l]*arr[l+1]
    ne=arr[r]*arr[r-1]
    if po>=ne:
        l+=2
        ans*=po
        ans%=m
    else:
        r-=2
        ans*=ne
        ans%=m
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr.sort(reverse=True)
n=len(arr)
l=arr[0]
r=n-1
ans=1
m=10**9+7
if l<=0:
    for i in range(k):
        ans*=arr[i]
        ans%=m
    print(ans)
    quit()
ans=1
l=0
if k%2==1:
    ans=arr[0]
    l=1
for i in range(k//2):
    po=arr[l]*arr[l+1]
    ne=arr[r]*arr[r-1]
    if po>=ne:
        l+=2
        ans*=po
        ans%=m
    else:
        r-=2
        ans*=ne
        ans%=m
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr.sort(reverse=True)
n=len(arr)
l=arr[0]
r=n-1
ans=1
m=10**9+7
if l<=0:
    for i in range(k):
        ans*=arr[i]
        ans%=m
    print(ans)
    quit()
ans=1
l=0
if k%2==1:
    ans=arr[0]
    l=1
for i in range(k//2):
    po=arr[l]*arr[l+1]
    ne=arr[r]*arr[r-1]
    if po>ne:
        l+=2
        ans*=po
        ans%=m
    else:
        r-=2
        ans*=ne
        ans%=m
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 10**9 + 7
    p = [a for a in A if a >= 0]
    m = [a for a in A if a < 0]


    def prod(L):
        res = 1
        for l in L:
            res = res * l % mod
        return res


    if len(p) == 0 and K % 2 == 1:
        ans = prod(sorted(A, reverse=True)[:K])
    else:
        p.sort(reverse=True)
        m.sort(reverse=True)
        if K % 2 == 1:
            ans = p.pop(0)
        else:
            ans = 1
        p = [a*b for a, b in zip(p[::2], p[1::2])]
        m = [a*b for a, b in zip(m[::2], m[1::2])]
        ans *= prod(sorted(p+m, reverse=True)[:K//2])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

# import bisect
# import numpy as np
# from collections import deque
from collections import deque
# map(int, sys.stdin.read().split())
# import heapq
import bisect


# def input():
#     return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    mod = 10 ** 9 + 7

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

    elif A[-1] < 0:
        ans = 1
        for i in range(K):
            ans *= A[-(i + 1)]
            ans %= mod
        print(ans % mod)

    elif K % 2 == 0:
        ans = 1
        j = 0
        i = N - 1
        for _ in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)

    else:
        ans = A[-1]
        j = 0
        i = N - 2
        for _ in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

elif A[-1] < 0:
    ans = 1
    for i in range(K):
        ans *= A[-(i + 1)]
        ans %= mod
    print(ans % mod)

elif K % 2 == 0:
    ans = 1
    j = 0
    i = N - 1
    for _ in range(K // 2):
        if A[j] * A[j + 1] > A[i] * A[i - 1]:
            ans *= A[j] * A[j + 1]
            ans %= mod
            j += 2
        else:
            ans *= A[i] * A[i - 1]
            ans %= mod
            i -= 2
    print(ans % mod)

else:
    ans = A[-1]
    j = 0
    i = N - 2
    for _ in range(K // 2):
        if A[j] * A[j + 1] > A[i] * A[i - 1]:
            ans *= A[j] * A[j + 1]
            ans %= mod
            j += 2
        else:
            ans *= A[i] * A[i - 1]
            ans %= mod
            i -= 2
    print(ans % mod)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = sorted(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 % mod)

elif A[-1] < 0:
    ans = 1
    for i in range(K):
        ans *= A[-(i + 1)]
        ans %= mod
    print(ans % mod)

elif K % 2 == 0:
    ans = 1
    j = 0
    i = N - 1
    for _ in range(K // 2):
        if A[j] * A[j + 1] > A[i] * A[i - 1]:
            ans *= A[j] * A[j + 1]
            ans %= mod
            j += 2
        else:
            ans *= A[i] * A[i - 1]
            ans %= mod
            i -= 2
    print(ans % mod)

else:
    ans = A[-1]
    j = 0
    i = N - 2
    for _ in range(K // 2):
        if A[j] * A[j + 1] > A[i] * A[i - 1]:
            ans *= A[j] * A[j + 1]
            ans %= mod
            j += 2
        else:
            ans *= A[i] * A[i - 1]
            ans %= mod
            i -= 2
    print(ans % mod)

Submission status: Wrong Answer

Solution code:
mod = 1000000007
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
ans = 1
if K%2 == 1 and A[-1] < 0:
    for i in range(K):
        ans = ans * (A[-i-1]%mod) % mod
else:
    n = 0
    p = -1
    i = K
    while i > 0:
        if i == 1:
            ans = ans * (A[p]%mod) % mod
            i -= 1
        else:
            if A[n]*A[n+1] > A[p]*A[p-1]:
                ans = ans * (A[n]%mod) % mod
                ans = ans * (A[n+1]%mod) % mod
                n += 2
                i -= 2
            else:
                ans = ans * (A[p]%mod) % mod
                p += 1
                i -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

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

mod = 10 ** 9 + 7
num = 0
Ans = 1

if A[-1] < 0 and K % 2 == 1:
    for i in range(K):
        Ans = Ans * A[i] % mod
    print(Ans)
    sys.exit()

while num < K-1:
    non_minus = A[-1] * A[-2]
    minus = A[0] * A[1]
    if non_minus > minus:
        Ans = Ans * A.pop() % mod
        num += 1
    else:
        Ans = Ans * A.popleft() * A.popleft() % mod
        num += 2

if num == K - 1:
    Ans = Ans * A[-1] % mod

print(Ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
# import bisect
# import numpy as np
# from collections import deque
from collections import deque
# map(int, sys.stdin.read().split())
# import itertools
# import heapq
import bisect


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    A.sort()

    #    print(A)
    pp = int(bisect.bisect_left(A, 0))
    #    print(A_plus)
    #    print(A_minus)
    if N == K:
        ans = 1
        for i in A:
            ans *= i % mod
        print(ans % mod)

    elif A[-1] < 0:
        ans = 1
        for i in range(K):
            ans *= A[-(i + 1)] % mod
        print(ans % mod)

    elif K % 2 == 0:
        ans = 1
        j = 0
        i = N - 1
        for i in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)

    else:
        ans = A[-1]
        j = 0
        i = N - 2
        for i in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
""" E
    https://atcoder.jp/contests/abc173/tasks/abc173_e
"""
import sys
import math
from functools import reduce

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return reduce(lambda acc, _: acc + [readIntegerSet(m)], range(0, n), [])

def last(a, op):
    for i in range(len(a)-1, -1):
        if op(a[i]):
            return i
    return -1

def first(a, op):
    for i in range(0, len(a)):
        if op(a[i]):
            return i
    return -1

def main(N, K, A):
    A = [(abs(a), a, a > 0) for a in A]
    A.sort(reverse=True, key=lambda _t: _t[0])

    candidate = A[0:K]

    # if candidate is negative
    if len(list(filter(lambda _t: not _t[2], candidate)))%2:
        # 候補の最小負値を残りの最大正値で代える
        i10 = last(candidate, lambda _t: not _t[2])
        i11 = first(A[K:], lambda _t: _t[2])
        impact1 = - i11 / i10 if i10 != -1 and i11 != -1 else 0

        # 候補の最小正値を残りの最大負値で代える
        i20 = last(candidate, lambda _t: _t[2])
        i21 = first(A[K:], lambda _t: not _t[2])
        impact2 = - i21 / i20 if i20 != -1 and i21 != -1 else 0

        if 0 < impact1 or 0 < impact2:
            # おおきくなれる方を採用
            if impact1 > impact2:
                candidate[i10] = A[K+i11]
            else:
                candidate[i20] = A[K+i21]
        else:
            # 負値を解消するすべがないので、仕方なく最大の負値を採る.
            candidate = A[N-K:]

    result = 1
    for _t in candidate:
        result = result * _t[1]
        if result > 1000000006 or result < 0:
            result %= 1000000007
        
    return result

if __name__ == "__main__":
    _N, _K = readIntegerSet(2)
    _A = readIntegerSet(_N)

    print(main(_N, _K, _A))

Submission status: Wrong Answer

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

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

s = [];  t = [];
for a in A:
    if a < 0:
        t.append(a)
    else:
        s.append(a)

P = 10 ** 9 + 7
# 非負にできるか判定
S = len(s)
T = len(t)
ok = False
if S > 0:
    if N == K:
        ok = (T % 2 == 0)
    else:
        ok = True
else:
    ok = (K % 2 == 0)

ans = 1
if not ok:
    A.sort(key = lambda x: abs(x))  # 絶対値小→大
    for i in range(K):
        ans = ans * A[i] % P
else:   # 非負にできる
    s.sort()    # 小→大
    t.sort(reverse = True)  # 絶対値小→大
    if K % 2 == 1:
        ans *= s.pop() # 一番大きい正の数を確保

    p = []
    while len(s) >= 2:
        x = s.pop()
        x = x * s.pop() % P
        p.append(x)

    while len(t) >= 2:
        x = t.pop()
        x = x * t.pop()
        p.append(x)

    p.sort(reverse = True)
    for i in range(K // 2):
        ans = ans * p[i] % P


print(ans % P)

Submission status: Wrong Answer

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

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

s = [];  t = [];
for a in A:
    if a < 0:
        t.append(a)
    else:
        s.append(a)

P = 10 ** 9 + 7
# 非負にできるか判定
S = len(s)
T = len(t)
ok = False
if S > 0:
    if N == K:
        ok = (T % 2 == 0)
    else:
        ok = True
else:
    ok = (K % 2 == 0)

ans = 1
if not ok:
    A.sort(key = lambda x: abs(x))  # 絶対値小→大
    for i in range(K):
        ans = ans * A[i] % P
else:   # 非負にできる
    s.sort()    # 小→大
    t.sort(reverse = True)  # 絶対値小→大
    if K % 2 == 1:
        ans *= s.pop() # 一番大きい正の数を確保

    p = []
    while len(s) >= 2:
        x = s.pop()
        x = x * s.pop() % P
        p.append(x)

    while len(t) >= 2:
        x = t.pop()
        x = x * t.pop()
        p.append(x)

    p.sort(reverse = True)
    for i in range(K // 2):
        ans = ans * p[i] % P


print(ans)

Submission status: Wrong Answer

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

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
p = 10 ** 9 + 7
A.sort(key = lambda x : abs(x)) # 絶対値小→大
A_zpos = [a for a in A if a >= 0]
A_neg = [a for a in A if a < 0]

# 非負にできるか判定
nneg_en = False
if A_zpos:
    if K == N:
        if len(A_neg) % 2 == 0:
            nneg_en = True
    else:
        nneg_en = True
else:
    if K % 2 == 0:
        nneg_en = True


if nneg_en: # 非負にできる
    if K % 2 == 1:
        ans = A_zpos.pop() # 一番大きい正の数を確保
        K -= 1
    else:
        ans = 1

    A_pair = []
    while len(A_zpos) >= 2:
        A_pair.append(A_zpos.pop() * A_zpos.pop() % p)

    while len(A_neg) >= 2:
        A_pair.append(A_neg.pop() * A_neg.pop() % p)

    A_pair.sort(reverse = True)
    for i in range(K // 2):
        ans = ans * A_pair[i] % p
else:
    ans = 1
    for i in range(K):
        ans = ans * A[i] % p

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from math import log

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def modinv(x, mod):
    a, b = x, mod
    u, v = 1, 0
    while b:
        t = a // b
        a -= t * b; a, b = b, a
        u -= t * v; u, v = v, u
    return u % mod


def solve():
    mod = 10**9 + 7
    n, k = nm()
    a = nl()
    a.sort(key=abs, reverse=True)

    if max(a) <= 0:
        if k & 1:
            b = a[-k:]
        else:
            b = a[:k]
        d = 1
        for x in b:
            d = d * x % mod
        print(d)
        return

    d = 1
    for x in a[:k]:
        d = d * x % mod
    g = [x < 0 for x in a]

    if sum(g[:k]) % 2 == 0:
        print(d)
        return

    b = list(map(lambda x:-10000 if x == 0 else log(abs(x)), a))
    mpi = mmi = -1
    Mpi = Mmi = -1
    for i in range(k):
        if a[i] <= 0:
            mmi = i
        if a[i] >= 0:
            mpi = i
    for i in range(n-1, k-1, -1):
        if a[i] <= 0:
            Mmi = i
        if a[i] >= 0:
            Mpi = i
    pp = mm = - 10 ** 18
    if mmi >= 0 and Mpi >= 0:
        pp = -b[mmi] + b[Mpi]
    if mpi >= 0 and Mmi >= 0:
        mm = -b[mpi] + b[Mmi]
    if max(pp, mm) == -10**18:
        d = 1
        for x in a[-k:]:
            d = d * x % mod
        print(d)
        return
    else:
        if pp > mm:
            d = d * a[Mpi] * modinv(a[mmi], mod) % mod
        else:
            d = d * a[Mmi] * modinv(a[mpi], mod) % mod
    print(d)

    return

solve()

Submission status: Wrong Answer

Solution code:
import sys
from math import log

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def modinv(x, mod):
    a, b = x, mod
    u, v = 1, 0
    while b:
        t = a // b
        a -= t * b; a, b = b, a
        u -= t * v; u, v = v, u
    return u % mod


def solve():
    mod = 10**9 + 7
    n, k = nm()
    a = nl()
    a.sort(key=abs, reverse=True)
    d = 1
    for x in a[:k]:
        d = d * x % mod
    g = [x<0 for x in a]
    if sum(g[:k]) & 1 == 0:
        print(d)
        return
    b = list(map(lambda x:-10000 if x == 0 else log(abs(x)), a))
    mpi = mmi = -1
    Mpi = Mmi = -1
    for i in range(k):
        if a[i] <= 0:
            mmi = i
        if a[i] >= 0:
            mpi = i
    for i in range(n-1, k-1, -1):
        if a[i] <= 0:
            Mmi = i
        if a[i] >= 0:
            Mpi = i
    pp = mm = - 10 ** 18
    if mmi >= 0 and Mpi >= 0:
        pp = -b[mmi] + b[Mpi]
    if mpi >= 0 and Mmi >= 0:
        mm = -b[mpi] + b[Mmi]
    if max(pp, mm) == -10**18:
        d = 1
        for x in a[-k:]:
            d = d * x % mod
        print(d)
        return
    else:
        if pp > mm:
            d = d * a[Mpi] * modinv(a[mmi], mod) % mod
        else:
            d = d * a[Mmi] * modinv(a[mpi], mod) % mod
    print(d)

    return

solve()

Submission status: Wrong Answer

Solution code:
import sys
from math import log

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def modinv(x, mod):
    a, b = x, mod
    u, v = 1, 0
    while b:
        t = a // b
        a -= t * b; a, b = b, a
        u -= t * v; u, v = v, u
    return u % mod


def solve():
    mod = 10**9 + 7
    n, k = nm()
    a = nl()
    a.sort(key=abs, reverse=True)
    d = 1
    for x in a[:k]:
        d = d * x % mod
    g = [x<0 for x in a]
    if sum(g[:k]) & 1 == 0:
        print(d)
        return
    b = list(map(lambda x:log(abs(x) + 10**-8), a))
    mpi = mmi = -1
    Mpi = Mmi = -1
    for i in range(k):
        if a[i] <= 0:
            mmi = i
        if a[i] >= 0:
            mpi = i
    for i in range(n-1, k-1, -1):
        if a[i] <= 0:
            Mmi = i
        if a[i] >= 0:
            Mpi = i
    pp = mm = - 10 ** 18
    if mmi >= 0 and Mpi >= 0:
        pp = -b[mmi] + b[Mpi]
    if mpi >= 0 and Mmi >= 0:
        mm = -b[mpi] + b[Mmi]
    if max(pp, mm) == -10**18:
        d = 1
        for x in a[-k:]:
            d = d * x % mod
        print(d)
        return
    else:
        if pp > mm:
            d = d * a[Mpi] * modinv(a[mmi], mod) % mod
        else:
            d = d * a[Mmi] * modinv(a[mpi], mod) % mod
    print(d)

    return

solve()

Submission status: Wrong Answer

Solution code:
_MULTITEST = False
##
def solve():
    MOD = int(1e9) + 7

    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()

    neg = sum(1 for x in a if x < 0)
    pos = sum(1 for x in a if x > 0)
    zero = a.count(0)
    
    ### Set lower bound for answer
    ans_is_neg = False
    if n == k:
        if zero == 0 and neg % 2 == 1:
            ans_is_neg = True
    else:
        if pos == 0:
            if zero == 0:
                ans_is_neg = True
    
    ### Solve by window-sliding
    # set some initial vars

    #print(ans_is_neg)
    if ans_is_neg:
        prod = 1
        for i in a[n-k:n]:
            prod = (prod * i) % MOD
        print(prod)
    else:
        prod = 1
        p1 = 0; p2 = n-1;
        while k > 0:
            if k > 1 and p1 + 1 < n and 0 < p2 and a[p1] * a[p1+1] > a[p2] * a[p2-1]:
                prod = (prod * a[p1] * a[p1 + 1]) % MOD
                p1 += 2; k -= 2;
            else:
                prod = (prod * a[p2]) % MOD
                p2 -= 1; k -= 1;
        print(prod)

##
if __name__ == "__main__":
    t = (int(input()) if _MULTITEST else 1)
    for tt in range(t):
        solve()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
inlist = list(map(int, input().split()))
inlist.sort(reverse=True)
poslist=list()
neglist=list()
pindex=0
nindex=N-1
for i in range(K):
  if abs(inlist[pindex])>=abs(inlist[nindex]):
    poslist.append(inlist[pindex])
    pindex+=1
  else:
    neglist.append(inlist[nindex])
    nindex-=1
if len(neglist)%2 !=0 and pindex <= nindex:
  if len(poslist)>0 and len(neglist)>0:# check 
    if poslist[-1]*inlist[pindex] < neglist[-1]*inlist[nindex]:
      poslist.pop()
      neglist.append(inlist[nindex])
    else:
      neglist.pop()
      poslist.append(inlist[pindex])
  elif len(poslist)==0:
    neglist.pop()
    poslist.append(inlist[pindex])
  elif len(neglist)==0:
    poslist.pop()
    neglist.append(inlist[nindex])
    
mult=1
poslist.extend(neglist)
for i in range(K):
  mult = mult * poslist[i]

ans = mult
if abs(mult)>1000000000:
  ans=mult%1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, K = input_ints()
    A = input_int_list_in_line()

    if N == K:
        prod = 1
        for i in A:
            prod *= i
            prod %= 10**9+7

        print_ans(prod)
        exit()

    Apz = [a for a in A if a >= 0]
    An = [a for a in A if a < 0]

    if len(An) == N and K % 2 == 1:
        An.sort(reverse=True)
        prod = 1
        for i in An[:K]:
            prod *= i
            prod %= 10**9+7     

        print_ans(prod)
        exit()

    prod = 1

    An.sort(reverse=False)
    Apz.sort(reverse=True)

    i = 0
    j = 0

    while K > 0:
        if j not in range(len(An)):
            prod *= Apz[i]
            prod %= 10**9+7
            i += 1
            K -= 1
            continue

        if i not in range(len(Apz)):
            prod *= An[j] * An[j+1]
            prod %= 10**9+7
            j += 2
            K -= 2
            continue

        if K >= 2 and (i+1) in range(len(Apz)) and (j+1) in range(len(An)) \
                and Apz[i] * Apz[i+1] < An[j] * An[j+1]:
            prod *= An[j] * An[j+1]
            prod %= 10**9+7
            j += 2
            K -= 2
            continue
        else:
            prod *= Apz[i]
            prod %= 10**9+7
            i += 1
            K -= 1
            continue

    print_ans(prod)


def print_ans(n: int):
    print(n % (10**9 + 7))


def input_ints():
    line_list = input().split()

    if len(line_list) == 1:
        return int(line_list[0])
    else:
        return map(int, line_list)


def input_int_list_in_line():
    return list(map(int, input().split()))


def input_int_tuple_list(n: int):
    return [tuple(map(int, input().split())) for _ in range(n)]


main()

Submission status: Wrong Answer

Solution code:
def main():
    N, K = input_ints()
    A = input_int_list_in_line()

    if N == K:
        prod = 1
        for i in A:
            prod *= i

        print_ans(prod)
        exit()

    Apz = [a for a in A if a >= 0]
    An = [a for a in A if a < 0]

    if len(An) == N and K % 2 == 1:
        An.sort(reverse=True)
        prod = 1
        for i in An[:K]:
            prod *= i

        print_ans(prod)
        exit()

    prod = 1

    An.sort(reverse=False)
    Apz.sort(reverse=True)

    i = 0
    j = 0

    while K > 0:
        if j not in range(len(An)):
            prod *= Apz[i]
            prod %= 10**9+7
            i += 1
            K -= 1
            continue

        if i not in range(len(Apz)):
            prod *= An[j] * An[j+1]
            prod %= 10**9+7
            j += 2
            K -= 2
            continue

        if K >= 2 and (i+1) in range(len(Apz)) and (j+1) in range(len(An)) \
                and Apz[i] * Apz[i+1] < An[j] * An[j+1]:
            prod *= An[j] * An[j+1]
            prod %= 10**9+7
            j += 2
            K -= 2
            continue
        else:
            prod *= Apz[i]
            prod %= 10**9+7
            i += 1
            K -= 1
            continue

    print_ans(prod)


def print_ans(n: int):
    print(n % (10**9 + 7))


def input_ints():
    line_list = input().split()

    if len(line_list) == 1:
        return int(line_list[0])
    else:
        return map(int, line_list)


def input_int_list_in_line():
    return list(map(int, input().split()))


def input_int_tuple_list(n: int):
    return [tuple(map(int, input().split())) for _ in range(n)]


main()

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
mod = 10**9+7
if (max(a) < 0 and k%2) or n == k:
  ans = 1
  for i in range(n-k,n):
    ans *= a[i]
    ans %= mod
  print(ans)
  exit()
cntn = 0
cntp = n-1
if k%2:
  ans = a[-1]
  cntp -= 1
  n -= 1
else:
  ans = 1
for i in range(k//2):
  tmp = 0
  if cntn < n-1 and a[cntn+1] < 0:
    tmp = max(tmp,a[cntn]*a[cntn+1])
    cntn += 2
  if cntp > 0 and a[cntp-1] >= 0:
    tmp = max(tmp,a[cntp-1]*a[cntp])
    cntp -= 2
  ans *= tmp
  ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
mod = 10**9+7
if (max(a) < 0 and k%2) or n == k:
  ans = 1
  for i in range(n-k,n):
    ans *= a[i]
    ans %= mod
  print(ans)
  exit()
cntn = 0
cntp = n-1
if k%2:
  ans = a[-1]
  cntp -= 1
  n -= 1
else:
  ans = 1
for i in range(k//2):
  tmp = 0
  if cntn < n-1 and a[cntn+1] < 0:
    tmp = max(tmp,a[cntn]*a[cntn+1])
    cntn += 2
  if cntp > 0 and a[cntp-1] >= 0:
    tmp = max(tmp,a[cntp-1]*a[cntp])
  ans *= tmp
  ans %= mod
print(ans)