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: Runtime Error

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10 ** 9+ 7
    ans = 1

    def answer(a):
        ans =1
        for i in range(k):
            ans *= a[i]
            ans %= mod
        print(ans)

    if n == k:
        answer(a)
        return

    if all([True if x < 0 else False for x in a]):
        a.sort(reverse=True)
        answer(a)
        return

    a.sort(reverse=True, key=lambda x: abs(x))
    flag = 1
    for i in range(k):
        if a[i] < 0:
            flag ^= 1
    if flag or 0 in a[:k]:
        answer(a)
        return
    
    x1, x2, y1, y2 = k-1, k-1, k, k
    while a[x1] >= 0 and x1 >= 0:
        x1 -= 1
    while a[x2] < 0 and x2 >= 0:
        x2 -= 1
    while a[y1] < 0 and y1 < n:
        y1 += 1
    while a[y2] >= 0 and y2 < n:
        y2 += 1

    if x1 == -1 or y1 == n:
        a[x2], a[y2] = a[y2], a[x2]
    
    elif x2 == -1 or y2 == n:
        a[x1], a[y1] = a[y1], a[x1]
    else:
        if a[x1]*a[y2] > a[x2]*a[y1]:
            a[x2], a[y2] = a[y2], a[x2]
        else:
            a[x1], a[y1] = a[y1], a[x1]
    answer(a)
    
    

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10 ** 9+ 7
    ans = 1

    def answer(a):
        ans =1
        for i in range(k):
            ans *= a[i]
            ans %= mod
        print(ans)

    if n == k:
        answer(a)
        return

    if all([True if x < 0 else False for x in a]):
        a.sort(reverse=True)
        answer(a)
        return

    a.sort(reverse=True, key=lambda x: abs(x))
    flag = 1
    for i in range(k):
        if a[i] < 0:
            flag ^= 1
    if flag or a[k-1] == 0:
        answer(a)
        return
    
    x1, x2, y1, y2 = k-1, k-1, k, k
    while a[x1]*a[x2] > 0 and x2 >= 0:
        x2 -= 1

    while a[x1]*a[y1] > 0 and y1 < n:
        y1 += 1

    if x2 == -1:
        a[x1], a[y1] = a[y1], a[x1]
    else:
        while a[x2]*a[y2] > 0 and y2 < n:
            y2 += 1
        if y1 == n:
            a[x2], a[y2] = a[y2], a[x2]
        else:
            if a[x1]*a[y2] < a[x2]*a[y1]:
                a[x1], a[y1] = a[y1], a[x1]
            else:
                a[x2], a[y2] = a[y2], a[x2]
    answer(a)
 

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

A_neg = []
A_pos = []

for i in range(N):
  if A[i] <= 0:
    A_neg.append(-A[i])
  else:
    A_pos.append(A[i])

A_neg.sort(reverse=True)
A_pos.sort(reverse=True)

ans = 1

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

elif K%2==1 and len(A_pos)==0:
  for i in range(1, K+1):
    ans *= ((-A_neg[-i])%1000000007)
    ans %= 1000000007
  print(ans)

