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:
n, k = map(int, input().split())
A = [*map(int, input().split())]
P, M = [], [] # plus, minus
for a in A:
    if a < 0: M.append(a)
    else: P.append(a)

def mix():
    len_p = len(P); len_m = len(M)
    P.sort(reverse=True); M.sort()
    P.append(-1); M.append(1) # add endpoint
    pa, ma = [], []
    while len(pa) + len(ma) < k:
        if P[len(pa)] < -M[len(ma)]: ma.append(M[len(ma)])
        else: pa.append(P[len(pa)])
    if len(ma)%2 == 0: return pa + ma
    exist_pa = len(pa) > 0; exist_ma = len(ma) > 0
    remain_p = len_p - len(pa) > 0; remain_m = len_m - len(ma) > 0
    if exist_pa & exist_ma & remain_p & remain_m:
        if abs(pa[-1] * P[len(pa)]) < abs(ma[-1] * M[len(ma)]):
            pa.pop(); ma.append(M[len(ma)])
        else:
            ma.pop(); pa.append(P[len(pa)])
    elif exist_ma & remain_p:
        ma.pop(); pa.append(P[len(pa)])
    elif exist_pa & remain_m:
        pa.pop(); ma.append(M[len(ma)])
    else:
        P.pop(); M.pop()
        P.sort(); M.sort(reverse=True)
        P.append(-1); M.append(1) # add endpoint
        pa, ma = [], []
        while len(pa) + len(ma) < k:
            if P[len(pa)] >= -M[len(ma)]: ma.append(M[len(ma)])
            else: pa.append(P[len(pa)])
        if len(ma)%2 == 1: return pa + ma
        exist_pa = len(pa) > 0; exist_ma = len(ma) > 0
        remain_p = len_p - len(pa) > 0; remain_m = len_m - len(ma) > 0
        if exist_pa & exist_ma & remain_p & remain_m:
            if abs(pa[-1] * P[len(pa)]) >= abs(ma[-1] * M[len(ma)]):
                pa.pop(); ma.append(M[len(ma)])
            else:
                ma.pop(); pa.append(P[len(pa)])
        elif exist_ma & remain_p:
            ma.pop(); pa.append(P[len(pa)])
        elif exist_pa & remain_m:
            pa.pop(); ma.append(M[len(ma)])
    return pa + ma

ans_list = []
if k==n: ans_list = A
elif len(P) == n: ans_list = sorted(P, reverse=True)[:k]
elif len(M) == n: ans_list = sorted(M, reverse=k%2)[:k]
else: ans_list = mix()
MOD = 10**9 + 7
ans = 1
for a in ans_list: ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from logging import *
basicConfig(level=DEBUG, format='%(levelname)s: %(message)s')
disable(CRITICAL)

MOD = 10**9 + 7
INF = MOD
def mmul(a, b): return a*b%MOD

n, k = map(int, input().split())
A = [*map(int, input().split())]
P, M = [], [] # plus, minus
for a in A:
    if a < 0: M.append(a)
    else: P.append(a)

debug('A {}'.format(sorted(A, reverse=True, key=lambda x:abs(x))))


