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:
#!/usr/bin/env python3
import sys
from functools import total_ordering

MOD = 1000000007  # type: int


def solve(N: int, K: int, A: "List[int]"):
    B = [Num(A[i]) for i in range(N)]
    B.sort(reverse=True)
    sign = 1
    ret = 1
    if N == 1:
        print(B[0].getNum() % MOD)
        return
    for i in range(K):
        sign *= B[i].getSign()
        ret *= B[i].getNum() % MOD
        ret %= MOD
    if sign > 0:
        print(ret)
        return
    elif sign < 0:
        minP = -1
        minP_i = 0
        minM = 1
        minM_i = 0
        for i in range(K - 1, -1, -1):
            if B[i].getSign() > 0:
                minP = B[i].getNum()
                minP_i = i
                break
        # else:
        #     minP = 10 ** 10
        for i in range(K - 1, -1, -1):
            if B[i].getSign() < 0:
                minM = B[i].getNum()
                minM_i = i
                break
        # else:
        #     minM = 10 ** 10
        maxP = -1
        maxP_i = 0
        maxM = 1
        maxM_i = 0
        for i in range(K, N):
            if B[i].getSign() > 0:
                maxP = B[i].getNum()
                maxP_i = i
                break
        # else:
        #     maxP = 0
        for i in range(K, N):
            if B[i].getSign() < 0:
                maxM = B[i].getNum()
                maxM_i = i
                break
        # else:
        #     maxM = 0
        if minP > 0 and minM < 0 and maxP > 0 and maxM < 0:
            x = abs(maxM) / abs(minP)   
            y = abs(maxP) / abs(minM)
            ret_new = 1
            if x > y:
                for i in range(K):
                    if i != minP_i:
                        ret_new *= B[i].getNum() % MOD
                        ret_new %= MOD
                ret_new *= B[maxM_i].getNum() % MOD
                ret_new %= MOD
            else:
                for i in range(K):
                    if i != minM_i:
                        ret_new *= B[i].getNum() % MOD
                        ret_new %= MOD
                ret_new *= B[maxP_i].getNum() % MOD
                ret_new %= MOD
            print(ret_new)
        else:
            if minP < 0:
                # minMの交換を行う
                if maxP > 0:
                    # 行う
                    ret_new = 1
                    for i in range(K):
                        if i != minM_i:
                            ret_new *= B[i].getNum() % MOD
                            ret_new %= MOD
                    ret_new *= B[maxP_i].getNum() % MOD
                    ret_new %= MOD
                    print(ret_new)
                    return
                else:
                    # 行えない
                    # 絶対値が最小のものが答え
                    ret_new = 1
                    for i in range(N - 1, N - K - 1, -1):
                        ret_new *= B[i].getNum() % MOD
                        ret_new %= MOD
                    print(ret_new)
                    return
            else:
                if maxP > 0:
                    # maxMが存在しない
                    # minMを交換
                    ret_new = 1
                    for i in range(K):
                        if i != minM_i:
                            ret_new *= B[i].getNum() % MOD
                            ret_new %= MOD
                    ret_new *= B[maxP_i].getNum() % MOD
                    ret_new %= MOD
                    print(ret_new)
                    return
                elif maxM < 0:
                    # maxPだけ存在しない
                    # minPを交換
                    ret_new = 1
                    for i in range(K):
                        if i != minP_i:
                            ret_new *= B[i].getNum() % MOD
                            ret_new %= MOD
                    ret_new *= B[maxM_i].getNum() % MOD
                    ret_new %= MOD
                    print(ret_new)
                    return
                else:
                    # maxPもmaxMも存在しない
                    # そのまま
                    print(ret)
                    return
    else:
        print(0)
        return


