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: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n,k = m()

a = l()

a.sort()

mina = []

pra = []

for i in range(len(a)):
	if a[i] >= 0:
		pra.append(a[i])
	else:
		mina.append(a[i])

lp = len(pra)

lm = len(mina)
ans = 1
if lp == 0:
	if k % 2 != 0:
		for i in range(0,k,2):
			if i == k-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		for i in range(0,k,2):
			ans *= (mina[i]*mina[i+1]) % mod
			ans %= mod
		print(ans % mod)
elif lp == 1:
	if n == k:
		ans *= pra[0]
		for i in range(0,lm,2):
			if i == lm-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		if k % 2 == 0:
			for i in range(0,k,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
		else:
			ans *= pra[0] 
			for i in range(0,k-1,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
else:
	cp = lp-1
	cm = 0
	
	for _ in range(k):
		if cp != -1 and cm != lm:
			if abs(mina[cm]) <= pra[cp]:
				if cp == 0:
					if (k-lp) % 2 == 0:
						cp -= 1
					else:
						cm += 1
				else:
					cp -= 1
			else:
				if cm == lm-1:
					if lm % 2 == 0:
						cm += 1
					else:
						cp -= 1
				else:
					
					cm += 1
		elif cp != -1:
			cp -= 1
		elif cm != lm:
			cm += 1
			
		else:
			break
	if cm % 2 != 0:
		if cp == lp-1:
			cp -= 1
			cm -= 1

		else:
			if cp != -1 and cm != lm:
				if pra[cp]*pra[cp+1] <= -mina[cm]*-mina[cm-1]:
					cp += 1
					cm += 1
				else:
					cp -= 1
					cm -= 1
			elif cp != -1:
				cp -= 1
				cm -= 1
			elif cm != lm:
				cp += 1
				cm += 1

	ii = -2
	for i in range(0,cm,2):
		if i == cm-1:
			ii = i
			continue
		ans *= (mina[i] * mina[i+1]) % mod
		ans %= mod
	for i in range(lp-1,cp,-1):
		ans *= pra[i] % mod
		ans %= mod
	if ii == cm-1:
		ans *= mina[ii]
		ans %= mod

		
	print(ans)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n,k = m()

a = l()

a.sort()

mina = []

pra = []

for i in range(len(a)):
	if a[i] >= 0:
		pra.append(a[i])
	else:
		mina.append(a[i])

lp = len(pra)

lm = len(mina)
ans = 1
if lp == 0:
	if k % 2 != 0:
		for i in range(0,k,2):
			if i == k-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		for i in range(0,k,2):
			ans *= (mina[i]*mina[i+1]) % mod
			ans %= mod
		print(ans % mod)
elif lp == 1:
	if n == k:
		ans *= pra[0]
		for i in range(0,lm,2):
			if i == lm-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		if k % 2 == 0:
			for i in range(0,k,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
		else:
			ans *= pra[0] 
			for i in range(0,k-1,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
else:
	cp = lp-1
	cm = 0
	
	for _ in range(k):
		if cp != -1 and cm != lm:
			if abs(mina[cm]) <= pra[cp]:
				if cp == 0:
					if (k-lp) % 2 == 0:
						cp -= 1
					else:
						cm += 1
				else:
					cp -= 1
			else:
				if cm == lm-1:
					if lm % 2 == 0:
						cm += 1
					else:
						cp -= 1
				else:
					
					cm += 1
		elif cp != -1:
			cp -= 1
		elif cm != lm:
			cm += 1
			
		else:
			break
	if cm % 2 != 0:
		if cp == lp-1:
			cp -= 1
			cm -= 1

		else:
			if cp != -1 and cm != lm:
				if pra[cp+1] == 0: 
					cp += 1
					cm += 1
				elif pra[cp]*pra[cp+1] <= -mina[cm]*-mina[cm-1]:
					cp += 1
					cm += 1
				else:
					cp -= 1
					cm -= 1
			elif cp != -1:
				cp -= 1
				cm -= 1
			elif cm != lm:
				cp += 1
				cm += 1

	ii = -2
	for i in range(0,cm,2):
		if i == cm-1:
			ii = i
			continue
		ans *= (mina[i] * mina[i+1]) % mod
		ans %= mod
	for i in range(lp-1,cp,-1):
		ans *= pra[i] % mod
		ans %= mod
	if ii == cm-1:
		ans *= mina[ii]
		ans %= mod

		
	print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N, K = map(int, input().split())
A = list(map(int, input().split()))
M = 10**9 + 7

def prod(X):
    ans = 1
    for x in X:
        ans = ans * x % M
    return ans

def solve():
    # Case 1: N == K
    if N == K:
        return prod(A)

    # Case 2: ans is negative
    if all(a < 0 for a in A) and K % 2 == 1:
        return prod(sorted(A)[-K:])

    # Case 3: ans is positive
    posA = np.int64(sorted([a for a in A if a >= 0]))
    negA = np.int64(sorted([a for a in A if a < 0]))

    ans = 1
    if K % 2 == 1: # Keep the largest positive
        ans = ans * posA[-1] % M
        posA = posA[:-1]
    
    # Construct largest value by pairing items
    if len(posA) % 2 == 1: # Discard the one with smallest absolute value
        posA = posA[1:]
    if len(negA) % 2 == 1: # Discard the one with smallest absolute value
        negA = negA[:-1]
    pos_pairs = posA[0::2] * posA[1::2]
    neg_pairs = negA[0::2] * negA[1::2]
    pairs = np.concatenate([pos_pairs, neg_pairs], axis=0).tolist()
    pairs = sorted(pairs, reverse=True)[:K//2]
    ans = ans * prod(pairs) % M

    return ans

print(solve())

Submission status: Accepted

Solution code:
#from functools import reduce
from collections import deque

#解説見た

def solve(N, K, A):
    MOD = int(1e9 + 7)
    A_plus = [x for x in A if x >= 0]
    A_plus.sort(reverse=True)
    A_minus = [x for x in A if x < 0]
    A_minus.sort()

    if K == 1:
        return max(A) % MOD
    if K == N:
        #ans = reduce(operator.mul, A)
        ans = 1
        for t in A:
            ans *= t
            ans %= MOD
        return ans % MOD

    if len(A_plus) == 0:
        #minusだけから選ぶ場合
        if K % 2 == 1:
            #答えは負になるので、絶対値が小さい順に積を取る
            ans = 1
            for t in list(reversed(A_minus))[:K]:
                ans *= t
                ans %= MOD
            return ans
        else:
            #答えは正になるので、絶対値が大きい順に積をとる
            ans = 1
            for t in A_minus[:K]:
                ans *= t
                ans %= MOD
            return ans
    
    k = K
    S = []
    A_plus = deque(A_plus)
    A_minus = deque(A_minus)
    if k % 2 == 1:
        t = A_plus.popleft()
        S.append(t)
        k -= 1
    #kは偶数になった
    assert k % 2 == 0
    while k > 0:
        if len(A_minus) < 2:
            t1 = A_plus.popleft()
            S.append(t1)
            t2 = A_plus.popleft()
            S.append(t2)
            k -= 2
        elif len(A_plus) < 2:
            t1 = A_minus.popleft()
            S.append(t1)
            t2 = A_minus.popleft()
            S.append(t2)
            k -= 2
        else:
            t_p = A_plus[0] * A_plus[1]
            t_m = A_minus[0] * A_minus[1]
            if t_p >= t_m:
                t1 = A_plus.popleft()
                S.append(t1)
                t2 = A_plus.popleft()
                S.append(t2)
                assert t1 * t2 == t_p
                k -= 2
            else:
                t1 = A_minus.popleft()
                S.append(t1)
                t2 = A_minus.popleft()
                S.append(t2)
                assert t1 * t2 == t_m
                k -= 2
    ans = 1
    for t in S:
        ans *= t
        ans %= MOD
    return ans % MOD

if __name__ == "__main__":
    #with open('ABC173E/random_mz03.txt', 'r') as f:
    #    input = f.readline
    N, K = tuple(int(c) for c in input().split())
    A = [int(c) for c in input().split()]
    ret = solve(N, K, A)
    print(ret)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def mod_div(x, y, mod=10 ** 9 + 7):
    return x * pow(y, mod - 2, mod) % mod


def solve():
    N, K = map(int, rl().split())
    A = list(map(int, rl().split()))
    MOD = 10 ** 9 + 7
    
    if K == N:
        ans = 1
        for ai in A:
            ans *= ai
            ans %= MOD
        print(ans)
        return

    A.sort(key=lambda num: abs(num), reverse=True)
    if all(ai < 0 for ai in A) and K % 2 == 1:
        ans = 1
        for ai in A[-K:]:
            ans *= ai
            ans %= MOD
        print(ans)
        return
    
    ans = 1
    INF = 10 ** 10
    min_pos, min_neg = INF, INF
    cnt_neg = 0
    for ai in A[:K]:
        if ai < 0:
            min_neg = ai
            cnt_neg += 1
        else:
            min_pos = ai
        ans *= ai
        ans %= MOD
    
    if cnt_neg % 2 == 0:
        print(ans)
    else:
        n_pos, n_neg = INF, INF
        for ai in A[K:]:
            if n_pos != INF and n_neg != INF:
                break
            if ai < 0 and n_neg == INF:
                n_neg = ai
            elif 0 <= ai and n_pos == INF:
                n_pos = ai
        if min_pos != INF and min_neg != INF and n_pos != INF and n_neg != INF:
            if abs(min_pos * n_pos) <= abs(min_neg * n_neg):
                ans = mod_div(ans, min_pos) * n_neg % MOD
            else:
                ans = mod_div(ans, min_neg) * n_pos % MOD
        elif min_neg != INF and n_pos != INF:
            ans = mod_div(ans, min_neg) * n_pos % MOD
        else:
            ans = mod_div(ans, min_pos) * n_neg % MOD
        print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from functools import reduce
from collections import deque
#import operator

#解説見た

def solve(N, K, A):
    MOD = int(1e9 + 7)
    A_plus = [x for x in A if x >= 0]
    A_plus.sort(reverse=True)
    A_minus = [x for x in A if x < 0]
    A_minus.sort()
    #print('+', len(A_plus))
    #print('-',len(A_minus))
    #from collections import Counter
    #print(Counter(A_plus))
    #print(Counter(A_minus))

    if K == 1:
        return max(A) % MOD
    if K == N:
        #ans = reduce(operator.mul, A)
        ans = 1
        for t in A:
            ans *= t
            ans %= MOD
        return ans % MOD

    if len(A_plus) == 0:
        #minusだけから選ぶ場合
        if K % 2 == 1:
            #答えは負になるので、絶対値が小さい順に積を取る
            ans = 1
            for t in list(reversed(A_minus))[:K]:
                ans *= t
                ans %= MOD
            return ans
        else:
            #答えは正になるので、絶対値が大きい順に積をとる
            ans = 1
            for t in A_minus[:K]:
                ans *= t
                ans %= MOD
            return ans
    
    k = K
    S = []
    A_plus = deque(A_plus)
    A_minus = deque(A_minus)
    if k % 2 == 1:
        t = A_plus.popleft()
        S.append(t)
        k -= 1
    #kは偶数になった
    assert k % 2 == 0
    while k > 0:
        if len(A_minus) < 2:
            #print('k',k)
            #print('+', list(A_plus))
            #print('-',list(A_minus))
            t1 = A_plus.popleft()
            S.append(t1)
            t2 = A_plus.popleft()
            S.append(t2)
            k -= 2
        elif len(A_plus) < 2:
            t1 = A_minus.popleft()
            S.append(t1)
            t2 = A_minus.popleft()
            S.append(t2)
            k -= 2
        else:
            t_p = A_plus[0] * A_plus[1]
            t_m = A_minus[0] * A_minus[1]
            if t_p >= t_m:
                t1 = A_plus.popleft()
                S.append(t1)
                t2 = A_plus.popleft()
                S.append(t2)
                assert t1 * t2 == t_p
                k -= 2
            else:
                t1 = A_minus.popleft()
                S.append(t1)
                t2 = A_minus.popleft()
                S.append(t2)
                assert t1 * t2 == t_m
                k -= 2
    #print(Counter(S))
    #print(len(S), K)
    ans = 1
    for t in S:
        ans *= t
        ans %= MOD
    return ans % MOD

if __name__ == "__main__":
    #with open('ABC173E/random_mz03.txt', 'r') as f:
    #    input = f.readline
    N, K = tuple(int(c) for c in input().split())
    A = [int(c) for c in input().split()]
    ret = solve(N, K, A)
    print(ret)

Submission status: Accepted

Solution code:
"""
    Satwik_Tiwari ;) .
    4th july , 2020  - Saturday
"""

#===============================================================================================
#importing some useful libraries.
from __future__ import division, print_function

from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase


import bisect
from heapq import *
from math import *
from collections import deque
from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
from itertools import combinations as comb # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
from itertools import permutations as permutate
from bisect import bisect_left as bl
#If the element is already present in the list,
# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect
#If the element is already present in the list,
# the right most position where element has to be inserted is returned

#==============================================================================================

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)

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

#===============================================================================================
#some shortcuts

mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") #for fast input
def out(var): sys.stdout.write(str(var))  #for fast output, always take string
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())
# def graph(vertex): return [[] for i in range(0,vertex+1)]
def zerolist(n): return [0]*n
def nextline(): out("\n")  #as stdout.write always print sring.
def testcase(t):
    for p in range(t):
        solve()
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(a,b):
    ans = 1
    while(b>0):
        if(b%2==1):
            ans*=a
        a*=a
        b//=2
    return ans
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
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

#===============================================================================================
# code here ;))
def bs(a,l,h,x):
    while(l<h):
        # print(l,h)
        mid = (l+h)//2
        if(a[mid] == x):
            return mid
        if(a[mid] < x):
            l = mid+1
        else:
            h = mid
    return l

def sieve(a): #O(n loglogn) nearly linear
    #all odd mark 1
    for i in range(3,((10**6)+1),2):
        a[i] = 1
    #marking multiples of i form i*i 0. they are nt prime
    for i in range(3,((10**6)+1),2):
        for j in range(i*i,((10**6)+1),i):
            a[j] = 0
    a[2] = 1 #special left case
    return (a)


def bfs(g,st):
    visited = [-1]*(len(g))
    visited[st] = 0
    queue = []
    queue.append(st)
    new = []
    while(len(queue) != 0):
        s = queue.pop()
        new.append(s)
        for i in g[s]:
            if(visited[i] == -1):
                visited[i] = visited[s]+1
                queue.append(i)
    return visited


def dfsusingstack(v,st):
    d = deque([])
    visited = [0]*(len(v))
    d.append(st)
    new = []
    visited[st] = 1
    while(len(d) != 0):
        curr = d.pop()
        new.append(curr)
        for i in v[curr]:
            if(visited[i] == 0):
                visited[i] = 1
                d.append(i)
    return new


def solve():
    n,k =sep()
    a = lis()
    pos= []
    neg = []
    for i in range(n):
        if(a[i]>=0):
            pos.append(a[i])
        else:
            neg.append(a[i])
    pos = sorted(pos)[::-1]
    neg = sorted(neg)
    cnt = k
    st1 = 0
    st2 = 0
    ans = 1
    f = False
    end2 = len(neg)-1
    while(cnt>0):
        # print(ans)
        if(cnt>1):
            if(st1>=len(pos)-1 and st2>=len(neg)-1):
                ans = (ans*((neg[st2]*pos[st1])%mod))%mod
                st1+=1
                st2+=1
                cnt-=2
                continue
            if(st1>=len(pos)-1):
                ans = (ans*((neg[st2]*neg[st2+1])%mod))%mod
                st2+=2
                cnt-=2
                continue
            if(st2>=len(neg)-1):
                ans = (ans*((pos[st1]*pos[st1+1])%mod))%mod
                st1+=2
                cnt-=2
                continue
            if(cnt==3 and st1 == len(pos)-2):
                ans = (ans*((neg[st2]*neg[st2+1])%mod))%mod
                st2+=2
                cnt-=2
                continue
            if(pos[st1]*pos[st1+1] > neg[st2]*neg[st2+1]):
                ans = (ans*((pos[st1]*pos[st1+1])%mod))%mod
                st1+=2
                cnt-=2
            else:
                ans = (ans*((neg[st2]*neg[st2+1])%mod))%mod
                st2+=2
                cnt-=2
        else:
            if(st1>len(pos)-1):
                f = True
                cnt=0
                continue
                # if(end2 > st2):
                #     print(ans,neg[end2])
                #     ans = (ans*(neg[end2]))%mod
                #     end2-=1
                #     cnt-=1
                #     continue
                # ans = (ans*neg[st2])%mod
                # st2+=1
                # cnt-=1
                # continue
            ans = (ans*pos[st1])%mod
            st1+=1
            cnt-=1

    if(f):
        new = pos+neg
        for i in range(len(new)):
            new[i] = abs(new[i])

        new = sorted(new)
        ans = 1
        for i in range(k):
            ans*=new[i]
            ans%=mod
        print((-ans)%mod)
        return

    print(ans%mod)





testcase(1)
# testcase(int(inp()))

Submission status: Accepted

Solution code:
def resolve():
    def addans(i, ans):
        return ans * i % mod
    import sys
    import bisect
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    inf = float("inf")
    n, k = map(int, input().split())
    a = sorted(list(map(int, input().split())))
    l = bisect.bisect_left(a, 0)
    r = bisect.bisect_right(a, 0)
    ans = 1
    minus = a[::-1]
    plus = a[:]
    if r == n and k % 2 == 1:
        ans = 1
        for i in range(k):
            ans = addans(a[-i - 1], ans)
        print(ans)
        return
    if k % 2 == 1:
        ans = plus.pop()
        k -= 1
    try:
        m = minus.pop() * minus.pop()
    except:
        m = -inf
    try:
        p = plus.pop() * plus.pop()
    except:
        p = -inf
    for _ in range(k // 2):
        if p >= m:
            ans = addans(p, ans)
            try:
                p = plus.pop() * plus.pop()
            except:
                p = -inf
        else:
            ans = addans(m, ans)
            try:
                m = minus.pop() * minus.pop()
            except:
                m = -inf
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

allm = True
for a in A:
    if a > 0:
        allm = False
        break

if N == K:
    ans = 1
    for a in A:
        ans = (ans*a) % MOD
    print(ans)
elif allm and K % 2 == 1:
    A.sort()
    A.reverse()
    ans = 1
    for a in A[:K]:
        ans = (ans*a) % MOD
    print(ans)
else:
    p, m = [], []
    for a in A:
        if a > 0:
            p.append(a)
        if a < 0:
            m.append(-a)
    p.sort(key=lambda k: -k)
    m.sort(key=lambda k: -k)

    pi, mi = 0, 0
    ans = 1
    while K > 0:
        if K == 1:
            ans = (ans*p[pi]) % MOD
            break
        elif pi < len(p)-1 or mi < len(m)-1:
            pv, mv = 0, 0
            if pi < len(p)-1:
                pv = p[pi]*p[pi+1]
            if mi < len(m)-1:
                mv = m[mi]*m[mi+1]

            if pv > mv:
                ans = (ans*p[pi]) % MOD
                pi += 1
                K -= 1
            else:
                ans = (ans*mv) % MOD
                mi += 2
                K -= 2
        else:
            ans = 0
            break
    print(ans)

Submission status: Accepted

Solution code:
mod = 10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort(key=lambda x:-abs(x))

if N==K:
    ans = 1
    for i in range(N):
        ans *= A[i]
        ans %= mod
elif A[K-1]==0:
    ans = 0
else:
    p = []
    p_ = []
    n = []
    n_ = []
    for i in range(N):
        a = A[i]
        if i<K:
            if a>0:
                p.append(a)
            elif a<0:
                n.append(a)
        else:
            if a>0:
                p_.append(a)
            elif a<0:
                n_.append(a)
    if len(n)%2==0:
        ans = 1
        for a in n:
            ans *= a
            ans %= mod
        for a in p:
            ans *= a
            ans %= mod
    else:
        if len(p)+len(p_)==0:
            if len(n)+len(n_)==N:
                n += n_
                ans = 1
                for i in range(K):
                    ans *= n[-i-1]
                    ans %= mod
            else:
                ans = 0
        else:
            if len(p)==0:
                n.pop()
                ans = p_[0]
                for a in n:
                    ans *= a
                    ans %= mod
            else:
                cand = []
                ap = p.pop()
                if p_:
                    cand.append([ap,p_[0]])
                an = n.pop()
                if n_:
                    cand.append([an,n_[0]])
                if len(cand)==2:
                    ap1,ap2 = cand[0]
                    an1,an2 = cand[1]
                    ans = max(ap1*ap2,an1*an2)%mod
                    for a in n:
                        ans *= a
                        ans %= mod
                    for a in p:
                        ans *= a
                        ans %= mod
                else:
                    ans = cand[0][0]*cand[0][1]%mod
                    for a in n:
                        ans *= a
                        ans %= mod
                    for a in p:
                        ans *= a
                        ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
import collections, heapq, itertools, bisect
import math, fractions
from functools import reduce, lru_cache
import sys, copy


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]

class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

    def inverse(self):
        return pow(self.x, MOD - 2, MOD)

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    N, K = LI()
    A = LI()

    if K == N:
        print(reduce(lambda x, y: x * y, A, ModInt(1)))
        exit()

    plus = sorted([ai for ai in A if ai >= 0], reverse=True)
    minus = sorted([ai for ai in A if ai < 0])

    if len(plus) == 0:
        if K % 2 == 1:
            print(reduce(lambda x, y: x * y, minus[-K:], ModInt(1)))
        else:
            print(reduce(lambda x, y: x * y, minus[:K], ModInt(1)))
        exit()

    ip, im = 0, 0
    ans = ModInt(1)

    j = 0

    while True:
        if j == K:
            break
        if j == K - 1:
            ans *= plus[ip]
            break

        # K - j >= 2
        if len(plus) - ip >= 2 and len(minus) - im >= 2:
            p = plus[ip] * plus[ip+1]
            m = minus[im] * minus[im+1]
            if p > m:
                ans *= plus[ip]
                ip += 1
                j += 1
            else:
                ans *= m
                im += 2
                j += 2
        elif len(plus) - ip >= 2:
            ans *= plus[ip]
            ip += 1
            j += 1
        elif len(minus) - im >= 2:
            ans *= minus[im] * minus[im+1]
            im += 2
            j += 2

    print(ans)



if __name__ == '__main__':
    main()