Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

We will choose exactly K of these elements. Find the maximum possible product of the chosen elements.

Then, print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Constraints

1 \leq K \leq N \leq 2\times 10^5

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

Print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

The possible products of the two chosen elements are 2, -3, -4, -6, -8, and 12, so the maximum product is 12.

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

The possible products of the three chosen elements are -24, -12, -8, and -6, so the maximum product is -6.

We print this value modulo (10^9+7), that is, 1000000001.

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

The possible products of the one chosen element are -1 and 1000000000, so the maximum product is 1000000000.

Sample Input 4

10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1

Sample Output 4

999983200

Be sure to print the product modulo (10^9+7).



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True,key=lambda x : abs(x))
ans=1
#因数のうちの最も絶対の小さい正と負の数
plus1=-1
minus1=-1
for i in range(k):
    ans*=a[i]
    if a[i]>=0:
        plus1=i
    else:
        minus1=i
#因数に含まれなっかた数のうち最も絶対値の大きい正と負に数
plus2=-1
for i in range(k,n):
    if a[i]>=0:
        plus2=i
        break
minus2=-1
for i in range(k,n):
    if a[i]<0:
        minus2=i
        break

Submission status: Wrong Answer

Solution code:
MOD=10**9+7
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls=sorted(ls, key=lambda x: -abs(x))

#かける数をフラグで管理
flag=[0 for _ in range(N)]

sign=0
for i in range(K):
  flag[i]=1
  if ls[i]<0:
    sign=(sign+1)%2

if sign==1: #絶対値が大きい順にかけた数は負か？
  #フラグのない負の数を、フラグのある正の数と取り換え可能か？
  swap_neg_to_pos=[]
  for i in range(K,N):
    if ls[i]<0:
      for j in range(K):
        if ls[K-1-j]>0:
          swap_neg_to_pos=[i,K-1-j,(0.0-ls[K-1-j])/ls[i]]
          break
      break
  #フラグのない正の数を、フラグのある負の数と取り換え可能か？
  swap_pos_to_neg=[]
  for i in range(K,N):
    if ls[i]>0:
      for j in range(K):
        if ls[K-1-j]<0:
          swap_pos_to_neg=[i,K-1-j,(0.0-ls[K-1-j])/ls[i]]
          break
      break

  #フラグを修正        
  if swap_neg_to_pos!=[] and swap_pos_to_neg!=[]: #どちらも取り換え可能
    if swap_neg_to_pos[2]<swap_pos_to_neg[2]: #負の数にフラグを与えたほうがロスが少ないとき
      flag[swap_neg_to_pos[0]]=1
      flag[swap_neg_to_pos[1]]=0
    else: #正の数にフラグを与えたほうがロスが少ないとき
      flag[swap_pos_to_neg[0]]=1
      flag[swap_pos_to_neg[1]]=0
  elif swap_neg_to_pos==[] and swap_pos_to_neg==[]: #どちらも取り換え不可能なとき 
    flag.reverse()
  elif swap_pos_to_neg!=[]: #正の数にフラグを与えることのみ可能なとき
    flag[swap_pos_to_neg[0]]=1
    flag[swap_pos_to_neg[1]]=0
  else:                     #負の数にフラグを与えることのみ可能なとき
    flag[swap_neg_to_pos[0]]=1
    flag[swap_neg_to_pos[1]]=0

ans=1
for i in range(N):
  if flag[i]==1:
    ans=(ans*ls[i])%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
MOD=10**9+7
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls=sorted(ls, key=lambda x: -abs(x))

#かける数をフラグで管理
flag=[0 for _ in range(N)]

sign=0
for i in range(K):
  flag[i]=1
  if ls[i]<0:
    sign=(sign+1)%2