@total_ordering
class Num:
    def __init__(self, num):
        self.num = num
        self.sign = (num > 0) - (num < 0)
    
    def __eq__(self, value):
        return abs(self.num) == abs(value.num)
    
    def __lt__(self, value):
        return abs(self.num) < abs(value.num)

    def getNum(self):
        return self.num

    def getSign(self):
        return self.sign

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N,K = LMIIS()
    A = LMIIS()
    positive = []
    negative = []
    for a in A:
        if a >= 0:
            positive.append(a)
        else:
            negative.append(a)
    positive.sort(reverse=True)
    negative.sort()
    ans = 1
    num_used = 0
    if len(positive) >= K:
        if len(positive) >= 2:
            comp = positive[0] * positive[1]
        else:
            comp = positive[0]
        for i in range(0,min(len(negative),K//2),2):
            if negative[i] * negative[i+1] >= comp:
                ans = ans * negative[i] * negative[i+1] % P
                num_used += 2
            else:
                break
        for i in range(K-num_used):
            ans = ans * positive[i] % P
            num_used += 1
        print(ans)
        return
    else:
        need = K - len(positive)
        dbg(need,positive,negative)
        #答えを正にできる
        if need%2 == 0:
            ans = 1
            for a in positive:
                ans = ans * a % P
            for i in range(0,need,2):
                ans = ans * negative[i] * negative[i+1] % P
                dbg(i,negative[i],negative[i+1],ans)
            # for i in range(K-need):
            #     ans = ans * positive[i] % P
            #     dbg(positive[i],ans)
            print(ans)
            return

        #答えが負
        else:
            ans = 1
            for a in positive:
                ans = ans * a % P
            negative = negative[::-1]
            for i in range(K-len(positive)):
                ans = ans * negative[i] % P
            print(ans)
            return
                



    
main()

Submission status: Wrong Answer

Solution code:
import bisect
N ,K = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
mod = 10 ** 9 + 7
# ans = 0
if A.count(0) > (N - K):
  print(0)
  quit()
  
# ans = minus
plus = bisect.bisect_right(A, 0)
minus = bisect.bisect_left(A, 0) 
if N == K:
  ans = 1
  for i in range(N):
    ans *= A[i]
    ans %= mod
  print(ans % mod)
  quit()
  
if minus == N:
  ans = 1
  for i in range(1, K + 1):
    ans *= A[-i]
    ans %= mod
  print(ans % mod)
  quit()
  
ans = 1

count = 0
i = 0
j = -1
while count < K:
  if K - count >= 2:
    fo = A[i] * A[i + 1]
    re = A[j] * A[j - 1]
    #print(fo, re)
    if fo >= re:
      ans *= (fo % mod) 
      ans %= mod
      i += 2
    elif (A[j - 1] < 1) or (A[j - 2] < 1):
      if (K % 2 == 0):
        ans *= (re % mod)
        ans %= mod
        j -= 2
      else:  
        ans *= (fo % mod) 
        ans %= mod
        i += 2      
    else:
      ans *= (re % mod)
      ans %= mod
      j -= 2
    count += 2  
  else:
    count += 1
    ans *= A[j]
      
  #print(ans)
print(ans % mod)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

NEGA = 0
POSI = 1
EVEN = 0
ODD = 1
MOD = 10**9 + 7

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    b = []
    for i_a in a:
        if i_a < 0:
            b.append((abs(i_a), NEGA))
        else:
            b.append((i_a, POSI))
    b.sort(reverse=True)

    e_or_o = 0
    pool_nega_num = None
    pool_posi_num = None
    add_num = 0
    ans = 1
    for i_num, i_n_or_p in b:
        if i_n_or_p == NEGA:
            e_or_o += 1

            if e_or_o % 2 == 1 and add_num +1 == k:
                ans *= i_num
                ans %= MOD
                add_num += 1
                break

            if e_or_o % 2 == 0:
                if add_num + 1 == k:
                    if pool_posi_num is None:
                        ans *= i_num * pool_nega_num
                    else:
                        ans = ans * i_num * pool_nega_num // pool_posi_num
                    ans %= MOD
                    add_num += 1
                else:
                    ans *= i_num * pool_nega_num
                    ans %= MOD
                    add_num += 2
            else:
                pool_nega_num = i_num
        
        else:
            ans *= i_num
            ans %= MOD
            add_num += 1
            pool_posi_num = i_num

        if add_num == k:
            break

    if e_or_o % 2 == 1:
        ans *= -1
        ans %= MOD
    print(ans)
    return


if __name__ == "__main__":
    main()
    sys.exit(0)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
import copy
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)


n, k = map(int, input().split())
A = list(map(int, input().split()))
pos = []
neg = []
for i in range(n):
    if A[i] < 0:
        neg.append(A[i])
    elif A[i] > 0:
        pos.append(-A[i])

if len(pos) + len(neg) < k:
    print(0)
    exit()

if n == k:
    ans = 1
    for i in range(n):
        ans = (ans * A[i]) % MOD
    print(ans)
    exit()

pos.sort()
neg.sort()
# print(pos, neg)

if len(pos) == 0:
    if k%2 == 1:
        if n - (len(pos) + len(neg)) > 0:
            print(0)
            exit()
        ans = 1
        for i in range(1, k+1):
            ans = (ans * neg[-i]) % MOD
        print(ans)
        exit()
    else:
        ans = 1
        for i in range(k):
            ans = (ans * neg[i]) % MOD
        print(ans)
        exit()

elif len(neg) == 0:
    ans = 1
    for i in range(k):
        ans = (ans * -pos[i]) % MOD
    print(ans)
    exit()

else:
    mix = pos + neg
    mix.sort()
    val = mix[k-1]
    pos_idx = bisect.bisect(pos, val) - 1
    neg_idx = bisect.bisect(neg, val) - 1
    pos_idx2 = bisect.bisect_left(pos, val) - 1
    neg_idx2 = bisect.bisect_left(neg, val) - 1
    # print(pos_idx, neg_idx, pos_idx2, neg_idx2)
    if pos_idx + neg_idx + 2 > k:
        rem = k-2-pos_idx2-neg_idx2
        if neg_idx2%2 == 0 and neg_idx2 < neg_idx:
            neg_idx2 += 1
            rem -= 1
        while neg_idx2+1 < neg_idx and rem >= 2:
            neg_idx2 += 2
            rem -= 2
        while rem >= 1:
            pos_idx2 += 1
            rem -= 1
        pos_idx = pos_idx2
        neg_idx = neg_idx2

    # print(pos_idx, neg_idx)

    if neg_idx % 2 == 0:
        if neg_idx == len(neg)-1 and pos_idx == len(pos)-1:
            print(0)
            exit()
        elif neg_idx == len(neg)-1:
            neg_idx -= 1
            pos_idx += 1
        elif pos_idx == len(pos)-1:
            neg_idx += 1
            pos_idx -= 1
        else:
            if neg[neg_idx+1] >= pos[pos_idx+1]:
                neg_idx -= 1
                pos_idx += 1
            else:
                neg_idx += 1
                pos_idx -= 1

    # print(pos_idx, neg_idx)
    ans = 1
    for i in range(pos_idx+1):
        ans = (ans * -pos[i]) % MOD
    for i in range(neg_idx + 1):
        ans = (ans * neg[i]) % MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
MOD=10**9+7

def futuuni(List,mi=False):
  res=1
  for i in range(K):
    dat=List[i]
    if mi:
      dat = -dat
    if dat<0:
      dat+=MOD
    res*=(dat%MOD)
    res%=MOD
  print(res)
  exit() 

plus=[]
minas=[]
zero=0
A=list(map(int,input().split()))
for a in A:
  if a>0:
    plus.append(a)
  elif a<0:
    minas.append(a)
  else:
    zero+=1
plus.sort(reverse=True)
minas.sort()
lp=len(plus)
lm=len(minas)
if lp+lm<K:
  print(0)
#膨大な例外処理
if N==K:
  futuuni(A)
if lp+lm<K:
  print(0)
  exit()
if lp==0:
  if K%2==0:
    futuuni(minas)
  else:
    if zero>0:
      print(0)
      exit()
    minas.sort(reverse=True)
    futuuni(minas)
if lm==0:
  futuuni(plus)
#例外処理ここまで

if K%2==0:
  pp=[plus[i]*plus[i-1] for i in range(1,lp,2)]
else:
  pp=[plus[i]*plus[i-1] for i in range(2,lp,2)]
mm=[minas[i]*minas[i-1] for i in range(1,lm,2)]
allpp=len(pp)
allpp_m=K//2-allpp
if K//2<=len(pp):
  allpp=K//2
  allpp_m=0


  
ind=allpp

for i in range(allpp):
  if pp[allpp-1-i]>mm[allpp_m+i]:
    ind=i
    break
  if allpp_m+i+1==len(mm):
    ind=i
    break  
ans=1
if K%2==1:
  ans*=plus[0]

for i in range(allpp_m+ind):
  ans*=(mm[i]%MOD)
  ans%=MOD
for i in range(allpp-ind):
  ans*=(pp[i]%MOD)
  ans%=MOD
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
arr = [int(x) for x in input().split()]
 
mod = 10**9 + 7
 
def solve(A, n, k): 
    mod = 10**9 + 7
  
    # sorting given input array 
    A.sort() 
    product = 1
  
    if (A[n - 1] == 0 and (k & 1)): 
        return 0
  
    if (A[n - 1] <= 0 and (k & 1)) : 
        for i in range(n - 1, n - k - 1, -1): 
            # print(i,A[i])
            product *= (A[i] % mod) 
        return product % mod
    i = 0 
    j = n - 1 
    if (k & 1): 
        product *= (A[j] % mod)
        j-= 1
        k-=1 
    k >>= 1
    for itr in range(k) :
        left_product = (A[i]%mod) * (A[i + 1]&mod)
        right_product = (A[j]%mod) * (A[j - 1]%mod)
        if (left_product > right_product) : 
            product *= (left_product % mod)
            i += 2
        else : 
            product *= (right_product % mod)
            j -= 2
    return product % mod
print(solve(arr, n, k) % mod)

Submission status: Wrong Answer

Solution code:
# Author : raj1307 - Raj Singh
# Date   : 05.07.2020

from __future__ import division, print_function

import os,sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def ii():  return int(input())
def si():  return input()
def mi():  return map(int,input().strip().split(" "))
def msi(): return map(str,input().strip().split(" "))
def li():  return list(mi())

def dmain():
    sys.setrecursionlimit(1000000)
    threading.stack_size(1024000)
    thread = threading.Thread(target=main)
    thread.start()
    
#from collections import deque, Counter, OrderedDict,defaultdict
#from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace
#from math import log,sqrt,factorial,cos,tan,sin,radians
#from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
#from decimal import *
#import threading
#from itertools import permutations
#Copy 2D list  m = [x[:] for x in mark] .. Avoid Using Deepcopy

abc='abcdefghijklmnopqrstuvwxyz'
abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod=1000000007
#mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]
def getKey(item): return item[1] 
def sort2(l):return sorted(l, key=getKey,reverse=True)
def d2(n,m,num):return [[num for x in range(m)] for y in range(n)]
def isPowerOfTwo (x): return (x and (not(x & (x - 1))) )
def decimalToBinary(n): return bin(n).replace("0b","")
def ntl(n):return [int(i) for i in str(n)]
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))

