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 time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools, copy, math
from bisect import *
from heapq import *
from collections import *


def lcm(a, b):  
    return (a*b)/gcd(a, b)

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()

######################################

N, K = In.ints()

MOD = 10**9+7

ans = 1
negs = []
pos = []

for el in In.ints():
    if el<0:
        negs.append(el)
    else:
        pos.append(el)

pos.sort()
negs.sort()

if (K%2!=0 and (K>len(pos) and K-len(pos) % 2 != 0)) or (K%2==0 and (K>len(pos) and K-len(pos)%2!=0 and len(negs)%2!=0 and K-len(pos)>=len(negs)-1)): 
    if 0 in pos:
        ans = 0
    else:
        ineg = len(negs)-1
        ipos = 0    
        while K>0:
            resNeg = negs[ineg] if ineg>=0 else 99999999999
            resPos = pos[ipos] if ipos<len(pos) else 99999999999
            
            if abs(resPos)<abs(resNeg):
                ans*=resPos

                ipos+=1
                K-=1        
            else:
                ans*=resNeg
                ineg-=1
                K-=1
            
            ans%=MOD
else:
    ineg = 0
    ipos = len(pos)-1

    while K>0:
        resNeg = -1
        resPos = -1

        if ineg<len(negs)-1:
            resNeg = negs[ineg]*negs[ineg+1]
        
        iposchoose = 0
        if ipos>=1 and pos[ipos]*pos[ipos-1] > pos[ipos]:            
            resPos = pos[ipos]*pos[ipos-1]
            iposchoose=2
        elif ipos>=0:
            resPos = pos[ipos]
        
        if resPos>resNeg:
            ans*=resPos

            if iposchoose==2:
                ipos-=2
                K-=2
            elif ipos>=0:
                ipos-=1
                K-=1            
        else:
            ans*=resNeg
            ineg+=2
            K-=2
        
        ans%=MOD

Out.int(ans)



######################################

if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Submission status: Wrong Answer

Solution code:
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools, copy, math
from bisect import *
from heapq import *
from collections import *


def lcm(a, b):  
    return (a*b)/gcd(a, b)

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()

######################################

N, K = In.ints()

MOD = 10**9+7

ans = 1
negs = []
pos = []

for el in In.ints():
    if el<0:
        negs.append(el)
    else:
        pos.append(el)

pos.sort()
negs.sort()

if K%2!=0 and (K>len(pos) and K-len(pos) % 2 != 0):
    if 0 in pos:
        ans = 0
    else:
        ineg = len(negs)-1
        ipos = 0    
        while K>0:
            resNeg = negs[ineg] if ineg>=0 else 99999999999
            resPos = pos[ipos] if ipos<len(pos) else 99999999999
            
            if abs(resPos)<abs(resNeg):
                ans*=resPos

                ipos+=1
                K-=1        
            else:
                ans*=resNeg
                ineg-=1
                K-=1
            
            ans%=MOD
else:
    ineg = 0
    ipos = len(pos)-1

    while K>0:
        resNeg = -1
        resPos = -1

        if ineg<len(negs)-1:
            resNeg = negs[ineg]*negs[ineg+1]
        
        iposchoose = 0
        if ipos>=1 and pos[ipos]*pos[ipos-1] > pos[ipos]:            
            resPos = pos[ipos]*pos[ipos-1]
            iposchoose=2
        elif ipos>=0:
            resPos = pos[ipos]
        
        if resPos>resNeg:
            ans*=resPos

            if iposchoose==2:
                ipos-=2
                K-=2
            elif ipos>=0:
                ipos-=1
                K-=1            
        else:
            ans*=resNeg
            ineg+=2
            K-=2
        
        ans%=MOD

Out.int(ans)



######################################

if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Submission status: Wrong Answer

Solution code:
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools, copy, math
from bisect import *
from heapq import *
from collections import *


def lcm(a, b):  
    return (a*b)/gcd(a, b)

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()

######################################

N, K = In.ints()

MOD = 10**9+7

ans = 1
negs = []
pos = []