else:
  if K%2==1:
    ans *= A_pos.pop(0)
    K -= 1
  buf = []
  if len(len(A_pos)>=2):
    for i in range(len(A_pos)//2):
      buf.append(A_pos[2*i]*A_pos[2*i+1])
  if len(len(A_pos)>=2):
    for i in range(len(A_neg)//2):
      buf.append(A_neg[2*i]*A_neg[2*i+1])
  buf.sort(reverse=True)
  for i in range(K//2):
    ans *= (buf[i]%1000000007)
    ans %= 1000000007
  print(ans)

Submission status: Runtime Error

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

# 正の数と負の数でリストを分ける
A_neg = []
A_pos = []
for i in range(N):
    if A[i] <= 0:
        A_neg.append(-A[i])
    else:
        A_pos.append(A[i])

# 絶対値が大きい順にソート
A_neg.sort(reverse=True)
A_pos.sort(reverse=True)

# 掛け算なので初期化を1で行う
ans = 1

# Kが奇数かつすべての数が負の場合
# 答えの候補がすべて負なので絶対値が小さい順にかける
if K % 2 == 1 and len(A_pos) == 0:
    for i in range(1, K + 1):
        ans *= ((-A_neg[-i]) % 1000000007)
        ans %= 1000000007
    print(-ans)

# その他の場合
else:
    #
    if K % 2 == 1:
        ans *= A_pos.pop(0)
        K -= 1
    # 数を2つセットにして符号を正に丸める
    buf = []
    for i in range(len(A_pos) // 2):
        buf.append(A_pos[2 * i] * A_pos[2 * i + 1])
    for i in range(len(A_neg) // 2):
        buf.append(A_neg[2 * i] * A_neg[2 * i + 1])
    # bufを絶対値の大きい順に並べ、前からK//2個をansに*
    buf.sort(reverse=True)
    for i in range(K // 2):
        ans *= (buf[i] % 1000000007)
        ans %= 1000000007
    print(ans)

Submission status: Runtime Error

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

# 正の数と負の数でリストを分ける
A_neg = []
A_pos = []
for i in range(N):
    if A[i] <= 0:
        A_neg.append(-A[i])
    else:
        A_pos.append(A[i])

# 絶対値が大きい順にソート
A_neg.sort(reverse=True)
A_pos.sort(reverse=True)

# 掛け算なので初期化を1で行う
ans = 1

# Kが奇数かつすべての数が負の場合
# 答えの候補がすべて負なので絶対値が小さい順にかける
if K % 2 == 1 and len(A_pos) == 0:
    for i in range(1, K + 1):
        ans *= (-A_neg[-i]) % (10 ** 9 + 7)
    print(-ans)

# その他の場合
else:
    #
    if K % 2 == 1:
        ans *= A_pos.pop(0)
        K -= 1
    # 数を2つセットにして符号を正に丸める
    buf = []
    for i in range(len(A_pos) // 2):
        buf.append(A_pos[2 * i] + A_pos[2 * i + 1])
    for i in range(len(A_neg) // 2):
        buf.append(A_neg[2 * i] + A_neg[2 * i + 1])
    # bufを絶対値の大きい順に並べ、前からK//2個をansに*
    buf.sort(reverse=True)
    for i in range(K // 2):
        ans *= buf[i] % (10 ** 9 + 7)
        ans %= 10 ** 9 + 7
    print(ans)

Submission status: Runtime Error

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

A_neg = []
A_pos = []

for i in range(N):
  if A[i] <= 0:
    A_neg.append(-A[i])
  else:
    A_pos.append(A[i])

A_neg.sort(reverse=True)
A_pos.sort(reverse=True)

ans = 1

if K%2==1 and len(A_pos)==0:
  for i in range(1, K+1):
    ans *= ((-A_neg[-i])%1000000007)
    ans %= 1000000007
  print(ans)

else:
  if K%2==1:
    ans *= A_pos.pop(0)
    K -= 1
  buf = []
  for i in range(len(A_pos)//2):
    buf.append(A_pos[2*i]*A_pos[2*i+1])
  for i in range(len(A_neg)//2):
    buf.append(A_neg[2*i]*A_neg[2*i+1])
  buf.sort(reverse=True)
  for i in range(K//2):
    ans *= (buf[i]%1000000007)
    ans %= 1000000007
  print(ans)

Submission status: Runtime Error

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

A_neg = []
A_pos = []

for i in range(N):
  if A[i] <= 0:
    A_neg.append(-A[i])
  else:
    A_pos.append(A[i])

A_neg.sort(reverse=True)
A_pos.sort(reverse=True)

ans = 1

if K%2==1 and len(A_pos)==0:
  for i in range(1, K+1):
    ans *= (A_neg[-i]%1000000007)
    ans %= 1000000007
  print(-ans)

else:
  if K%2==1:
    ans *= A_pos.pop(0)
    K -= 1
  buf = []
  for i in range(len(A_pos)//2):
    buf.append(A_pos[2*i]*A_pos[2*i+1])
  for i in range(len(A_neg)//2):
    buf.append(A_neg[2*i]*A_neg[2*i+1])
  buf.sort(reverse=True)
  for i in range(K//2):
    ans *= (buf[i]%1000000007)
    ans %= 1000000007
  print(ans)

Submission status: Runtime Error

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

A_neg = []
A_pos = []

for i in range(N):
  if A[i] <= 0:
    A_neg.append(-A[i])
  else:
    A_pos.append(A[i])

A_neg.sort(reverse=True)
A_pos.sort(reverse=True)

ans = 1

if K%2==1 and len(A_pos)==0:
  for i in range(1, K+1):
    ans *= (A_neg[-i]%1000000007)
    ans %= 1000000007
  print(-ans)

else:
  if K%2==1:
    ans *= A_pos.pop(0)
    K -= 1
  buf = []
  for i in range(len(A_pos)//2):
    buf.append(A_pos[2*i]*A_pos[2*i+1])
  for i in range(len(A_neg)//2):
    buf.append(A_neg[2*i]*A_neg[2*i+1])
  buf.sort(reverse=True)
  for i in range(K//2):
    ans *= (buf[i]%1000000007)
    ans %= 1000000007
  print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
a.sort(reverse = True)
w = 10**9 + 7
ans = 1
if k%2 == 1:#kは奇数
  for i in range(k):
    ans *= a[i]
  print(ans % w)


else:#kは偶数
  if n%2 == 0:#nは偶数
    A = n//2
    a_new = [a[2*i]*a[2*i+1] for i in range(A)]
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)
      
  else:#nは奇数
    a_plus =[]
    a_minus = []
    positive = 0
    for i in range(n):
      if a[i] > 0 :
        a_plus.append(a[i])
        positive += 1
      else:
        a_minus.append(a[i])
    a_plus.sort(reverse = True)
    a_minus.sort()
    C = positive
    D = n-C
    a_new = []
    a_new.append([a_plus[2*i]*a_plus[2*i+1] for i in range(C//2)])
    a_new.append([a_minus[2*i]*a_minus[2*i+1] for i in range(D//2)])
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)

Submission status: Runtime Error

Solution code:
import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0 and k%2 ==1 :
  if zero >= 1:
    ans = 0
  else:
    minus.sort(reverse=True)
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  if k%2 == 1:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((P-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(M//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)

Submission status: Runtime Error

Solution code:
n,k=[int(i) for i in raw_input().split()]
a=[int(i) for i in raw_input().split()]
a.sort()
b=[]
c=[]
for i in range(n):
    if a[i]<0:
        b.append(a[i])
    else:
        c.append(a[i])
b.sort()
c.sort()
o=[]
i=0;n=len(c);m=len(b);l=0
j=n-1
if(k%2):
    o+=c[j]
    j-=1
    l+=1
while l<k:
    if(j>0 and i<m-1 and l<k-1):
        if(c[j]*c[j-1])>(b[i])*(b[i+1]):
           o+=[c[j],c[j-1]]
           j-=2
        else:
           o+=[b[i],b[i+1]]
           i+=2
        l+=2
    elif(i<m-1 and l<k-1):
        o+=[b[i],b[i+1]]
        l+=2
        i+=2
    elif(j>-1):
        o+=[c[j]]
        l+=1
        j-=1
    else:
        o+=[b[i]]
        i+=1
        l+=1
    
if n==0:
    o=b[m-k:]
s=1
for i in o:
    s*=i
    s%=(10**9+7)
print s

Submission status: Runtime Error

Solution code:
n,k=[int(i) for i in raw_input().split()]
a=[int(i) for i in raw_input().split()]
a.sort()
b=[]
c=[]
for i in range(n):
    if a[i]<0:
        b.append(a[i])
    else:
        c.append(a[i])
b.sort()
c.sort()
o=[]
i=0;n=len(c);m=len(b);l=0
j=n-1
if(k%2):
    o+=c[j]
    j-=1
    l+=1
while l<k:
    if(j>0 and i<m-1 and l<k-1):
        if(c[j]*c[j-1])>(b[i])*(b[i+1]):
           o+=[c[j],c[j-1]]
           j-=2
        else:
           o+=[b[i],b[i+1]]
           i+=2
        l+=2
    elif(i<m-1 and l<k-1):
        o+=[b[i],b[i+1]]
        l+=2
        i+=2
    elif(j>-1):
        o+=[c[j]]
        l+=1
        j-=1
    else:
        break
    
if n==0:
    o=b[m-k:]
s=1
for i in o:
    s*=i
    s%=(10**9+7)
print s

Submission status: Runtime Error

Solution code:
n,k=[int(i) for i in raw_input().split()]
a=[int(i) for i in raw_input().split()]
a.sort()
b=[]
c=[]
for i in range(n):
    if a[i]<0:
        b.append(a[i])
    else:
        c.append(a[i])
b.sort()
c.sort()
o=[]
i=0;n=len(c);m=len(b);l=0
j=n-1
if(k%2):
    o.append(c[j])
    j-=1
    l+=1
while l<k:
    if(j>0 and i<m-1 and l<k-1):
        if(c[j]*c[j-1])>(b[i])*(b[i+1]):
           o+=[c[j],c[j-1]]
           j-=2
        else:
           o+=[b[i],b[i+1]]
           i+=2
        l+=2
    elif(i<m-1 and l<k-1):
        o+=[b[i],b[i+1]]
        l+=2
        i+=2
    elif(j>-1):
        o+=[c[j]]
        l+=1
        j-=1
    
if n==0:
    o=b[m-k:]
s=1
for i in o:
    s*=i
    s%=(10**9+7)
print s

Submission status: Runtime Error

Solution code:
def prod(li, MOD):
    ret = 1
    for a in li:
        ret *= a
        ret %= MOD
    return ret

N, K = map(int, input().split())
MOD = 1_000_000_007
aaa = list(map(int, input().split()))
if N == K:
    print(prod(aaa, MOD))
    exit()
aaa.sort(key=lambda x : abs(x))
if sum(a < 0 for a in aaa[-K:]) % 2 == 0:
    print(prod(aaa[-K:], MOD))
else:
    if all(a <= 0 for a in aaa):
        bbb = aaa[:K]
    else:
        try:
            x1, y1 = min([a for a in aaa[-K:] if a > 0]), min([a for a in aaa[:-K] if a < 0])
        except:
            x1, y1 = 10**10, 1
        try:
            x2, y2 = max([a for a in aaa[-K:] if a < 0]), max([a for a in aaa[:-K] if a >= 0])
        except:
            x2, y2 = 10**10, 1
        bbb = aaa[-K:]
        if abs(x2 * y1) > abs(x1 * y2):
            bbb.remove(x1)
            bbb.append(y1)
        else:
            bbb.remove(x2)
            bbb.append(y2)
    print(prod(bbb, MOD))

Submission status: Runtime Error

Solution code:
def prod(li, MOD):
    ret = 1
    for a in li:
        ret *= a
        ret %= MOD
    return ret

N, K = map(int, input().split())
MOD = 1_000_000_007
aaa = list(map(int, input().split()))
if N == K:
    print(prod(aaa, MOD))
    exit()
aaa.sort(key=lambda x : abs(x))
if sum(a < 0 for a in aaa[-K:]) % 2 == 0:
    print(prod(aaa[-K:], MOD))
else:
    if all(a <= 0 for a in aaa):
        bbb = aaa[:K]
    else:
        try:
            x1, y1 = max([a for a in aaa[-K:] if a > 0]), max([a for a in aaa[:-K] if a < 0])
        except:
            x1, y1 = 1, -(10**9+1)
        try:
            x2, y2 = max([a for a in aaa[-K:] if a < 0]), max([a for a in aaa[:-K] if a >= 0])
        except:
            x2, y2 = -(10**9+1), 1
        bbb = aaa[-K:]
        if abs(x2 * y1) > abs(x1 * y2):
            bbb.remove(x1)
            bbb.append(y1)
        else:
            bbb.remove(x2)
            bbb.append(y2)
    print(prod(bbb, MOD))

Submission status: Runtime Error

Solution code:
def prod(li, MOD):
    ret = 1
    for a in li:
        ret *= a
        ret %= MOD
    return ret

N, K = map(int, input().split())
MOD = 1_000_000_007
aaa = list(map(int, input().split()))
if N == K:
    print(prod(aaa, MOD))
    exit()
if K == 1:
    print(max(aaa) % MOD)
    exit()
aaa.sort(key=lambda x : abs(x))
if sum(a < 0 for a in aaa[-K:]) % 2 == 0:
    print(prod(aaa[-K:], MOD))
else:
    if all(a <= 0 for a in aaa):
        print(prod(aaa[:K], MOD))
    elif all(a <= 0 for a in aaa[:-K]):
        for a in aaa[-K:][::-1]:
            if a > 0:
                break
        bbb = aaa[-K:].remove(a)
        bbb.append(aaa[-(K + 1)])
        print(prod(bbb, MOD))
    elif all(a > 0 for a in aaa[:-K]):
        for a in aaa[-K:][::-1]:
            if a < 0:
                break
        bbb = aaa[-K:].remove(a)
        bbb.append(aaa[-(K + 1)])
        print(prod(bbb, MOD))
    else:
        bbb = aaa[-(K-1):]
        for a in aaa[:-K][::-1]:
            if a * aaa[-K] <= 0:
                bbb.append(a)
                break
        print(prod(bbb, MOD))

Submission status: Runtime Error

Solution code:
def prod(li, MOD):
    ret = 1
    for a in li:
        ret *= a
        ret %= MOD
    return ret

N, K = map(int, input().split())
MOD = 1_000_000_007
aaa = list(map(int, input().split()))
if N == K:
    print(prod(aaa, MOD))
    exit()
aaa.sort(key=lambda x : abs(x))
if sum(a < 0 for a in aaa[-K:]) % 2 == 0:
    print(prod(aaa[-K:], MOD))
else:
    if all(a <= 0 for a in aaa):
        print(prod(aaa[:K], MOD))
    elif all(a <= 0 for a in aaa[:-K]):
        for a in aaa[-K:][::-1]:
            if a > 0:
                break
        bbb = aaa[-K:].remove(a)
        bbb.append(aaa[-(K + 1)])
        print(prod(bbb, MOD))
    elif all(a > 0 for a in aaa[:-K]):
        for a in aaa[-K:][::-1]:
            if a < 0:
                break
        bbb = aaa[-K:].remove(a)
        bbb.append(aaa[-(K + 1)])
        print(prod(bbb, MOD))
    else:
        bbb = aaa[-(K-1):]
        for a in aaa[:-K][::-1]:
            if a * aaa[-K] <= 0:
                bbb.append(a)
                break
        print(prod(bbb, MOD))

Submission status: Runtime Error

Solution code:
def prod(li, MOD):
    ret = 1
    for a in li:
        ret *= a
        ret %= MOD
    return ret

N, K = map(int, input().split())
MOD = 1_000_000_007
aaa = list(map(int, input().split()))
aaa.sort(key=lambda x : abs(x))
if sum(a < 0 for a in aaa[-K:]) % 2 == 0:
    print(prod(aaa[-K:], MOD))
else:
    if all(a <= 0 for a in aaa):
        print(prod(aaa[:K], MOD))
    elif all(a <= 0 for a in aaa[:-K]):
        for a in aaa[-K:]:
            if a > 0:
                break
        bbb = aaa[-K:].remove(a)
        bbb.append(aaa[-(K + 1)])
        print(prod(bbb, MOD))
    elif all(a > 0 for a in aaa[:-K]):
        for a in aaa[-K:]:
            if a < 0:
                break
        bbb = aaa[-K:].remove(a)
        bbb.append(aaa[-(K + 1)])
        print(prod(bbb, MOD))
    else:
        bbb = aaa[-(K-1):]
        for a in aaa[:-K]:
            if a * aaa[-K] <= 0:
                bbb.append(a)
        print(prod(bbb, MOD))

Submission status: Runtime Error

Solution code:
def prod(li, MOD):
    ret = 1
    for a in li:
        ret *= a
        ret %= MOD
    return ret

N, K = map(int, input().split())
aaa = list(map(int, input().split()))
aaa.sort(key=lambda x : abs(x))
pus = []
miu = []
for i in range(K):
    a = aaa.pop()
    if a >= 0:
        pus.append(a)
    else:
        miu.append(a)
if len(pus) == 0:
    if len(miu) % 2 == 1:
        aaa.extend(miu)
        aaa.sort(key=lambda x : abs(x))
        miu = aaa[:K]
elif len(miu) == 0:
    pass
elif len(miu) % 2 == 1:
    x = min(pus) if abs(min(pus)) > abs(max(miu)) else max(miu)
    if x >= 0 and all(a >= 0 for a in aaa):
        miu.pop()
        pus.append(aaa[-1])
        pus.append(aaa[-2])
    elif x < 0 and all(a <= 0 for a in aaa):
        pus.pop()
        miu.append(aaa[-1])
        miu.append(aaa[-2])
    else:
        if abs(pus[-1]) > abs(miu[-1]):
            miu.pup()
        else:
            pus.pop()
        for y in aaa[::-1]:
            if x * y <= 0:
                if y >= 0:
                    pus.append(y)
                else:
                    miu.append(y)

ans = 1
MOD = 1_000_000_007
ans = prod(pus, MOD) * prod(miu, MOD)
ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
MOD = (int) (1e9+7)

def power(a,n):
    if a == 0: return 0
    if n == 0: return 1

    res = 1
    while n > 0:
        if n % 2 == 1: res = res * a % MOD
        a = a * a % MOD
        n //= 2

    return res

def inverse(n):
    return power(n, MOD-2)

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

B = []
pos, neg = 0, 0
for a in A:
    if a > 0:
        B.append([a,1])
        pos += 1
    if a < 0:
        B.append([-a,-1])
        neg += 1
    if a == 0:
        B.append([0,0])
B.sort(reverse=True)

ans, sign  = 1, 1
if N == neg and K % 2 == 1:
    for i in range(K):
        ans *= B[N-1-i][0] 
        ans %= MOD
    print(-ans % MOD)
    exit()

for i in range(K):
    ans *= B[i][0]
    ans %= MOD
    sign *= B[i][1]

if sign < 0:
    out_neg, out_pos = 0,0
    for i in range(K):
        if B[K-1-i][1] < 0:
            out_neg = B[K-1-i][0]
            break
    
    for i in range(K):
        if B[K-1-i][1] > 0:
            out_pos = B[K-1-i][0]
            break
    
    for i in range(N-K):
        if B[K+i][1] > 0:
            in_pos = B[K+i][0]
        break
    
    for i in range(N-K):
        if B[K+i][1] < 0:
            in_neg = B[K+i][0]
        break
    
    #print([out_neg,out_pos])
    #print([in_neg,in_pos])

    if out_neg == 0:
        ans = (ans * in_neg % MOD) * inverse(out_pos) % MOD
    elif out_pos == 0:
        ans = (ans * in_pos % MOD) * inverse(out_neg) % MOD
    else:
        if(out_pos * in_pos > out_neg + in_neg):
            ans = (ans * in_neg % MOD) * inverse(out_pos) % MOD
        else:
            ans = (ans * in_pos % MOD) * inverse(out_neg) % MOD
            
print(ans)

Submission status: Runtime Error

Solution code:
MOD = (int) (1e9+7)

def power(a,n):
    if a == 0: return 0
    if n == 0: return 1

    res = 1
    while n > 0:
        if n % 2 == 1: res = res * a % MOD
        a = a * a % MOD
        n /= 2

    return res

def inverse(n):
    return power(n, MOD-2)

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

B = []
pos, neg = 0, 0
for a in A:
    if a > 0:
        B.append([a,1])
        pos += 1
    if a < 0:
        B.append([-a,-1])
        neg += 1
    if a == 0:
        B.append([0,0])
B.sort(reverse=True)

#print(B)

ans, sign  = 1, 1
if N == neg and K % 2 == 1:
    for i in range(K):
        ans *= B[N-1-i][0] 
        ans %= MOD
    print(-ans % MOD)
    exit()

for i in range(K):
    ans *= B[i][0]
    ans %= MOD
    sign *= B[i][1]

if sign < 0:
    out_neg, out_pos = 0,0
    for i in range(K):
        if B[K-1-i][1] < 0:
            out_neg = B[K-1-i][0]
            break
    
    for i in range(K):
        if B[K-1-i][1] > 0:
            out_pos = B[K-1-i][0]
            break
    
    for i in range(N-K):
        if B[K+i][1] > 0:
            in_pos = B[K+i][0]
        break
    
    for i in range(N-K):
        if B[K+i][1] < 0:
            in_neg = B[K+i][0]
        break
    
    #print([out_neg,out_pos])
    #print([in_neg,in_pos])

    if out_neg == 0:
        ans = (ans * in_neg % MOD) * inverse(out_pos) % MOD
    elif out_pos == 0:
        ans = (ans * in_pos % MOD) * inverse(out_neg) % MOD
    else:
        if(out_pos * in_pos > out_neg + in_neg):
            ans = (ans * in_neg % MOD) * inverse(out_pos) % MOD
        else:
            ans = (ans * in_pos % MOD) * inverse(out_neg) % MOD
            
print(ans)

Submission status: Runtime Error

Solution code:
MOD = (int) (1e9+7)

def power(a,n):
    if a == 0: return 0
    if n == 1: return 1

    res = 1
    while n > 0:
        if n % 2 == 1: res = res * a % MOD
        a = a * a % MOD

    return res

def inverse(n):
    return power(n, MOD-2)

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

B = []
pos, neg = 0, 0
for a in A:
    if a > 0:
        B.append([a,1])
        pos += 1
    if a < 0:
        B.append([-a,-1])
        neg += 1
    if a == 0:
        B.append([0,0])
B.sort(reverse=True)

#print(B)

ans, sign  = 1, 1
if N == neg and K % 2 == 1:
    for i in range(K):
        ans *= B[N-1-i][0] 
        ans %= MOD
    print(-ans % MOD)
    exit()

for i in range(K):
    ans *= B[i][0]
    ans %= MOD
    sign *= B[i][1]

if sign < 0:
    out_neg, out_pos = 0,0
    for i in range(K):
        if B[K-1-i][1] < 0:
            out_neg = B[K-1-i][0]
            break
    
    for i in range(K):
        if B[K-1-i][1] > 0:
            out_pos = B[K-1-i][0]
            break
    
    for i in range(N-K):
        if B[K+i][1] > 0:
            in_pos = B[K+i][0]
        break
    
    for i in range(N-K):
        if B[K+i][1] < 0:
            in_neg = B[K+i][0]
        break
    
    #print([out_neg,out_pos])
    #print([in_neg,in_pos])

    if out_neg == 0:
        ans = (ans * in_neg % MOD) * inverse(out_pos) % MOD
    elif out_pos == 0:
        ans = (ans * in_pos % MOD) * inverse(out_neg) % MOD
    else:
        if(out_pos * in_pos > out_neg + in_neg):
            ans = (ans * in_neg % MOD) * inverse(out_pos) % MOD
        else:
            ans = (ans * in_pos % MOD) * inverse(out_neg) % MOD
            
print(ans)

Submission status: Runtime Error

Solution code:
MOD = (int) (1e9+7)

def power(a,n):
    if a == 0: return 0
    if n == 1: return 1

    res = 1
    while n > 0:
        if n % 2 == 1: res = res * a % MOD
        a = a * a % MOD

    return res

def inverse(n):
    return power(n, MOD-2)

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

B = []
pos, neg = 0, 0
for a in A:
    if a > 0:
        B.append([a,1])
        pos += 1
    if a < 0:
        B.append([-a,-1])
        neg += 1
    if a == 0:
        B.append([0,0])
B.sort(reverse=True)

print(B)

ans, sign  = 1, 1
if N == neg and K % 2 == 1:
    for i in range(K):
        ans *= B[N-1-i][0] 
        ans %= MOD
    print(-ans % MOD)
    exit()

for i in range(K):
    ans *= B[i][0]
    ans %= MOD
    sign *= B[i][1]

if sign < 0:
    out_neg, out_pos = 0,0
    for i in range(K):
        if B[K-1-i][1] < 0:
            out_neg = B[K-1-i][0]
            break
    
    for i in range(K):
        if B[K-1-i][1] > 0:
            out_pos = B[K-1-i][0]
            break
    
    for i in range(N-K):
        if B[K+i][1] > 0:
            in_pos = B[K+i][0]
        break
    
    for i in range(N-K):
        if B[K+i][1] < 0:
            in_neg = B[K+i][0]
        break
    
    #print([out_neg,out_pos])
    #print([in_neg,in_pos])

    if out_neg == 0:
        ans = (ans * in_neg % MOD) * inverse(out_pos) % MOD
    elif out_pos == 0:
        ans = (ans * in_pos % MOD) * inverse(out_neg) % MOD
    else:
        if(out_pos * in_pos > out_neg + in_neg):
            ans = (ans * in_neg % MOD) * inverse(out_pos) % MOD
        else:
            ans = (ans * in_pos % MOD) * inverse(out_neg) % MOD
            
print(ans)

Submission status: Runtime Error

Solution code:
def can_plus(PLUSS, MINUSS, K):
    PLUSS = list(reversed(sorted(PLUSS)))
    MINUSS = list(sorted(MINUSS))

    cumul = 1

    plus_idx = 0
    minus_idx = 0

    cnt = 0
    while True:
        if cnt == K:
            break
        elif cnt == K-1:
            cumul = cumul * PLUSS[plus_idx]
            plus_idx += 1
            cnt += 1
        elif minus_idx >= len(MINUSS) - 1:
            cumul = cumul * PLUSS[plus_idx]
            plus_idx += 1
            cnt += 1
        elif plus_idx >= len(PLUSS) - 1:
            cumul = cumul * MINUSS[minus_idx] * MINUSS[minus_idx + 1]
            minus_idx += 2
            cnt += 2
        elif (plus_idx == len(PLUSS) - 2) and ((K - cnt) % 2) == 1:
            cumul = cumul * PLUSS[plus_idx]
            plus_idx += 1
            cnt += 1
        elif (plus_idx <= len(PLUSS) - 2) and (minus_idx <= len(MINUSS) - 2):
            plus_pair = PLUSS[plus_idx] * PLUSS[plus_idx + 1]
            minus_pair = MINUSS[minus_idx] * MINUSS[minus_idx + 1]
            if plus_pair >= minus_pair:
                cumul = cumul * plus_pair
                plus_idx += 2
            else:
                cumul = cumul * minus_pair
                minus_idx += 2
            cnt += 2
        else:
            cnt += 1
    return cumul


def main():
    a = input()
    aa = a.split()
    K = int(aa[1])

    b = input()
    A = [int(bb) for bb in b.split()]

    PLUSS = []
    MINUSS = []
    ZEROS = []
    for a in A:
        if a > 0:
            PLUSS.append(a)
        elif a < 0:
            MINUSS.append(a)
        else:
            ZEROS.append(a)

    # ゼロ以下になることが避けられない場合
    if len(MINUSS) + len(PLUSS) < K:
        print("0")
        return
    elif (len(PLUSS) == 0 or (len(MINUSS) + len(PLUSS) == K)) and (len(MINUSS) % 2) == 1:
        if len(ZEROS) > 0:
            print("0")
            return
        elif len(PLUSS) == 0:
            cumul = 1
            m = list(reversed(sorted(MINUSS)))
            for i in range(K):
                cumul = cumul*m[i]
        else:
            cumul = 1
            for a in A:
                cumul = cumul * a
    else:
        cumul = can_plus(PLUSS, MINUSS, K)

    DIV = 1_000_000_007
    print(cumul % DIV)


main()

Submission status: Runtime Error

Solution code:
import math


def can_plus(PLUSS, MINUSS, K):
    PLUSS = list(reversed(sorted(PLUSS)))
    MINUSS = list(sorted(MINUSS))

    cumul = 1

    plus_idx = 0
    minus_idx = 0

    cnt = 0
    while True:
        if cnt == K:
            break
        elif cnt == K-1:
            cumul = cumul * PLUSS[plus_idx]
            plus_idx += 1
            cnt += 1
        elif (plus_idx == len(PLUSS) - 2) and ((K - cnt) % 2) == 1:
            cumul = cumul * PLUSS[plus_idx]
            plus_idx += 1
            cnt += 1
        elif (plus_idx <= len(PLUSS) - 2) and (minus_idx <= len(MINUSS) - 2):
            plus_pair = PLUSS[plus_idx] * PLUSS[plus_idx + 1]
            minus_pair = MINUSS[minus_idx] * MINUSS[minus_idx + 1]
            if plus_pair >= minus_pair:
                cumul = cumul * plus_pair
                plus_idx += 2
            else:
                cumul = cumul * minus_pair
                minus_idx += 2
            cnt += 2
        elif minus_idx >= len(MINUSS) - 1:
            cumul = cumul * PLUSS[plus_idx]
            plus_idx += 1
            cnt += 1
        else:
            cumul = cumul * MINUSS[minus_idx] * MINUSS[minus_idx + 1]
            minus_idx += 2
            cnt += 2
    return cumul


def main():
    a = input()
    aa = a.split()
    K = int(aa[1])

    b = input()
    A = [int(bb) for bb in b.split()]

    PLUSS = []
    MINUSS = []
    ZEROS = []
    for a in A:
        if a > 0:
            PLUSS.append(a)
        elif a < 0:
            MINUSS.append(a)
        else:
            ZEROS.append(a)

    # ゼロ以下になることが避けられない場合
    if len(MINUSS) + len(PLUSS) < K:
        print("0")
        return
    elif (len(PLUSS) == 0 or (len(MINUSS) + len(PLUSS) == K)) and (len(MINUSS) % 2) == 1:
        if len(ZEROS) > 0:
            print("0")
            return
        elif len(PLUSS) == 0:
            cumul = 1
            m = list(reversed(sorted(MINUSS)))
            for i in range(K):
                cumul = cumul*m[i]
        else:
            cumul = 1
            for a in A:
                cumul = cumul * a
    else:
        cumul = can_plus(PLUSS, MINUSS, K)

    DIV = 1_000_000_007
    print(cumul % DIV)


main()