def ceil(x,y):
    if x%y==0:
        return x//y
    else:
        return x//y+1

def powerMod(x,y,p):
    res = 1
    x %= p
    while y > 0:
        if y&1:
            res = (res*x)%p
        y = y>>1
        x = (x*x)%p
    return res

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x
    
def isPrime(n) : # Check Prime Number or not 
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
    return True



def read():
    sys.stdin  = open('input.txt', 'r')  
    sys.stdout = open('output.txt', 'w') 




def main():
    


    #for _ in range(ii()):


    n,k=mi()
    a=li()
    if n==k:
        ans=1
        for i in range(n):

            x=(a[i]%mod+mod)%mod;
            ans=(ans*x)%mod
        print(ans)
        return


    x=[]
    y=[]

    for i in range(n):
        if a[i]<0:
            y.append(a[i])
        else:
            x.append([a[i],1])

    neg=[]


    y.sort()
    ex=-1

    for i in range(0,len(y),2):
        if i==len(y)-1:
            ex=y[i]
            continue

        x.append([y[i]*y[i+1],2])



    x.sort(reverse=True)
   


    ans=1
    cnt=0


    p=[]
    q=[]

    ext=-1


    for i in range(len(x)):
        #print(cnt,x[i][1],cnt)


        if cnt+x[i][1]<=k:

            if x[i][1]==1:
                p.append(x[i][0])
            else:
                q.append(x[i][0])

            ans=(ans*x[i][0])%mod
            cnt+=x[i][1]

        elif cnt!=k:

            ext=max(ext,x[i][0])



    if cnt==k:
        print(ans)
        return



    if len(p)!=0:

        ans=1

        for i in range(len(p)-1):
            ans=(ans*p[i])%mod
        for j in range(len(q)):
            ans=(ans*q[j])%mod
        ans=ans*ext
        ans%=mod
        print(ans)
        return


    mm=[]
    y=y[::-1]
    for i in range(0,len(y),2):
        if i==len(y)-1:
            break

        mm.append([y[i]*y[i+1],2])

    for i in range(n):
        if a[i]>=0:
            mm.append([a[i],1])

    cnt=0
    mm.sort()

    ans=1
    for i in range(len(mm)):


         if cnt+mm[i][1]<=k:


            ans=(ans*mm[i][0])%mod
            cnt+=mm[i][1]

    


    if cnt==k:
        print(ans)
        return












    ans=1
    cnt=0
    for i in range(len(y)-1,-1,-1):
        if cnt==k:
            break

        x=(mod+y[i]%mod)%mod
        ans*=x
        ans%=mod
        cnt+=1

    print(ans)












    









    