for el in In.ints():
    if el<0:
        negs.append(el)
    else:
        pos.append(el)

pos.sort()
negs.sort()

validNegsCount = len(negs) if len(negs)%2==0 else len(negs)-1 

if K%2!=0 and (((K-len(pos)) % 2 != 0)):
    ineg = len(negs)-1
    ipos = 0    
    while K>0:
        resNeg = negs[ineg] if ineg>=0 else 99999999999
        resPos = pos[ipos] if ipos<len(pos) else 99999999999
        
        if resPos<resNeg:
            ans*=resPos

            ipos+=1
            K-=1        
        else:
            ans*=resNeg
            ineg-=1
            K-=1
        
        ans%=MOD
else:
    ineg = 0
    ipos = len(pos)-1

    while K>0:
        resNeg = -1
        resPos = -1

        if ineg<len(negs)-1:
            resNeg = negs[ineg]*negs[ineg+1]
        
        iposchoose = 0
        if ipos>=1 and pos[ipos]*pos[ipos-1] > pos[ipos]:            
            resPos = pos[ipos]*pos[ipos-1]
            iposchoose=2
        elif ipos>=0:
            resPos = pos[ipos]
        
        if resPos>resNeg:
            ans*=resPos

            if iposchoose==2:
                ipos-=2
                K-=2
            elif ipos>=0:
                ipos-=1
                K-=1            
        else:
            ans*=resNeg
            ineg+=2
            K-=2
        
        ans%=MOD

Out.int(ans)



######################################

if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Submission status: Wrong Answer

Solution code:
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools, copy, math
from bisect import *
from heapq import *
from collections import *


def lcm(a, b):  
    return (a*b)/gcd(a, b)

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()

######################################

N, K = In.ints()

MOD = 10**9+7

ans = 1
negs = []
pos = []

for el in In.ints():
    if el<0:
        negs.append(el)
    else:
        pos.append(el)

pos.sort()
negs.sort()

validNegsCount = len(negs) if len(negs)%2==0 else len(negs)-1 

if K%2!=0 and (((K-len(pos)) % 2 != 0)):
    ineg = len(negs)-1
    ipos = 0    
    while K>0:
        resNeg = negs[ineg] if ineg>=0 else 99999999999
        resPos = pos[ipos] if ipos<len(pos) else 99999999999
        
        if resPos<resNeg:
            ans*=resPos

            ipos+=1
            K-=1        
        else:
            ans*=resNeg
            ineg-=1
            K-=1
        
        ans%=MOD
else:
    ineg = 0
    ipos = len(pos)-1

    while K>0:
        resNeg = -1
        resPos = -1

        if ineg<len(negs)-1:
            resNeg = negs[ineg]*negs[ineg+1]
        
        if ipos>=1:
            resPos = pos[ipos]*pos[ipos-1]
        elif ipos>=0:
            resPos = pos[ipos]
        
        if resPos>resNeg:
            ans*=resPos

            if ipos>=1:
                ipos-=2
                K-=2
            elif ipos>=0:
                ipos-=1
                K-=1            
        else:
            ans*=resNeg
            ineg+=2
            K-=2
        
        ans%=MOD

Out.int(ans)



######################################

if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Submission status: Wrong Answer

Solution code:
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools, copy, math
from bisect import *
from heapq import *
from collections import *


def lcm(a, b):  
    return (a*b)/gcd(a, b)

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()

######################################

N, K = In.ints()
A = In.ints()

MOD = 10**9+7

ans = 1
negs = []
pos = []

for i in range(len(A)):
    if A[i]<0:
        negs.append(A[i])
    else:
        pos.append(A[i])

pos.sort()
negs.sort()

validNegsCount = len(negs) if len(negs)%2==0 else len(negs)-1 

if K>len(pos) + validNegsCount or K%2!=0 and len(pos)==0:
    #smallest possible
    while K>0:
        resNeg = negs[-1] if len(negs)>=1 else 9999999999999999
        resPos = pos[0] if len(pos)>=1 else 9999999999999999
        
        if resPos<resNeg:
            ans*=resPos

            pos.pop(0)
            K-=1        
        else:
            ans*=resNeg
            negs.pop(-1)
            K-=1
        
        ans%=MOD