def mix():
    len_p = len(P); len_m = len(M)

    P.sort(reverse=True); M.sort()
    P.append(-1); M.append( 1) # add endpoint

    debug('P {}'.format(P));debug('M {}'.format(M))

    pa, ma = [], []
    while len(pa) + len(ma) < k:
        if P[len(pa)] < -M[len(ma)]: ma.append(M[len(ma)])
        else: pa.append(P[len(pa)])

    debug('pa {}'.format(pa));debug('ma {}'.format(ma))
    if len(ma)%2 == 0: return pa + ma

    exist_pa = len(pa) > 0; exist_ma = len(ma) > 0
    remain_p = len_p - len(pa) > 0; remain_m = len_m - len(ma) > 0
    debug('exist_pa {}'.format(exist_pa));debug('exist_ma {}'.format(exist_ma))
    debug('remain_p {}'.format(remain_p));debug('remain_m {}'.format(remain_m))

    if exist_pa & exist_ma & remain_p & remain_m:
        p_in = pa[-1]; p_out = P[len(pa)]
        m_in = ma[-1]; m_out = M[len(ma)]
        if abs(p_in*p_out) < abs(m_in*m_out): pa.pop(); ma.append(m_out)
        else: ma.pop(); pa.append(p_out)
        debug('pa {}'.format(pa));debug('ma {}'.format(ma))
        return pa + ma

    # if (not exist_pa) & exist_ma & remain_p & (not remain_m):
    # if exist_ma & remain_p & (not remain_m):
    if exist_ma & remain_p:
        m_in = ma[-1]; p_out = P[len(pa)]
        ma.pop(); pa.append(p_out)
        debug('pa {}'.format(pa));debug('ma {}'.format(ma))
        return pa + ma

    # if exist_pa & (not exist_ma) & (not remain_p) & remain_m:
    # if exist_pa & (not remain_p) & remain_m:
    if exist_pa & remain_m:
        p_in = pa[-1]; m_out = M[len(ma)]
        pa.pop(); ma.append(m_out)
        debug('pa {}'.format(pa));debug('ma {}'.format(ma))
        return pa + ma

    # --------------------------------
    P.pop(); M.pop()

    P.sort(); M.sort(reverse=True)
    P.append(-1); M.append( 1) # add endpoint
    debug('---')
    debug('P {}'.format(P));debug('M {}'.format(M))

    pa, ma = [], []
    while len(pa) + len(ma) < k:
        if P[len(pa)] >= -M[len(ma)]: ma.append(M[len(ma)])
        else: pa.append(P[len(pa)])

    debug('pa {}'.format(pa));debug('ma {}'.format(ma))
    if len(ma)%2 == 1: return pa + ma

    exist_pa = len(pa) > 0; exist_ma = len(ma) > 0
    remain_p = len_p - len(pa) > 0; remain_m = len_m - len(ma) > 0
    debug('exist_pa {}'.format(exist_pa));debug('exist_ma {}'.format(exist_ma))
    debug('remain_p {}'.format(remain_p));debug('remain_m {}'.format(remain_m))

    if exist_pa & exist_ma & remain_p & remain_m:
        p_in = pa[-1]; p_out = P[len(pa)]
        m_in = ma[-1]; m_out = M[len(ma)]
        if abs(p_in*p_out) >= abs(m_in*m_out): pa.pop(); ma.append(m_out)
        else: ma.pop(); pa.append(p_out)
        debug('pa {}'.format(pa));debug('ma {}'.format(ma))
        return pa + ma

    # if (not exist_pa) & exist_ma & remain_p & (not remain_m):
    if exist_ma & remain_p:
        m_in = ma[-1]; p_out = P[len(pa)]
        ma.pop(); pa.append(p_out)
        debug('pa {}'.format(pa));debug('ma {}'.format(ma))
        return pa + ma

    # if exist_pa & (not exist_ma) & (not remain_p) & remain_m:
    if exist_pa & remain_m:
        p_in = pa[-1]; m_out = M[len(ma)]
        pa.pop(); ma.append(m_out)
        debug('pa {}'.format(pa));debug('ma {}'.format(ma))
        return pa + ma

    # return [0]
    return pa + ma


ans = 1
if k==n:
    debug('k==n: {} == {} '.format(k,n))
    debug('A {}'.format(A))
    for a in A: ans = mmul(ans, a)
else:
    debug('k<n: {} < {} '.format(k,n))
    if len(P) == n:
        debug('n({}) all plus({})'.format(n,len(P)))
        P.sort(reverse=True)
        debug('P[:k] {}'.format(P[:k]))
        for a in P[:k]: ans = mmul(ans, a)
    elif len(M) == n:
        debug('n({}) all minus({})'.format(n,len(M)))
        if k%2:
            debug('k({}) is odd ({})'.format(k,k%2))
            M.sort(reverse=True)
        else:
            debug('k({}) is even ({})'.format(k,k%2))
            M.sort()
        debug('M[:k] {}'.format(M[:k]))
        for a in M[:k]: ans = mmul(ans, a)
    else:
        debug('n({}) mix plus({}):minus({})'.format(n,len(P),len(M)))
        for a in mix(): ans = mmul(ans, a)