if sign==1: #絶対値が大きい順にかけた数は負か？
  #フラグのない負の数を、フラグのある正の数と取り換え可能か？
  swap_neg_to_pos=[]
  for i in range(K,N):
    if ls[i]<0:
      for j in range(K):
        if ls[K-1-j]>0:
          swap_neg_to_pos=[i,K-1-j,(0.0-ls[K-1-j])/ls[i]]
          break
      break
  #フラグのない正の数を、フラグのある負の数と取り換え可能か？
  swap_pos_to_neg=[]
  for i in range(K,N):
    if ls[i]>0:
      for j in range(K):
        if ls[K-1-j]<0:
          swap_pos_to_neg=[i,K-1-j,(0.0-ls[K-1-j])/ls[i]]
          break

  #フラグを修正        
  if swap_neg_to_pos!=[] and swap_pos_to_neg!=[]: #どちらも取り換え可能
    if swap_neg_to_pos[2]<swap_pos_to_neg[2]: #負の数にフラグを与えたほうがロスが少ないとき
      flag[swap_neg_to_pos[0]]=1
      flag[swap_neg_to_pos[1]]=0
    else: #正の数にフラグを与えたほうがロスが少ないとき
      flag[swap_pos_to_neg[0]]=1
      flag[swap_pos_to_neg[1]]=0
  elif swap_neg_to_pos==[] and swap_pos_to_neg==[]: #どちらも取り換え不可能なとき 
    flag.reverse()
  elif swap_pos_to_neg!=[]: #正の数にフラグを与えることのみ可能なとき
    flag[swap_pos_to_neg[0]]=1
    flag[swap_pos_to_neg[1]]=0
  else:                     #負の数にフラグを与えることのみ可能なとき
    flag[swap_neg_to_pos[0]]=1
    flag[swap_neg_to_pos[1]]=0

ans=1
for i in range(N):
  if flag[i]==1:
    ans=(ans*ls[i])%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
MOD=10**9+7
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls=sorted(ls, key=lambda x: -abs(x))

#かける数をフラグで管理
flag=[0 for _ in range(N)]

sign=0
for i in range(K):
  flag[i]=1
  if ls[i]<0:
    sign=(sign+1)%2

if sign==1: #絶対値が大きい順にかけた数は負か？
  #フラグのない負の数を、フラグのある正の数と取り換え可能か？
  swap_neg_to_pos=[]
  for i in range(K,N):
    if ls[i]<0:
      for j in range(K):
        if ls[K-1-j]>0:
          swap_neg_to_pos=[i,K-1-j,(0.0-ls[K-1-j])/ls[i]]
          break
      break
  #フラグのない正の数を、フラグのある負の数と取り換え可能か？
  swap_pos_to_neg=[]
  for i in range(K,N):
    if ls[i]>0:
      for j in range(K):
        if ls[K-1-j]<0:
          swap_pos_to_neg=[i,K-1-j,(0.0-ls[K-1-j])/ls[i]]
          break

  #フラグを修正        
  if swap_neg_to_pos!=[] and swap_pos_to_neg!=[]: #どちらも取り換え可能
    if swap_neg_to_pos[2]<swap_pos_to_neg[2]: #負の数にフラグを与えたほうがロスが少ないとき
      print(swap_neg_to_pos)
      flag[swap_neg_to_pos[0]]=1
      flag[swap_neg_to_pos[1]]=0
    else: #正の数にフラグを与えたほうがロスが少ないとき
      flag[swap_pos_to_neg[0]]=1
      flag[swap_pos_to_neg[1]]=0
  elif swap_neg_to_pos==[] and swap_pos_to_neg==[]: #どちらも取り換え不可能なとき 
    flag.reverse()
  elif swap_pos_to_neg!=[]: #正の数にフラグを与えることのみ可能なとき
    flag[swap_pos_to_neg[0]]=1
    flag[swap_pos_to_neg[1]]=0
  else:                     #負の数にフラグを与えることのみ可能なとき
    flag[swap_neg_to_pos[0]]=1
    flag[swap_neg_to_pos[1]]=0