else:
    #biggest possible
    while K>0:
        resNeg = -1
        resPos = -1

        if len(negs)>=2:
            resNeg = negs[0]*negs[1]
        
        if len(pos)>=2:
            resPos = pos[-1]*pos[-2]
        elif len(pos)>=1:
            resPos = pos[-1]
        
        if resPos>resNeg:
            ans*=resPos

            if len(pos)>=2:
                pos.pop(-1)
                pos.pop(-1)
                K-=2
            elif len(pos)>=1:
                pos.pop(-1)
                K-=1            
        else:
            ans*=resNeg
            negs.pop(0)
            negs.pop(0)
            K-=2
        
        ans%=MOD

Out.int(ans)



######################################

if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Submission status: Wrong Answer

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 = []
    for i in range(C//2):
      a_new.append(a_plus[2*i]*a_plus[2*i+1])
    for i in range(D//2):
      a_new.append(a_minus[2*i]*a_minus[2*i+1])
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)

Submission status: Wrong Answer

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 = []
    pos = 0
    neg = 0
    for i in range(n):
      if a[i] > 0 :
        a_plus.append(a[i])
        pos += 1
      else :
        a_minus.append(a[i])
        neg += 1
    a_plus.sort(reverse = True)
    a_minus.sort()
    a_plus_new = [a_plus[2*i]*a_plus[2*i+1] for i in range(pos//2)]
    a_minus_new = [a_minus[2*i]*a_minus[2*i+1] for i in range(neg//2)]
    a_new = a_plus_new + a_minus_new
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)

Submission status: Wrong Answer

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_plus_new = [a_plus[2*i]*a_plus[2*i+1] for i in range(C//2)]
    a_minus_new = [a_minus[2*i]*a_minus[2*i+1] for i in range(D//2)]
    a_new = a_plus_new + a_minus_new
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)

Submission status: Wrong Answer

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 = []
    for i in range(n):
      if a[i] > 0 :
        a_plus.append(a[i])
      else:
        a_minus.append(a[i])
    a_plus.sort(reverse = True)
    a_minus.sort()
    C = len(a_plus)
    D = n-C
    a_plus_new = [a_plus[2*i]*a_plus[2*i+1] for i in range(C//2)]
    a_minus_new = [a_minus[2*i]*a_minus[2*i+1] for i in range(D//2)]
    a_new = a_plus_new + a_minus_new
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)

Submission status: Wrong Answer

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 = []
    for i in range(n):
      if a[i] >= 0 :
        a_plus.append(a[i])
      else:
        a_minus.append(a[i])
    a_plus.sort(reverse = True)
    a_minus.sort()
    C = len(a_plus)
    D = n-C
    a_plus_new = [a_plus[2*i]*a_plus[2*i+1] for i in range(C//2)]
    a_minus_new = [a_minus[2*i]*a_minus[2*i+1] for i in range(D//2)]
    a_new = a_plus_new + a_minus_new
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)

Submission status: Wrong Answer

Solution code:
import heapq
import sys
import functools
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 = []
    for i in range(n):
      if a[i] >= 0 :
        a_plus.append(a[i])
      else:
        a_minus.append(a[i])
    a_plus.sort(reverse = True)
    a_minus.sort()
    C = len(a_plus)
    D = len(a_minus)
    a_plus_new = [a_plus[2*i]*a_plus[2*i+1] for i in range(C//2)]
    a_minus_new = [a_minus[2*i]*a_minus[2*i+1] for i in range(D//2)]
    a_new = a_plus_new + a_minus_new
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)

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()))
#-------------
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 = []
    for i in range(n):
      if a[i] >= 0 :
        a_plus.append(a[i])
      else:
        a_minus.append(a[i])
    a_plus.sort(reverse = True)
    a_minus.sort()
    a_plus_new = [a_plus[2*i]*a_plus[2*i+1] for i in range(len(a_plus)//2)]
    a_minus_new = [a_minus[2*i]*a_minus[2*i+1] for i in range(len(a_minus)//2)]
    a_new = a_plus_new + a_minus_new
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)

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()))
#-------------
a.sort(reverse = True)
w = 10**9 + 7
ans = 1
if k%2 == 1:
  for i in range(k):
    ans *= a[i]
  print(ans % w)

else:
  if n%2 == 0:
    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:
    a_plus = a[:k]
    a.sort()
    a_minus = a[:k]
    a_plus_new = [a_plus[2*i]*a_plus[2*i+1] for i in range(k//2)]
    a_minus_new = [a_minus[2*i]*a_minus[2*i+1] for i in range(k//2)]
    a_new = a_plus_new + a_minus_new
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)

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()))
#-------------
a.sort(reverse = True)
w = 10**9 + 7
ans = 1
if k%2 == 1:
  for i in range(k):
    ans *= a[i]
  print(ans % w)

else:
  if n%2 == 0:
    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:
    a_plus = heapq.nlargest(k, a)
    a_minus = heapq.nsmallest(k, a)
    a_plus.sort(reverse = True)
    a_minus.sort()
    a_plus_new = [a_plus[2*i]*a_plus[2*i+1] for i in range(len(a_plus)//2)]
    a_minus_new = [a_minus[2*i]*a_minus[2*i+1] for i in range(len(a_minus)//2)]
    a_new = a_plus_new + a_minus_new
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)

Submission status: Wrong Answer

Solution code:
from functools import reduce
MOD = 10**9 + 7
def mul(a, b):
    "Same as a * b."
    return (a * b)%MOD

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

nums.sort(reverse = True, key = lambda x: abs(x))
neg, pos = [], []

for i in nums:
    if i >= 0: pos.append(i)
    else: neg.append(i)

if k == n:
    print(reduce(mul, nums))

elif k%2 and len(pos) == 0:
    # negative answer
    print(reduce(mul, neg[-k:]))

else:
    # positive answer
    ans = reduce(mul, nums[:k])
    if ans >= 0: 
        print(ans)
    else:
        # The product of first k numbers is negative

        # Case1: remove the smallest negative element (in abs value) and ADD the largest non-negative element.

        # Case2: remove the smallest positive element and ADD the largest negative element (in abs value)

        arr = nums[:k][::-1]

        smallest_neg, smallest_pos = None, None

        for i in arr:
            if i >= 0: 
                smallest_pos = i
                break
        for i in arr:
            if i<0:
                smallest_neg = i
                break
        
        largest_pos, largest_neg = -10**9, 10**9
        for i in nums[k+1:]:
            if i >= 0:
                largest_pos = i
                break
        for i in nums[k+1:]:
            if i < 0:
                largest_neg = i
                break
        
        if largest_pos*smallest_neg <= largest_neg*smallest_pos:
            print((largest_pos*(ans//smallest_neg))%MOD)
        else:
            print((largest_neg*(ans//smallest_pos))%MOD)

Submission status: Wrong Answer

Solution code:
from functools import reduce
MOD = 10**9 + 7
def mul(a, b):
    "Same as a * b."
    return (a * b)%MOD

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

nums.sort(reverse = True, key = lambda x: abs(x))
neg, pos = [], []

for i in nums:
    if i >= 0: pos.append(i)
    else: neg.append(i)

if k == n:
    print(reduce(mul, nums))

elif k%2 and len(pos) == 0:
    # negative answer
    print(reduce(mul, neg[-k:]))

else:
    # positive answer
    ans = reduce(mul, nums[:k])
    if ans >= 0: 
        print(ans)
    else:
        # The product of first k numbers is negative

        # Case1: remove the smallest negative element (in abs value) and ADD the largest non-negative element.

        # Case2: remove the smallest positive element and ADD the largest negative element (in abs value)

        arr = nums[:k][::-1]

        smallest_neg, smallest_pos = None, None

        for i in arr:
            if i >= 0: 
                smallest_pos = i
                break
        for i in arr:
            if i<0:
                smallest_neg = i
                break
        
        largest_pos, largest_neg = None, None
        for i in nums[k+1:]:
            if i >= 0:
                largest_pos = i
                break
        for i in nums[k+1:]:
            if i < 0:
                largest_neg = i
                break
        
        case1, case2 = ans, ans
        if smallest_neg!= None and largest_pos!= None:
            case1 = largest_pos*(ans//smallest_neg)
        
        if smallest_pos!= None and largest_neg!= None:
            case2 = largest_neg*(ans//smallest_pos)
        
        print(max(case1, case2)%MOD)

Submission status: Wrong Answer

Solution code:
from functools import reduce
MOD = 10**9 + 7
def mul(a, b):
    "Same as a * b."
    return (a * b)%MOD

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

nums.sort(reverse = True, key = lambda x: abs(x))
neg, pos = [], []

for i in nums:
    if i >= 0: pos.append(i)
    else: neg.append(i)

if k == n:
    print(reduce(mul, nums))

elif k%2 and len(pos) == 0:
    # negative answer
    print(reduce(mul, neg[-k:]))

else:
    # positive answer
    ans = reduce(mul, nums[:k])
    if ans >= 0: 
        print(ans)
    else:
        # The product of first k numbers is negative

        # Case1: remove the smallest negative element (in abs value) and ADD the largest non-negative element.

        # Case2: remove the smallest positive element and ADD the largest negative element (in abs value)

        arr = nums[:k][::-1]

        smallest_neg, smallest_pos = None, None

        for i in arr:
            if i >= 0: 
                smallest_pos = i
                break
        for i in arr:
            if i<0:
                smallest_neg = i
                break
        
        largest_pos, largest_neg = None, None
        for i in nums[k+1:]:
            if i > 0:
                largest_pos = i
                break
        for i in nums[k+1:]:
            if i < 0:
                largest_neg = i
                break
        
        case1, case2 = ans, ans
        if smallest_neg!= None and largest_pos!= None:
            case1 = largest_pos*(ans//smallest_neg)
        
        if smallest_pos!= None and largest_neg!= None:
            case2 = largest_neg*(ans//smallest_pos)
        
        print(max(case1, case2)%MOD)

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *

mod = 10**9+7

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
l = bisect_left(A, 0)
r = bisect_right(A, 0)
if N-r+l < K:
    print(0)
    exit()
b = A[:l]
c = A[r:][::-1]
if len(b) + len(c) == K:
    ans = 1
    for _b in b:
        ans = ans * _b % mod
    for _c in c:
        ans = ans * _c % mod
    print(ans)
    exit()
if K % 2 and len(c) == 0:
    if r-l > 0:
        print(0)
    else:
        ans = 1
        for i in range(K):
            ans = ans * b[-1-i] % mod
        print(ans)
    exit()
n = [1]*(len(b)+1)
for i in range(len(b)):
    n[i+1] = n[i] * b[i] % mod
p = [1]*(len(c)+1)
for i in range(len(c)):
    p[i+1] = p[i] * c[i] % mod
ans = -float('inf') if K > 1 else c[0]
for i in range(0, K+1, 2):
    if i <= len(b) and K-i <= len(c):
        ans = max(ans, n[i] * p[K-i] % mod)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
A = sorted(A, key=lambda x: abs(x), reverse=True)
signs = [int(a < 0) for a in A]

if N == K :
  select = A
### Aがすべて負なら大きいほうから選択する
elif sum(signs) == N :
  select = A[-K:]
else :
  ### 基本絶対値の大きいほうから選択する
  ### 負の数が奇数個になるなら、一番絶対値の小さい数を
  ### それと違う符号の数に入れかえる
  if sum(signs[:K]) % 2 == 1 :
    if sum(signs[:K]) == sum(signs) :
      select = A[:K]
      for i in range(0, K) :
        if signs[K-i-1] == 1 :
          select.pop(K-i-1)
          break
      s = 1
    else :
      select = A[:K-1]
      s = signs[K-1]
    for i in range(K, N) :
      if signs[i] != s :
        select.append(A[i])
        break
  else :
    select = A[:K]

ans = 1
for i in select :
  ans = (ans * i) % int(10**9+7)
print(ans)