ans += MOD; ans %= MOD
debug('ans {}'.format(ans))
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
import numpy as np

mod=10**9+7

def mat(list):
    return reduce(lambda a,b: a*b%mod, list)


N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
A = np.array(sorted(A, key=abs, reverse=True))
A_pn = A < 0
if N == np.count_nonzero(A_pn):
    if K % 2 == 0:
        print(mat(A[:K]))
    else:
        print(mat(A[-K:]))
elif np.count_nonzero(A_pn[:K]) % 2 == 0:
    print(mat(A[:K]))
elif N==K:
    print(mat(A))
else:
    negative_all = np.where(A_pn)[0]
    negative_rest = np.count_nonzero(negative_all>=K)
    if negative_rest == 0:
        # 負の数が残っていない
        A[negative_all[-1]] = A[K]
        print(mat(A[:K]))
    elif negative_rest == N-K:
        # 正の数が残っていない
        last_positive = np.where(A_pn[:K]==False)[0][-1]
        A[last_positive] = A[K]
        print(mat(A[:K]))
    elif len(negative_all)-negative_rest==K:
        # 負の数しか選択されていない
        last_negative = negative_all[negative_all<K][-1]
        next_positive = np.where(A_pn==False)[0][0]
        A[last_negative] = A[next_positive]
        print(mat(A[:K]))
    else:
        last_negative = negative_all[negative_all<K][-1]
        next_negative = negative_all[negative_all>=K][0]
        positive_all = np.where(A_pn==False)[0]
        last_positive = positive_all[positive_all<K][-1]
        next_positive = positive_all[positive_all>=K][0]
        if A[last_negative]*A[next_negative] > A[last_positive]*A[next_positive]:
            A[last_positive] = A[next_negative]
        else:
            A[last_negative] = A[next_positive]
        print(mat(A[:K]))

Submission status: Accepted

Solution code:
## necessary imports
import sys
input = sys.stdin.readline
# from math import ceil, floor, factorial;

def ceil(x):
    if x != int(x):
        x = int(x) + 1;
    return x;
    
# swap_array function
def swaparr(arr, a,b):
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp

## gcd function
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b, a % b);

## nCr function efficient using Binomial Cofficient
def nCr(n, k): 
    if(k > n - k): 
        k = n - k 
    res = 1
    for i in range(k): 
        res = res * (n - i) 
        res = res / (i + 1) 
    return int(res) 

## upper bound function code -- such that e in a[:i] e < x;
def upper_bound(a, x, lo=0, hi = None):
    if hi == None:
        hi = len(a);
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x:
            lo = mid+1
        else:
            hi = mid
    return lo

## prime factorization
def primefs(n):
    ## if n == 1    ## calculating primes
    primes = {}
    while(n%2 == 0 and n > 0):
        primes[2] = primes.get(2, 0) + 1
        n = n//2
    for i in range(3, int(n**0.5)+2, 2):
        while(n%i == 0 and n > 0):
            primes[i] = primes.get(i, 0) + 1
            n = n//i
    if n > 2:
        primes[n] = primes.get(n, 0) + 1
    ## prime factoriazation of n is stored in dictionary
    ## primes and can be accesed. O(sqrt n)
    return primes

## MODULAR EXPONENTIATION FUNCTION
def power(x, y, p): 
    res = 1
    x = x % p  
    if (x == 0) : 
        return 0
    while (y > 0) : 
        if ((y & 1) == 1) : 
            res = (res * x) % p 
        y = y >> 1      
        x = (x * x) % p 
    return res 

## DISJOINT SET UNINON FUNCTIONS
def swap(a,b):
    temp = a
    a = b
    b = temp
    return a,b

# find function with path compression included (recursive)
# def find(x, link):
#     if link[x] == x:
#         return x
#     link[x] = find(link[x], link);
#     return link[x];