ans=1
for i in range(N):
  if flag[i]==1:
    ans=(ans*ls[i])%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, K = read_values()
    A = read_list()
    A.sort()
    res = 1    
    if N == K:
        for a in A:
            res *= a
            res %= mod
    elif A[-1] < 0 or A[0] >= 0:
        for a in A[:-(K + 1):-1]:
            res *= a
            res %= mod
    else:
        k = bisect.bisect_left(A, 0)
        neg = A[:k]
        pos = A[k:][::-1]
        
        n = 0
        p = 0
        while n + p < K:
            if n == len(neg):
                p += 1
            elif p == len(pos):
                n += 1
            elif -neg[n] <= pos[p]:
                p += 1
            else:
                n += 1
        if n % 2 == 1:
            if p == 0 or n == len(neg):
                n -= 1
                p += 1
            elif p == len(pos):
                n += 1
                p -= 1
            elif pos[p] * pos[p - 1]  <= neg[n] * neg[n - 1]:
                n += 1
                p -= 1
            else:
                n -= 1
                p += 1

        for a in pos[:p]:
            res *= a
            res %= mod
        
        for a in neg[:n]:
            res *= a
            res %= mod

    print(res % mod)

    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, K = read_values()
    A = read_list()
    A.sort()
    
    k = bisect.bisect_left(A, 0)
    res = 1    
    if N == K:
        for a in A:
            res *= a
            res %= mod
    elif k == N:
        for a in A[:-(K + 1):-1]:
            res *= a
            res %= mod
    else:
        l = 0
        r = 0
        while l + r < K:
            if abs(A[l]) <= abs(A[-(r + 1)]):
                r += 1
            else:
                l += 1
        if l % 2 == 1:
            if r == 0:
                r += 1
                l -= 1
            elif A[l - 1] * A[l] <= A[-r] * A[-(r + 1)]:
                l -= 1
                r += 1
            else:
                l += 1
                r -= 1

        for a in A[:l]:
            res *= a
            res %= mod
        
        for a in A[:-(r + 1):-1]:
            res *= a
            res %= mod

    print(res % mod)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, K = read_values()
    A = read_list()
    A.sort()
    
    k = bisect.bisect_left(A, 0)
    res = 1    
    if N == K:
        for a in A:
            res *= a
            res %= mod
    elif k == N:
        for a in A[:-(K + 1):-1]:
            res *= a
            res %= mod
    else:
        l = 0
        r = 0
        while l + r < K:
            if abs(A[l]) <= abs(A[-(r + 1)]):
                r += 1
            else:
                l += 1
        if l % 2 == 1:
            if A[l] >= 0:
                l -= 1
                r += 1
            elif A[-(r + 1)] < 0:
                l += 1
                r -= 1
            elif abs(A[l - 1]) * abs(A[l]) <= abs(A[-r]) * abs(A[-(r + 1)]):
                l -= 1
                r += 1
            else:
                l += 1
                r -= 1

        for a in A[:l]:
            res *= a
            res %= mod
        
        for a in A[:-(r + 1):-1]:
            res *= a
            res %= mod

    print(res % mod)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, K = read_values()
    A = read_list()
    A.sort()
    
    k = bisect.bisect_left(A, 0)
    res = 1    
    if N == K:
        for a in A:
            res *= a
            res %= mod
    elif k == N:
        for a in A[:-(K + 1):-1]:
            res *= a
            res %= mod
    else:
        l = 0
        r = 0
        while l + r < K:
            if abs(A[l]) <= abs(A[-(r + 1)]):
                r += 1
            else:
                l += 1
        if l % 2 == 1:
            if A[l] >= 0:
                l -= 1
                r += 1
            elif abs(A[l - 1]) * abs(A[l]) <= abs(A[-r]) * abs(A[-(r + 1)]):
                l -= 1
                r += 1
            else:
                l += 1
                r -= 1

        for a in A[:l]:
            res *= a
            res %= mod
        
        for a in A[:-(r + 1):-1]:
            res *= a
            res %= mod

    print(res % mod)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, K = read_values()
    A = read_list()
    A.sort()
    
    k = bisect.bisect_left(A, 0)
    res = 1    
    if N == K:
        for a in A:
            res *= a
            res %= mod
    elif k == N:
        for a in A[:-(K + 1):-1]:
            res *= a
            res %= mod
    else:
        l = 0
        r = 0
        while l + r < K:
            if abs(A[l]) <= abs(A[-(r + 1)]):
                r += 1
            else:
                l += 1

        if l % 2 == 1:
            if A[l + 1] >= 0:
                l -= 1
                r += 1
            elif abs(A[l]) * abs(A[l + 1]) <= abs(A[-(r + 1)]) * abs(A[-(r + 2)]):
                l -= 1
                r += 1
            else:
                l += 1
                r -= 1

        for a in A[:l]:
            res *= a
            res %= mod
        
        for a in A[:-(r + 1):-1]:
            res *= a
            res %= mod

    print(res % mod)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, K = read_values()
    A = read_list()
    A.sort()
    
    k = bisect.bisect_left(A, 0)
    res = 1    
    if N == K:
        for a in A:
            res *= a
            res %= mod
    elif k == N:
        for a in A[:-(K + 1):-1]:
            res *= a
            res %= mod
    else:
        l = 0
        r = 0
        while l + r < K:
            if abs(A[l]) <= abs(A[-(r + 1)]):
                r += 1
            else:
                l += 1

        if l % 2 == 1:
            if k == l:
                l -= 1
                r += 1
            elif abs(A[l]) * abs(A[l + 1]) <= abs(A[-(r + 1)]) * abs(A[-(r + 2)]):
                l -= 1
                r += 1
            else:
                l += 1
                r -= 1

        for a in A[:l]:
            res *= a
            res %= mod
        
        for a in A[:-(r + 1):-1]:
            res *= a
            res %= mod

    print(res % mod)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, K = read_values()
    A = read_list()
    A.sort()
    
    k = bisect.bisect_left(A, 0)
    res = 1    
    if N == K:
        for a in A:
            res *= a
            res %= mod
    elif k == N:
        for a in A[:-(K + 1):-1]:
            res *= a
            res %= mod
    else:
        l = 0
        r = 0
        while l + r < K:
            if abs(A[l]) <= abs(A[-(r + 1)]):
                r += 1
            else:
                l += 1

        if l % 2 == 1:
            if abs(A[l]) * abs(A[l + 1]) <= abs(A[-(r + 1)]) * abs(A[-(r + 2)]):
                l -= 1
                r += 1
            else:
                l += 1
                r -= 1

        for a in A[:l]:
            res *= a
            res %= mod
        
        for a in A[:-(r + 1):-1]:
            res *= a
            res %= mod

    print(res % mod)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, K = read_values()
    A = read_list()
    A.sort()
    
    k = bisect.bisect_left(A, 0)
    res = 1    
    if N == K:
        for a in A:
            res *= a
            res %= mod
    elif k == N:
        for a in A[:-(K + 1):-1]:
            res *= a
            res %= mod
    else:
        l = 0
        r = 0
        while l + r < K:
            if abs(A[l]) <= abs(A[-(r + 1)]):
                r += 1
            else:
                l += 1

        if l % 2 == 1:
            if abs(A[l]) * abs(A[-(r + 1)]) <= abs(A[l + 1]) * abs(A[-(r + 2)]):
                l -= 1
                r += 1
            else:
                l += 1
                r -= 1

        for a in A[:l]:
            res *= a
            res %= mod
        
        for a in A[:-(r + 1):-1]:
            res *= a
            res %= mod

    print(res % mod)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, K = read_values()
    A = read_list()
    A.sort()
    
    k = bisect.bisect_left(A, 0)
    res = 1    
    if N == K:
        res = 1
        for a in A:
            res *= a
            res %= mod
    elif k == N:
        for a in A[:-(K + 1):-1]:
            res *= a
            res %= mod
    else:
        l = 0
        r = 0
        while l + r < K:
            if abs(A[l]) <= abs(A[-(r + 1)]):
                r += 1
            else:
                l += 1

        if l % 2 == 1:
            if A[l] * A[-(r + 1)] <= A[l + 1] * A[-(r + 2)]:
                l -= 1
                r += 1
            else:
                l += 1
                r -= 1

        for a in A[:l]:
            res *= a
            res %= mod
        
        for a in A[:-(r + 1):-1]:
            res *= a
            res %= mod

    print(res % mod)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, K = read_values()
    A = read_list()
    A.sort()
    k = bisect.bisect_left(A, 0)

    res = 1
    if k == N:
        for a in A[:-(K + 1):-1]:
            res *= a
            res %= mod
    else:
        l = 0
        r = 0
        while l + r < K:
            if abs(A[l]) <= abs(A[-(r + 1)]):
                r += 1
            else:
                l += 1

        if l % 2 == 1:
            if A[l + 1] * A[-(r + 1)] <= A[l] * A[-(r + 2)]:
                l -= 1
                r += 1
            else:
                l += 1
                r -= 1

        for a in A[:l]:
            res *= a
            res %= mod
        
        for a in A[:-(r + 1):-1]:
            res *= a
            res %= mod

    print(res % mod)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, K = read_values()
    A = read_list()
    A.sort()
    k = bisect.bisect_left(A, 0)

    res = 1
    if k == N:
        for a in A[:-(K + 1):-1]:
            res *= a
            res %= mod
    else:
        l = 0
        r = 0
        while l + r < K:
            if abs(A[l]) <= abs(A[-(r + 1)]):
                r += 1
            else:
                l += 1

        if l % 2 == 1:
            if A[l] * A[l + 1] <= A[-(r + 1)] + A[-(r + 2)]:
                l -= 1
                r += 1
            else:
                l += 1
                r -= 1

        for a in A[:l]:
            res *= a
            res %= mod
        
        for a in A[:-(r + 1):-1]:
            res *= a
            res %= mod

    print(res % mod)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N, K=map(int,input().split())