# region fastio
# template taken from https://github.com/cheran-senthil/PyRival/blob/master/templates/template.py

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion


if __name__ == "__main__":
    #read()
    main()
    #dmain()

# Comment Read()

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import operator

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

pos = [a for a in A if a > 0]
neg = [a for a in A if a < 0]
LP = len(pos)
LN = len(neg)
zer = N - LP - LN

MOD = 10 ** 9 + 7


def solve():
    global N, K, pos, neg, LP, LN, zer, MOD
    # ZERO
    if LP + LN < K:
        return 0

    # 全部使い切るとき
    if LP + LN == K:
        ans = 1
        for n in pos:
            ans *= n
            ans %= MOD
        for n in neg:
            ans *= n
            ans %= MOD
        return ans

    # negative にしかならない
    # 正がなくて、負の数を奇数回使う
    if LP == 0 and K % 2 == 1:
        if zer > 0:
            return 0
        else:
            neg.sort(reverse=True)
            ans = 1
            for n in neg:
                ans *= n
                ans %= MOD

            return ans

    # positiveにできるなら
    # 2個ずつ比較
    pos.sort()
    neg.sort(reverse=True)

    ans = 1

    while K > 0 and len(neg) >= 2 and len(pos) >= 2:
        # 2個を比べる
        p = pos[-1] * pos[-2]
        n = neg[-1] * neg[-2]

        if n >= p:
            neg.pop()
            neg.pop()

            ans *= n
            ans %= MOD
            K -= 2
        else:
            ans *= pos[-1]
            ans %= MOD
            pos.pop()

            K -= 1

    # あとK個使う必要がある
    if K > 0:
        # negが1個以下
        if len(neg) <= 1:
            # posから取る
            for p in pos:
                ans *= p
                ans %= MOD
                K -= 1
                if K == 0:
                    break
        # posが1個以下
        else:
            while K >= 2:
                ans *= neg[-1]
                ans %= MOD
                ans *= neg[-2]
                ans %= MOD
                K -= 2
                neg.pop()
                neg.pop()

            if K == 1:
                ans *= pos[-1]
                ans %= MOD

    return ans