# find function with path compression (ITERATIVE)
def find(x, link):
    p = x;
    while( p != link[p]):
        p = link[p];
    
    while( x != p):
        nex = link[x];
        link[x] = p;
        x = nex;
    return p;


# the union function which makes union(x,y)
# of two nodes x and y
def union(x, y, link, size):
    x = find(x, link)
    y = find(y, link)
    if size[x] < size[y]:
        x,y = swap(x,y)
    if x != y:
        size[x] += size[y]
        link[y] = x

## returns an array of boolean if primes or not USING SIEVE OF ERATOSTHANES
def sieve(n): 
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
    return prime

#### PRIME FACTORIZATION IN O(log n) using Sieve ####
MAXN = int(1e5 + 5)
def spf_sieve():
    spf[1] = 1;
    for i in range(2, MAXN):
        spf[i] = i;
    for i in range(4, MAXN, 2):
        spf[i] = 2;
    for i in range(3, ceil(MAXN ** 0.5), 2):
        if spf[i] == i:
            for j in range(i*i, MAXN, i):
                if spf[j] == j:
                    spf[j] = i;
    ## function for storing smallest prime factors (spf) in the array

################## un-comment below 2 lines when using factorization #################
# spf = [0 for i in range(MAXN)]
# spf_sieve();
def factoriazation(x):
    ret = {};
    while x != 1:
        ret[spf[x]] = ret.get(spf[x], 0) + 1;
        x = x//spf[x]
    return ret
    ## this function is useful for multiple queries only, o/w use
    ## primefs function above. complexity O(log n)

## taking integer array input
def int_array():
    return list(map(int, input().strip().split()))
## taking string array input
def str_array():
    return input().strip().split();

#defining a couple constants
MOD = int(1e9)+7;
CMOD = 998244353;
INF = float('inf'); NINF = -float('inf');

################### ---------------- TEMPLATE ENDS HERE ---------------- ###################

mod = 1000000007
N, K = int_array(); A = int_array();
pos = []; neg = [];
for i in range(N):
    if A[i] > 0:
        pos.append(A[i])
    else:
        neg.append(A[i])

ans = 1
if len(pos) == 0:
    if K % 2 == 0:
        neg.sort(reverse=True)
    else:
        neg.sort()
    for i in range(K):
        ans = (ans * neg.pop()) % mod
elif N == K:
    for i in pos:
        ans = (ans * i) % mod
    for i in neg:
        ans = (ans * i) % mod