A=list(map(int,input().split()))
def Prod(P,j):
    k=1
    for i in range(len(P)):
        if i!=j:
            k=k*P[i][1]
    return k%(10**9+7)
B=[]
for i in range(N):
    B.append((abs(A[i]),A[i]))
C=sorted(B,reverse=True)
S = C[0:K]
T = C[K:N]
c=0
for i in range(K):
    if C[i][1]<0:
        c=c+1
if c%2==0:
    print(Prod(S,K))
else:
    J=None
    if S[K - 1][1] < 0:
        sgn = -1
    else:
        sgn = 1
    for j in range(K):
        if sgn * S[K - j - 1][1] < 0:
            J=j
            break
    c1=0
    if J==None:
        c2=1
    else:
        c2=0
    Z=[]
    for i in range(N-K):
        if c1==0 and sgn*T[i][1] < 0:
            Z.append(Prod(S,K-1)*T[i][1])
            c1=1
            c2=1
        elif c2==0 and sgn*T[i][1]>0:
            Z.append(Prod(S,J)*T[i][1])
            c2=1
        elif c1==1 and c2==1:
            break
    if Z!=[]:
        Z=sorted(Z)
        print(Z[0])
    else: # すべてマイナス
        print(Prod(C[N-K:N],N))

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
N,K = [int(hoge) for hoge in input().split()]
A = [int(hoge) for hoge in input().split()]
#必然、マイナスの数は偶数個がいい
Plus = []
Minus = []
Zero = 0
for a in A:
    if a > 0:
        Plus.append(a)
    elif a < 0:
        Minus.append(-a)
    else:
        Zero += 1