print(solve())

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
arr = list(map(int, input().split()))
mod = 10**9 + 7
def maxProductFinderK(sequence, K):
    absolute = []
    list2 = sorted(sequence)
    neg_count = 0
    for x in range(1, K+1):
      if abs(list2[0]) > list2[len(list2)-1]:
        absolute.append(list2[0])
        list2.pop(0)
        neg_count = neg_count + 1
      else:
        absolute.append(list2[len(list2)-1])
        list2.pop(len(list2) - 1)
    if neg_count % 2 != 0 and len(list2) != 0:
        absolute = sorted(absolute)
        absolute.pop(neg_count - 1)
        absolute.append(list2[len(list2)-1])
    b = 1
    if K == 0:
      b = 0
    for y in absolute:
      b = b * y
      d = 1
        
    return b % mod
print(maxProductFinderK(arr, k))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

MOD = 10**9+7


def main(input, print):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    nc = 0
    for i in range(n):
        if a[i] < 0:
            nc += 1
    negative = 0
    cnt = 0
    ans = 1
    a = sorted(a, key=abs, reverse=True)
    y = 0
    for i in range(n):
        if k == cnt:
            break
        if a[i] < 0:
            if negative % 2 == 1:
                ans = ans * y * a[i] % MOD
                cnt += 2
            else:
                y = a[i]
            negative += 1
        else:
            ans = ans * a[i] % MOD
            cnt += 1
    if cnt == k:
        print(ans)
        return
    ans = 1
    a = sorted(a, key=abs)
    y = 0
    for i in range(k):
        ans = ans * a[i] % MOD

    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, k = map(int, input().split())