else:
    pos.sort();
    neg.sort(reverse=True)
    if K % 2 == 1:
        ans = pos.pop()
    for i in range(K//2):
        if len(pos) > 1 and len(neg) > 1:
            if pos[-1] * pos[-2] > neg[-1] * neg[-2]:
                for _ in range(2):
                    ans = ans * pos.pop() % mod
            else:
                for _ in range(2):
                    ans = ans * neg.pop() % mod
        elif len(pos) > 1:
            for _ in range(2):
                ans = ans * pos.pop() % mod
        else:
            for _ in range(2):
                ans = ans * neg.pop() % mod

print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
minus=[]
plus=[]
cnt=Counter(a)
zerocnt=cnt[0]
minuscnt=0
pluscnt=0
for i in range(n):
    if a[i]<0:
        minuscnt+=1
        minus.append(a[i])
    elif a[i]>0:
        pluscnt+=1
        plus.append(a[i])


if n==k:
    ans=1
    for i in range(n):
        ans*=a[i]
        ans%=mod
    print(ans%mod)
    quit()

if minuscnt==n:
    ans=1
    if k%2==0:
        for i in range(k):
            ans*=a[i]
            ans%=mod
        print(ans)
    else:
        for i in range(k):
            ans*=a[-1-i]
            ans%=mod
        print(ans)
    quit()

if minuscnt%2==1:
    minuscnt-=1

# print(minus)
plus.reverse()
# plus.append(0)
# plus.append(0)
# print(plus)

ans=1
nokori=k
m,p=0,0
# minuscnt=max(minuscnt,1)

while nokori:
    # print(pluscnt,p,m,nokori)
    if m==minuscnt:
        if p!=pluscnt:
            ans*=plus[p]
            p+=1
            nokori-=1
        else:
            ans=0
            nokori=0
    elif p==pluscnt:
        if nokori==1:
            ans=0
            nokori-=1
        else:
            ans*=minus[m]*minus[m+1]
            m+=2
            nokori-=2
    elif p+1==pluscnt:
        if nokori%2==0:
            ans*=minus[m]*minus[m+1]
            m+=2
            nokori-=2
            # if nokori==1:
        else:
            ans*=plus[p]
            p+=1
            nokori-=1
            # elif plus[p]>minus[m]*minus[m+1]:
            #     ans*=plus[p]
            #     p+=1
            #     nokori-=1
            # else:
            #     ans*=minus[m]*minus[m+1]
            #     m+=2
            #     nokori-=2
    elif nokori==1:
        ans*=plus[p]
        nokori-=1
    elif plus[p]*plus[p+1]>minus[m]*minus[m+1]:
        # if nokori%2==0:
        #     ans*=plus[p]*plus[p+1]
        #     p+=2
        #     nokori-=2
        # else:
        ans*=plus[p]
        p+=1
        nokori-=1
    else:
        ans*=minus[m]*minus[m+1]
        m+=2
        nokori-=2
    ans%=mod
print(ans%mod)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a=sorted(a,reverse=True)
mod=10**9+7
l=0
r=n-1
ans=1
if k%2==1:
  ans=a[0]
  l=1
if ans<0:
  c=1
  for i in range(k):
    c=c*a[i]%mod
  print(c)
  
else:
  for i in range(k//2):
    L=a[l]*a[l+1]
    R=a[r]*a[r-1]
    if L>=R:
      ans=ans*L%mod
      l+=2
    else:
      ans=ans*R%mod
      r-=2
  print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

N, K = MAP()
A = LIST()

A1 = []
A2 = []
zero = 0
for a in A:
    if a > 0:
        A1.append(a)
    elif a < 0:
        A2.append(-a)
    else:
        zero += 1

B1 = np.log(np.array(A1, dtype=np.longdouble))
B2 = np.log(np.array(A2, dtype=np.longdouble))
A1.sort()
A2.sort()
B1.sort()
B2.sort()
acc1 = np.insert(B1.cumsum(), 0, 0)
accrev1 = np.insert(B1[::-1].cumsum(), 0, 0)
acc2 = np.insert(B2.cumsum(), 0, 0)
accrev2 = np.insert(B2[::-1].cumsum(), 0, 0)
mx = -np.inf
mn = np.inf
idx1 = (-1, -1)
idx2 = (-1, -1)
for i in range(K+1):
    j = K - i
    if len(B1) < i or len(B2) < j:
        continue
    if j % 2 == 0:
        sm = accrev1[i] + accrev2[j]
        if sm > mx:
            mx = sm
            idx1 = (i, j)
    else:
        sm = acc1[i] + acc2[j]
        if sm < mn:
            mn = sm
            idx2 = (i, j)

if mx != -np.inf:
    ans = 1
    n, m = idx1
    A1.reverse()
    A2.reverse()
    for i in range(n):
        ans *= A1[i]
        ans %= MOD
    for i in range(m):
        ans *= -A2[i]
        ans %= MOD
    print(ans)
elif zero:
    print(0)
else:
    ans = 1
    n, m = idx2
    for i in range(n):
        ans *= A1[i]
        ans %= MOD
    for i in range(m):
        ans *= -A2[i]
        ans %= MOD
    print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split(' '))
l = map(int, input().split(' '))

s = 1
if n == k:
	for i in l:
		s *= i
		s %= 1000000007
	print(s)
else:
	pos = []
	neg = []

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

	pos.sort()
	neg.sort(reverse=True)
	answer = []

	if k % 2 == 1 and not pos:
		for i in range(k):
			s *= neg[i]
			s %= 1000000007
		print(s)

	else:
		if k % 2 == 1:
			s = pos.pop()
		for i in range(k//2):
			if len(pos) >= 2:
				answer.append(pos.pop()*pos.pop())
			else:
				break
		for i in range(k//2):
			if len(neg) >= 2:
				answer.append(neg.pop()*neg.pop())
			else:
				break
		answer.sort(reverse=True)
		for i in range(k//2):
			s *= answer[i]
			s %= 1000000007
		print(s)

Submission status: Accepted

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

if N==K: #全部
    ans=1
    for i in range(N):
        ans*=A[i]
        ans%=mod
    print(ans)
    exit()
if max(A)<0 and K%2==1: #答えがマイナス
    A.sort(reverse=True)
    ans=1
    for i in range(K):
        ans*=A[i]
        ans%=mod
    print(ans)
    exit()

plus=[]
minus=[]
for i in range(N):
    if A[i]>=0:
        plus.append(A[i])
    else:
        minus.append(A[i])
plus.sort(reverse=True) #5,3,1
minus.sort() #-5,-3,-1
plus_k=0
minus_k=0
if K%2==0:
    ans=1
else:
    ans=plus[0]
    plus_k=1

for _ in range(K):
    if plus_k+minus_k==K:
        break
    if plus_k>=len(plus)-1:
        ans*=minus[minus_k]*minus[minus_k+1]%mod
        ans%=mod
        minus_k+=2
        continue
    if minus_k>=len(minus)-1:
        ans*=plus[plus_k]*plus[plus_k+1]%mod
        ans%=mod
        plus_k+=2
        continue
    if plus[plus_k]*plus[plus_k+1]>minus[minus_k]*minus[minus_k+1]:
        ans*=plus[plus_k]*plus[plus_k+1]%mod
        ans%=mod
        plus_k+=2
        continue
    else:
        ans*=minus[minus_k]*minus[minus_k+1]%mod
        ans%=mod
        minus_k+=2
        continue
print(ans)

Submission status: Accepted

Solution code:
mod = 1000000007
N, K = map(int, input().split())

pos = []
neg = []
A = list(map(int, input().split()))
for i in range(N):
    if A[i] > 0:
        pos.append(A[i])
    else:
        neg.append(A[i])

ans = 1
if len(pos) == 0:
    if K % 2 == 0:
        neg.sort(reverse=True)
    else:
        neg.sort()
    for i in range(K):
        ans = (ans * neg.pop()) % mod
elif N == K:
    for i in pos:
        ans = (ans * i) % mod
    for i in neg:
        ans = (ans * i) % mod
else:
    pos.sort()
    neg.sort(reverse=True)
    if K % 2 == 1:
        ans = pos.pop()
    for i in range(K//2):
        if len(pos) > 1 and len(neg) > 1:
            if pos[-1] * pos[-2] > neg[-1] * neg[-2]:
                for _ in range(2):
                    ans = ans * pos.pop() % mod
            else:
                for _ in range(2):
                    ans = ans * neg.pop() % mod
        elif len(pos) > 1:
            for _ in range(2):
                ans = ans * pos.pop() % mod
        else:
            for _ in range(2):
                ans = ans * neg.pop() % mod


print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
m,p,z=[],[],0
for a in A:
    if a<0:
        m.append(a)
    elif a>0:
        p.append(a)
    else:
        z+=1
m.sort()
p.sort()
mod=10**9+7
from functools import reduce
if (len(p) or K%2==0) and K<len(m)+len(p) or K==len(m)+len(p) and len(m)%2==0:
    r=1
    i,j=0,0
    while i+j<K:
        if i<len(m)-1 and i+j<K-1 and (j>=len(p)-1 or m[i]*m[i+1]>p[-j-1]*p[-j-2]):
            r=r*m[i]*m[i+1]%mod
            i+=2
        else:
            r=r*p[-j-1]%mod
            j+=1
    print(r)
elif z:
    print(0)
else:
    print(reduce(lambda x,y:x*y%mod,(m+p)[-K:]))

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
mod = 10**9+7
plus = []
minus=[]
for i in A:
    if i>=0:
        plus.append(i)
    else:
        minus.append(i)
ok = False
if len(plus)>0:
    if n==k:
        ok = (len(minus)%2==0)
    else:
        ok = True
else:
    ok = (k%2==0)
ans = 1
if not ok:
    A.sort(key=abs)
    for i in range(k):
        ans *= A[i]
        ans %= mod
else:
    plus.sort()
    minus.sort(reverse=True)
    if k%2 == 1:
        ans *= plus.pop()
    P = []
    while len(plus) >= 2:
        P.append((plus.pop())*(plus.pop()))
    while len(minus) >= 2:
        P.append((minus.pop())*(minus.pop()))
    P.sort(reverse=True)
    for i in range(k//2):
        ans *= P[i]
        ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys

n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])

P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
#x:配列
mod=10**9+7
def multarray(x):
    ret=1
    for i in x:
        ret*=i
        ret%=mod
    return ret

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

#n==kの場合はかけるだけ
if n==k:
    print(multarray(a))
    exit()

#0以上の数と負の数に分けて格納
ap,am=[],[]
for i in range(n):
    if a[i]>=0:
        ap.append(a[i])
    else:
        am.append(a[i])
#それぞれ絶対値の順番にソート
ap.sort(reverse=True)
am.sort()

#0以上の数のみか正の数のみの場合は先に場合分け
if len(am)==0:
    print(multarray(ap[:k]))
    exit()
if len(ap)==0:
    if k%2==0:
        print(multarray(am[:k]))
    else:
        print(multarray(am[::-1][:k]))
    exit()

#組にして格納する(0以上か負かを記録しておく)
apm2=[]
for i in range(len(am)//2):
    apm2.append((am[2*i]*am[2*i+1],0))
for i in range(len(ap)//2):
    apm2.append((ap[2*i]*ap[2*i+1],1))
apm2.sort(reverse=True)

#0以上の数で次にどこを見るのかをチェックしておく
p=0
ans=[]
for i in range(k//2):
    p+=(2*apm2[i][1])
    ans.append(apm2[i][0])

#Kが偶数の時
if k%2==0:
    print(multarray(ans))
    exit()

ans_cand=[]
#一個増やす場合
if p!=len(ap):
    ans_cand.append(multarray(ans)*ap[p]%mod)
#一個減らして二個増やす場合
if p!=0:
    #減らすindex
    check_i=ans.index(ap[p-1]*ap[p-2])
    #ap[p-1]を減らす操作(0除算を避ける)
    ans[check_i]=ap[p-2]
    ans.append(apm2[k//2][0])
    ans_cand.append(multarray(ans))
print(max(ans_cand))

Submission status: Accepted

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

ans = 1
if N == K:
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit(0)

if N - A.count(0) < K:
    print(0)
    exit(0)

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

if K % 2 == 1 and len(plus) == 0:
    minus.sort(reverse=True)
    for i in range(K):
        ans *= minus[i]
        ans %= MOD
    print(ans)
    exit(0)

plus.sort(reverse=True)
minus.sort()

if len(minus) == 0:
    for k in range(K):
        ans *= plus[k]
        ans %= MOD
    print(ans)
    exit(0)

i = 0
j = 0

if K % 2 == 1:
    ans = plus[0]
    K -= 1
    plus = plus[1:]

for _ in range(K//2):
    if i+1 >= len(plus):
        ans *= (minus[j] * minus[j+1])
        ans %= MOD
        j += 2
        continue
    elif j+1 >= len(minus):
        ans *= (plus[i] * plus[i+1])
        ans %= MOD
        i += 2
        continue

    a = plus[i] * plus[i+1]
    b = minus[j] * minus[j+1]
    if a > b:
        ans *= a
        i += 2
    else:
        ans *= b
        j += 2
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
def prod(list):
    prod = 1
    for k in list:
        prod = (prod * k) % (10**9+7)
    return prod
    
    


n, kk = map(int, input().split())
a = list(map(int, input().split()))

plus = []
minus = []

for k in a:
    if k >= 0:
        plus.append(k)
    if k <= 0:
        minus.append(k)

if len(plus) == 0:
    if kk % 2 == 0:
        mi = sorted(minus)
        ans = prod(mi[:kk])
    else:
        mi = sorted(minus, reverse=True)
        ans = prod(mi[:kk])

    print(int(ans) % (10**9+7))

elif n == kk:
    ans = prod(a)
    print(int(ans) % (10**9+7))

else:
    mi = sorted(minus)
    pl = sorted(plus, reverse=True)
    mi.append(0)
    mi.append(0)
    pl.append(0)
    pl.append(0)
    miind = 0
    plind = 0
    ans = 1
    while kk > miind + plind:
        if mi[miind]*mi[miind+1] > pl[plind]*pl[plind+1] and kk != miind + plind + 1:
            ans = (ans*mi[miind]*mi[miind+1]) % (10**9+7)
            miind += 2
        else:
            ans = (ans*pl[plind]) % (10**9+7)
            plind += 1

    print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr.sort(reverse=True)
n=len(arr)
l=0
r=n-1
ans=1
if k%2==1:
    ans=arr[0]
    l=1
m=10**9+7
if ans<0:
    ans=1
    for i in range(k):
        ans*=arr[i]
        ans%=m
    print(ans)
    quit()
for i in range(k//2):
    po=arr[l]*arr[l+1]
    ne=arr[r]*arr[r-1]
    if po>=ne:
        l+=2
        ans*=po
        ans%=m
    else:
        r-=2
        ans*=ne
        ans%=m
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
MOD = 10**9+7
a = list(map(int,input().split()))
b = []
c = []
d = []
num_z = 0
for val in a:
    if val>0:
        b.append(val)
        d.append(val)
    elif val<0:
        c.append(-val)
        d.append(-val)
    else:
        num_z += 1
        d.append(0)
num_b = len(b)
num_c = len(c)
res = 1
if (N==num_c and K%2==1):
    d = sorted(d)
    for val in d[:K]:
        res = res*val%MOD
    res = -res%MOD
elif (N==K and num_c>0):
    c = sorted(c)
    for val in a:
        res = res*val%MOD
elif num_b==0:
    if K%2==0:
        if num_c >= K:
            c = sorted(c,reverse=True)
            for val in c[:K]:
                res = res*val%MOD
        else:
            res = 0
    else:
        res = 0
else:
    b = sorted(b,reverse=True)
    c = sorted(c,reverse=True)
    bidx = 0
    cidx = 0
    tmp = 0
    if num_b+num_c < K:
        res = 0
    else:
        if num_b >= K:
            bidx = K
        elif num_c>=2:
            bidx = num_b
            cidx = K-bidx
            if (K-num_b)%2==1:
                if cidx == num_c:
                    print(0)
                    exit()
                bidx -= 1
                cidx += 1
        else:
            print(0)
            exit()
        #print(bidx,cidx)
        for val in b[:bidx]:
            res = res*val%MOD
        for val in c[:cidx]:
            res = res*val%MOD
        for k in range(100000):
            if bidx<=1 or cidx+1 >= num_c:
                break
            if b[bidx-1]*b[bidx-2] > c[cidx]*c[cidx+1]:
                break
            else:
                res *= c[cidx]
                res *= c[cidx+1]
                res = res%MOD
                res = res*pow(b[bidx-1],MOD-2,MOD)
                res = res*pow(b[bidx-2],MOD-2,MOD)
                res = res%MOD
                bidx -= 2
                cidx += 2
print(res%MOD)

Submission status: Accepted

Solution code:
from functools import reduce

mod = 10 ** 9 + 7

N, K, *A = map(int, open(0).read().split())

A.sort(reverse=True)

ans = 1
l, r = 0, N - 1
if K % 2 == 1:
    ans = A[0]
    l = 1

if ans < 0:
    print(reduce(lambda a, b: a * b % mod, A[:K], 1))
    quit()


for i in range(K // 2):
    L = A[l] * A[l + 1]
    R = A[r] * A[r - 1]
    if L >= R:
        ans *= L
        l += 2
    else:
        ans *= R
        r -= 2
    ans %= mod

print(ans)