Plus.sort(reverse=True)
Minus.sort(reverse=True)
Nonzero = N - Zero
ans = 1
#ノンゼロ<K...必ずゼロ
#ノンゼロ == K ...マイナスが偶数→全部掛け
#                 マイナスが奇数→ゼロがあればゼロ、なければ全部掛け
#ノンゼロ > K:
#   Kが偶数→2つずつペアにしてデカい順にかける
#   Kが奇数→2つずつペアにするが、プラスのラスト1つを存在しないものとして扱う。
#   余ったらプラスの最小のやつをかける
if Nonzero < K:
    ans = 0
elif Nonzero == K:
    for a in A:
        if a:
            ans *= a
            ans %= MOD
    if len(Minus) % 2 and Zero:
        ans = 0
else:
    if K%2 == 0:
        Duet = []
        for n,p in enumerate(Plus):
            if n%2 == 0:
                cur = p
            else:
                Duet.append((cur*p , "Plus" ))
        for n,p in enumerate(Minus):
            if n%2 == 0:
                cur = p
            else:
                Duet.append((cur*p , "Minus" ))
        Duet.sort(reverse=True)
        ans = 1
        for i in range(K//2):
            ans *= Duet[i][0]
            ans %= MOD
    else:
        if len(Plus) > 0:
            Duet = []
            for n,p in enumerate(Plus):
                if n==len(Plus)-1:
                    break
                if n%2 == 0:
                    cur = p
                else:
                    Duet.append((cur*p , True ))
            for n,p in enumerate(Minus):
                if n%2 == 0:
                    cur = p
                else:
                    Duet.append((cur*p , False ))
            Duet.sort(reverse=True)
            ans = 1
            P = 0
            M = 0
            for i in range(K//2):
                ans *= Duet[i][0]
                ans %= MOD
                if Duet[i][1]:
                    P += 1
                else:
                    M += 1
            ans *= Plus[2*P]
            ans %= MOD
        else:
            for i in range(K):
                ans *= A[i]
                ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
N,K = [int(hoge) for hoge in input().split()]
A = [int(hoge) for hoge in input().split()]
#必然、マイナスの数は偶数個がいい
Plus = []
Minus = []
Zero = 0
for a in A:
    if a > 0:
        Plus.append(a)
    elif a < 0:
        Minus.append(-a)
    else:
        Zero += 1
Plus.sort(reverse=True)
Minus.sort(reverse=True)
Nonzero = N - Zero
ans = 1
#ノンゼロ<K...必ずゼロ
#ノンゼロ == K ...マイナスが偶数→全部掛け
#                 マイナスが奇数→ゼロがあればゼロ、なければ全部掛け
#ノンゼロ > K:
#   Kが偶数→2つずつペアにしてデカい順にかける
#   Kが奇数→2つずつペアにするが、プラスのラスト1つを存在しないものとして扱う。
#   余ったらプラスの最小のやつをかける
if Nonzero < K:
    ans = 0
elif Nonzero == K:
    for a in A:
        if a:
            ans *= a
            ans %= MOD
    if len(Minus) % 2:
        ans = 0
else:
    if K%2 == 0:
        Duet = []
        for n,p in enumerate(Plus):
            if n%2 == 0:
                cur = p
            else:
                Duet.append((cur*p , "Plus" ))
        for n,p in enumerate(Minus):
            if n%2 == 0:
                cur = p
            else:
                Duet.append((cur*p , "Minus" ))
        Duet.sort(reverse=True)
        ans = 1
        for i in range(K//2):
            ans *= Duet[i][0]
            ans %= MOD
    else:
        if len(Plus) > 0:
            Duet = []
            for n,p in enumerate(Plus):
                if n==len(Plus)-1:
                    break
                if n%2 == 0:
                    cur = p
                else:
                    Duet.append((cur*p , True ))
            for n,p in enumerate(Minus):
                if n%2 == 0:
                    cur = p
                else:
                    Duet.append((cur*p , False ))
            Duet.sort(reverse=True)
            ans = 1
            P = 0
            M = 0
            for i in range(K//2):
                ans *= Duet[i][0]
                ans %= MOD
                if Duet[i][1]:
                    P += 1
                else:
                    M += 1
            ans *= Plus[2*P]
            ans %= MOD
        else:
            for i in range(K):
                ans *= A[i]
                ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
N,K = [int(hoge) for hoge in input().split()]
A = [int(hoge) for hoge in input().split()]
#必然、マイナスの数は偶数個がいい
Plus = []
Minus = []
Zero = 0
for a in A:
    if a > 0:
        Plus.append(a)
    elif a < 0:
        Minus.append(a)
    else:
        Zero += 1
Plus.sort(reverse=True)
Minus.sort(reverse=True)
Nonzero = N - Zero
ans = 1
#ノンゼロ<K...必ずゼロ
#ノンゼロ == K ...マイナスが偶数→全部掛け
#                 マイナスが奇数→ゼロがあればゼロ、なければ全部掛け
#ノンゼロ > K:
#   Kが偶数→2つずつペアにしてデカい順にかける
#   Kが奇数→2つずつペアにするが、プラスのラスト1つを存在しないものとして扱う。
#   余ったらプラスの最小のやつをかける
if Nonzero < K:
    ans = 0
elif Nonzero == K:
    if len(Minus)%2 and Zero:
        ans = 0
    else:
        ans = 1
        for a in A:
            if a:
                ans *= a
                ans %= MOD
else:
    if K%2 == 0:
        Duet = []
        for n,p in enumerate(Plus):
            if n%2 == 0:
                cur = p
            else:
                Duet.append((cur*p , "Plus" ))
        for n,p in enumerate(Minus):
            if n%2 == 0:
                cur = p
            else:
                Duet.append((cur*p , "Minus" ))
        Duet.sort(reverse=True)
        ans = 1
        for i in range(K//2):
            ans *= Duet[i][0]
            ans %= MOD
    else:
        if len(Plus) > 0:
            Duet = []
            for n,p in enumerate(Plus):
                if n==len(Plus)-1:
                    break
                if n%2 == 0:
                    cur = p
                else:
                    Duet.append((cur*p , True ))
            for n,p in enumerate(Minus):
                if n%2 == 0:
                    cur = p
                else:
                    Duet.append((cur*p , False ))
            Duet.sort(reverse=True)
            ans = 1
            P = 0
            M = 0
            for i in range(K//2):
                ans *= Duet[i][0]
                ans %= MOD
                if Duet[i][1]:
                    P += 1
                else:
                    M += 1
            ans *= Plus[2*P]
            ans %= MOD
        else:
            for i in range(K):
                ans *= A[i]
                ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
N,K = [int(hoge) for hoge in input().split()]
A = [int(hoge) for hoge in input().split()]
#必然、マイナスの数は偶数個がいい
Plus = []
Minus = []
Zero = 0
for a in A:
    if a > 0:
        Plus.append(a)
    elif a < 0:
        Minus.append(-a)
    else:
        Zero += 1
Plus.sort(reverse=True)
Minus.sort(reverse=True)
Nonzero = N - Zero
ans = 1
#ノンゼロ<K...必ずゼロ
#ノンゼロ == K ...マイナスが偶数→全部掛け
#                 マイナスが奇数→ゼロがあればゼロ、なければ全部掛け
#ノンゼロ > K:
#   Kが偶数→2つずつペアにしてデカい順にかける
#   Kが奇数→2つずつペアにするが、プラスのラスト1つを存在しないものとして扱う。
#   余ったらプラスの最小のやつをかける
if Nonzero < K:
    ans = 0
elif Nonzero == K:
    if K%2 and Zero:
        ans = 0
    else:
        ans = 1
        for a in A:
            ans *= a
            ans %= MOD
else:
    if K%2 == 0:
        Duet = []
        for n,p in enumerate(Plus):
            if n%2 == 0:
                cur = p
            else:
                Duet.append((cur*p , "Plus" ))
        for n,p in enumerate(Minus):
            if n%2 == 0:
                cur = p
            else:
                Duet.append((cur*p , "Minus" ))
        Duet.sort(reverse=True)
        ans = 1
        for i in range(K//2):
            ans *= Duet[i][0]
            ans %= MOD
    else:
        if len(Plus) > 0:
            Duet = []
            for n,p in enumerate(Plus):
                if n==len(Plus)-1:
                    break
                if n%2 == 0:
                    cur = p
                else:
                    Duet.append((cur*p , True ))
            for n,p in enumerate(Minus):
                if n%2 == 0:
                    cur = p
                else:
                    Duet.append((cur*p , False ))
            Duet.sort(reverse=True)
            ans = 1
            P = 0
            M = 0
            for i in range(K//2):
                ans *= Duet[i][0]
                ans %= MOD
                if Duet[i][1]:
                    P += 1
                else:
                    M += 1
            ans *= Plus[2*P]
            ans %= MOD
        else:
            for i in range(K):
                ans *= A[i]
                ans %= MOD

print(ans)