a = list( map(int, input().split()))
p = 10**9+7

a.sort()

from bisect import bisect_left, bisect_right
zerostart = bisect_left(a, 0)
posstart = bisect_right(a, 0)

aneg = a[:zerostart]
cntzero = posstart - zerostart
apos = a[posstart:]

cntneg = len(aneg)
cntpos = len(apos)

# 答えが0になる時
if k > n-cntzero:
    print(0)
    exit()

cntneg = len(aneg)
cntpos = len(apos)

mix = [(-neg,-1) for neg in aneg] + [(pos,1) for pos in apos]
mix.sort(key=lambda x:x[0],reverse=True)


# 答えが正になる時
if k <= cntpos or (k%2==0 and  k <= (cntneg//2)*2 + cntpos) or (k%2==1 and cntpos%2==1 and k <= (cntneg//2)*2 + cntpos-1):
    pos_pair_mix=[]
    apos.sort(reverse=True)
    for i in range(cntpos//2):
        pos_pair_mix.append((apos[2*i]*apos[2*i+1],+1,i))

    for i in range(cntneg//2):
        pos_pair_mix.append((aneg[2*i]*aneg[2*i+1],-1,i))

    pos_pair_mix.sort(key=lambda x:x[0],reverse=True)

    ans = 1
    last_apos=0

    for i in range(k//2):
        ans*=pos_pair_mix[i][0]%p
        ans%=p
        if pos_pair_mix[i][1]==1:
            last_apos = pos_pair_mix[i][2]+1
    if k%2==0:
        print(ans%p)
        exit()
    else:
        print((ans*apos[last_apos])%p)
        exit()

# 答えが負になる時
mix = [(neg,-neg,-1) for neg in aneg] + [(pos,1) for pos in apos]
mix.sort(key=lambda x:x[1])

ans = 1
for i in range(k-cntzero):
    ans*=mix[i][0]
    ans%=p

if ans <0 and cntzero>0:
    ans = 0

print(ans%p)

Submission status: Wrong Answer

Solution code:
import bisect
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
mod = 10**9 + 7
ans = 1
pluses = bisect.bisect_left(a, 0)
minuses = n-pluses
if a[-1] < 0 and k%2 == 1:
	for i in range(k):
		ans = ans * a[-i-1] % mod
elif a[-1] < 0 and k%2 == 0:
	for i in range(k):
		ans = ans * a[i] % mod
elif a[0] >= 0:
	for i in range(k):
		ans = ans * a[i] % mod
elif k%2 == 0:
	righttmp = n-1
	lefttmp = 0
	rightmode = 1
	leftmode = 1
	minusmode = 0
	mode = 0
	for i in range(k//2):
		if lefttmp < n-1:
			if a[lefttmp] >= 0 or a[lefttmp+1] >= 0:
				leftmode = 0
		else:
			leftmode = 0
		if righttmp > 0:
			if a[righttmp] < 0 or a[righttmp-1] < 0:
				rightmode = 0
		else:
			rightmode = 0
		if rightmode:
			if leftmode:
				tmp = -10**27
				righttmptmp = 0
				lefttmptmp = 0
				if a[righttmp]*a[righttmp-1] > tmp:
					lefttmptmp = lefttmp
					righttmptmp = righttmp-2
					tmp = a[righttmp]*a[righttmp-1]
				if a[lefttmp]*a[lefttmp+1] > tmp:
					lefttmptmp = lefttmp+2
					righttmptmp = righttmp
					tmp = a[lefttmp]*a[lefttmp+1]
				ans = ans*tmp%mod
				righttmp, lefttmp = righttmptmp, lefttmptmp
			else:
				ans = ans*a[righttmp]*a[righttmp-1]%mod
				righttmp = righttmp-2
else:
	righttmp = n-1
	lefttmp = 0
	rightmode = 1
	leftmode = 1
	minusmode = 0
	mode = 0
	for i in range(k//2):
		if lefttmp < n-1:
			if a[lefttmp] >= 0 or a[lefttmp+1] >= 0:
				leftmode = 0
		else:
			leftmode = 0
		if righttmp > 0:
			if a[righttmp] < 0 or a[righttmp-1] < 0:
				rightmode = 0
		else:
			rightmode = 0
		if rightmode:
			if leftmode:
				tmp = -10**27
				righttmptmp = 0
				lefttmptmp = 0
				if a[righttmp]*a[righttmp-1] > tmp:
					lefttmptmp = lefttmp
					righttmptmp = righttmp-2
					tmp = a[righttmp]*a[righttmp-1]
				if a[lefttmp]*a[lefttmp+1] > tmp:
					lefttmptmp = lefttmp+2
					righttmptmp = righttmp
					tmp = a[lefttmp]*a[lefttmp+1]
				ans = ans*tmp%mod
				righttmp, lefttmp = righttmptmp, lefttmptmp
			else:
				ans = ans*a[righttmp]*a[righttmp-1]%mod
				righttmp = righttmp-2
	ans = ans * a[righttmp] % mod
print(ans % mod)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
N, K = map(int,input().split())
A = list(map(int,input().split()))

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

plus.sort(reverse = True)
minus.sort() #絶対値の大きい順
Lp = len(plus)
Lm = len(minus)
idx_p = 0
idx_m = 0


MOD = 10**9+7

if K>Lp and (K-Lp)&1: #必ずマイナス
    A.sort(key = lambda x:abs(x))
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans = (ans + MOD)%MOD
    print(ans)
    sys.exit()


# 2個ずつ見る
Ks = 0
ans = 1
while Ks<K:
    if Ks+1==K:
        if idx_p<Lp:
            ans *= plus[idx_p]
            ans %= MOD
        else:
            ans *= minus[-1]
            ans += MOD
            ans %= MOD
        break
    
    if idx_p<Lp-1 and idx_m<Lm-1:
        if plus[idx_p]*plus[idx_p+1]>minus[idx_m]*minus[idx_m+1]:
            ans *= plus[idx_p] * plus[idx_p+1]
            ans %= MOD
            idx_p += 2
        else:
            ans *= minus[idx_m] * minus[idx_m+1]
            ans %= MOD
            idx_m += 2
        Ks += 2
    elif idx_m<Lm-1:
        ans *= minus[idx_m]*minus[idx_m+1]
        ans %= MOD
        idx_m += 2
        Ks += 2
    elif idx_p<Lp-1:
        ans *= plus[idx_p] * plus[idx_p+1]
        ans %= MOD
        idx_p += 2
        Ks += 2

print((ans+MOD)%MOD)