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

n, k = int_array(); a = int_array();
pos = []; neg = []; ans = 1;
for i in a:
    if i < 0:
        neg.append(i);
    else:
        pos.append(i);

if n == k:
    for i in a:
        ans = (ans * i) % MOD;
elif not pos:
    if k & 1:
        neg.sort(reverse = 1);
    else:
        neg.sort();
    for i in range(k):
        ans = (ans * neg[i]) % MOD;
else:
    pos.sort(); neg.sort(reverse = 1);
    if k & 1:
        ans = pos.pop();
    for _ in range(k // 2):
        if len(pos) > 1 and len(neg) > 1:
            if pos[-1] * pos[-2] >= neg[-1] * neg[-2]:
                ans = (ans * pos.pop()) % MOD;
                ans = (ans * pos.pop()) % MOD;
            else:
                ans = (ans * neg.pop()) % MOD;
                ans = (ans * neg.pop()) % MOD;
        elif len(pos) > 1:
            ans = (ans * pos.pop()) % MOD;
            ans = (ans * pos.pop()) % MOD;
        else:
            ans = (ans * neg.pop()) % MOD;
            ans = (ans * neg.pop()) % MOD;
print(ans);

Submission status: Accepted

Solution code:
#写経
#https://atcoder.jp/contests/abc173/submissions/15061788

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

    A.sort()
    MOD = 10 ** 9 + 7
    ans = 1

    if K % 2 == 1 and A[-1] < 0:
        for i in range(K):
            ans = ans * A[N - (i + 1)] % MOD

        print(ans)
        return

    l = 0
    r = N - 1
    if K % 2 == 1:
        ans = ans * A[r]
        r -= 1
    
    for _ in range(K // 2):
        ml = A[l] * A[l + 1]
        mr = A[r] * A[r - 1]
        if ml > mr:
            ans = ans * ml % MOD
            l += 2
        else:
            ans = ans * mr % MOD
            r -= 2

    print(ans)
    return
resolve()

Submission status: Accepted

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

a = list(map(int, input().split()))
a_pos = sorted([i for i in a if i >= 0])
a_neg = sorted([i for i in a if i < 0], reverse=True)

mod = 10 ** 9 + 7
ans = 1

if len(a_pos) == 0 and k % 2:
    for i in a_neg[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

while k > 0:
    if k == 1 or len(a_neg) <= 1:
        if len(a_pos) == 0:
            ans *= a_neg.pop()
        elif len(a_pos) > 0:
            ans *= a_pos.pop()
        k -= 1
    elif len(a_pos) <= 1:
        ans *= a_neg.pop() * a_neg.pop()
        k -= 2
    
    elif a_pos[-1] * a_pos[-2] > a_neg[-1] * a_neg[-2]:
        ans *= a_pos.pop()
        k -= 1
    elif a_pos[0] * a_pos[1] <= a_neg[-1] * a_neg[-2]:
        ans *= a_neg.pop() * a_neg.pop()
        k -= 2
    ans %= mod

print(ans)

Submission status: Accepted

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

a = list(map(int, input().split()))
a_pos = sorted([i for i in a if i >= 0])
a_neg = sorted([i for i in a if i < 0], reverse=True)

mod = 10 ** 9 + 7
ans = 1

if len(a_pos) == 0 and k % 2:
    for i in a_neg[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

while k > 0:
    if k == 1 or len(a_neg) <= 1:
        if len(a_pos) == 0:
            ans *= a_neg.pop()
        elif len(a_pos) > 0:
            ans *= a_pos.pop()
        k -= 1
    elif len(a_pos) <= 1:
        ans *= a_neg.pop() * a_neg.pop()
        k -= 2
    
    elif a_pos[-1] * a_pos[-2] > a_neg[-1] * a_neg[-2]:
        ans *= a_pos.pop()
        k -= 1
    elif a_pos[0] * a_pos[1] <= a_neg[-1] * a_neg[-2]:
        ans *= a_neg.pop() * a_neg.pop()
        k -= 2
    ans %= mod

else:
    print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 1000000007
plus = []
minus = []
ans = 1
lp = 0
lm = 0
lz = 0
for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
    lp += 1
  elif A[k] < 0:
    minus.append(A[k])
    lm += 1
  else:
    lz += 1
plus.sort(reverse = True)
minus.sort()
def main(mp, mm, plus, minus):
  mod = 1000000007
  ans = 1
  for k in range(mp):
    ans = ans * plus[k] % mod
  for k in range(mm):
    ans = ans * minus[k] % mod
  print(ans)
  exit()
if lz + K > N:
  print(0)
  exit()
elif lp == 0: 
  if K % 2 == 1:
    if lz > 0:
      print(0)
      exit()
    else:
      for k in range(K):
        ans = ans * minus[- k - 1] % mod
      print(ans)
      exit()
  else:
    main(0, K, plus, minus)
elif lm == 0:
  main(K, 0, plus, minus)
p = 0
m = 0
for _ in range(K):
  if plus[p] >= -1 * minus[m]:
    p += 1
    if p == lp:
      m = K - p
      break
  else:
    m += 1
    if m == lm:
      p = K - m
      break
if m % 2 == 0:
  main(p, m, plus, minus)
else:
  if p == lp:
    if m != lm:
      main(p - 1, m + 1, plus, minus)
    else:
      if lz > 0:
        print(0)
        exit()
      else:
        main(p, m, plus, minus)
  elif m == lm:
    main(p + 1, m - 1, plus, minus)
  elif p == 0:
    main(p + 1, m - 1, plus, minus)
  else:
    if plus[p] * plus[p - 1] > minus[m - 1] * minus[m]:
      main(p + 1, m - 1, plus, minus)
    else:
      main(p - 1, m + 1, plus, minus)

Submission status: Accepted

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

mod = 10 ** 9 + 7
plus = []
lz = 0
minus = []
ans = 1

for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
  elif A[k] < 0:
    minus.append(A[k])
  else:
    lz += 1
plus.sort(reverse = True)
minus.sort()
lp = len(plus)
lm = len(minus)

def main(mp, mm, plus, minus):
  mod = 10 ** 9 + 7
  ans = 1
  for k in range(mp):
    ans = ans * plus[k] % mod
  for k in range(mm):
    ans = ans * minus[k] % mod
  print(ans)
  exit()

if lz + K > N:
  print(0)
  exit()
elif lp == 0: 
  if K % 2 == 1:
    if lz > 0:
      print(0)
      exit()
    else:
      for k in range(K):
        ans = ans * minus[- k - 1] % mod
      print(ans)
      exit()
  else:
    main(0, K, plus, minus)
elif lm == 0:
  main(K, 0, plus, minus)

p = 0
m = 0
for _ in range(K):
  if plus[p] >= -1 * minus[m]:
    p += 1
    if p == lp:
      m = K - p
      break
  else:
    m += 1
    if m == lm:
      p = K - m
      break

if m % 2 == 0:
  main(p, m, plus, minus)
else:
  if p == lp:
    if m != lm:
      main(p - 1, m + 1, plus, minus)
    else:
      if lz > 0:
        print(0)
        exit()
      else:
        main(p, m, plus, minus)
  elif m == lm:
    main(p + 1, m - 1, plus, minus)
  elif p == 0:
    main(p + 1, m - 1, plus, minus)
  else:
    if plus[p] * plus[p - 1] > minus[m - 1] * minus[m]:
      main(p + 1, m - 1, plus, minus)
    else:
      main(p - 1, m + 1, plus, minus)

Submission status: Accepted

Solution code:
# 解説を参考に作成

# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
def inverse(a, p):
    """逆元"""
    a_, p_ = a, p
    x, y = 1, 0
    while p_:
        t = a_ // p_
        a_ -= t * p_
        a_, p_ = p_, a_
        x -= t * y
        x, y = y, x
    x %= p
    return x


def dev_mod(a, b, mod):
    """a(= A % mod) / b を mod で割った余り"""
    return (a * inverse(b, mod)) % mod


# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, K, As):
    mod = 10 ** 9 + 7
    As.sort()
    ans = 1
    if N == K:
        for a in As:
            ans = (ans * a) % mod
    elif As[-1] < 0 and K % 2 == 1:
        for k in range(1, K + 1):
            ans = (ans * As[- k]) % mod
    else:
        As.sort(key=abs)
        last_p = -1
        last_m = -1
        cnt_m = 0
        for k in range(1, K + 1):
            ans = (ans *  As[- k]) % mod
            if As[- k] < 0:
                last_m = As[- k]
                cnt_m += 1
            else:
                last_p = As[- k]
        if cnt_m % 2 == 1:
            mlt_p = max(As[:N - K])
            mlt_m = min(As[:N - K])
            if last_p < 0:
                ans = dev_mod(ans, last_m, mod) * mlt_p % mod
            elif mlt_m >= 0:
                ans = dev_mod(ans, last_m, mod) * mlt_p % mod
            elif mlt_p < 0:
                ans = dev_mod(ans, last_p, mod) * mlt_m % mod
            else:
                if abs(last_p * mlt_p) <= abs(last_m * mlt_m):
                    ans = dev_mod(ans, last_p, mod) * mlt_m % mod
                else:
                    ans = dev_mod(ans, last_m, mod) * mlt_p % mod
    print(ans % mod)


# def solve2(N, K, As):
#     mod = 10 ** 9 + 7
#     As.sort()
#     ans = 1
#     if N == K:
#         for a in As:
#             ans *= a
#     elif As[-1] < 0 and K % 2 == 1:
#         for k in range(1, K + 1):
#             ans *= As[- k]
#     else:
#         As.sort(key=abs)
#         last_p = None
#         last_m = None
#         cnt_m = 0
#         for k in range(1, K + 1):
#             ans *= As[- k]
#             if As[- k] < 0:
#                 last_m = As[- k]
#                 cnt_m += 1
#             else:
#                 last_p = As[- k]
#         if cnt_m % 2 == 1:
#             ans1 = ans // last_m * max(As[:N - K])
#             ans2 = ans // last_p * min(As[:N - K]) if last_p is not None else -1
#             ans = max(ans1, ans2)
#     print(ans % mod)


if __name__ == '__main__':
    N, K = map(int, input().split())
    As = [int(i) for i in input().split()]
    # import random
    # N, K = 2 * 10 ** 5, 10 ** 5
    # As = [random.randint(- 10 ** 9, 10 ** 9) for _ in range(N)]
    solve(N, K, As)
    # solve2(N, K, As)

Submission status: Accepted

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

mod = 10 ** 9 + 7
plus = []
zero = []
minus = []
ans = 1

for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
  elif A[k] < 0:
    minus.append(-1 * A[k])
  else:
    zero.append(A[k])
plus.sort(reverse = True)
minus.sort(reverse = True)
lp = len(plus)
lm = len(minus)
lz = len(zero)

if lz + K > N:
  print(0)
  exit()
elif lp == 0: 
  if K % 2 == 1:
    if lz > 0:
      print(0)
      exit()
    else:
      for k in range(K):
        ans = ans * (-1) * minus[- k - 1] % mod  
      print(ans)
      exit()
  else:
    for k in range(K):
      ans = ans * (-1) * minus[k] % mod
    print(ans)
    exit()
elif lm == 0:
  for k in range(K):
    ans = ans * plus[k] % mod
  print(ans)
  exit()

p = 0
m = 0
for k in range(K):
  if plus[p] >= minus[m]:
    p += 1
    if p == lp:
      m = K - p  
      break
  else:
    m += 1
    if m == lm:
      p = K - m
      break

def main(mp, mm, plus, minus):
  mod = 10 ** 9 + 7
  ans = 1
  for k in range(mp):
    ans = ans * plus[k] % mod
  for k in range(mm):
    ans = ans * (-1) * minus[k] % mod
  print(ans)
  exit()

if m % 2 == 0:
  main(p, m, plus, minus)
else:
  if p == lp:
    if m != lm:
      main(p - 1, m + 1, plus, minus)
    else:
      if lz > 0:
        print(0)
        exit()
      else:
        main(p, m, plus, minus)
  elif m == lm:
    main(p + 1, m - 1, plus, minus)
  elif p == 0:
    main(p + 1, m - 1, plus, minus)
  else:
    if plus[p] * plus[p - 1] > minus[m - 1] * minus[m]:
      main(p + 1, m - 1, plus, minus)
    else:
      main(p - 1, m + 1, plus, minus)

Submission status: Accepted

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

mod = 10 ** 9 + 7
plus = []
zero = []
minus = []
ans = 1

for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
  elif A[k] < 0:
    minus.append(-1 * A[k])
  else:
    zero.append(A[k])
plus.sort(reverse = True)
minus.sort(reverse = True)
lp = len(plus)
lm = len(minus)

if len(zero) + K > N:
  print(0)
  exit()
elif lp == 0: 
  if K % 2 == 1:
    if len(zero) > 0:
      print(0)
      exit()
    else:
      for k in range(K):
        ans = ans * (-1) * minus[- k - 1] % mod  
      print(ans)
      exit()
  else:
    for k in range(K):
      ans = ans * (-1) * minus[k] % mod
    print(ans)
    exit()
elif lm == 0:
  for k in range(K):
    ans = ans * plus[k] % mod
  print(ans)
  exit()

p = 0
m = 0
for k in range(K):
  if plus[p] >= minus[m]:
    p += 1
    if p == lp:
      m = K - p  
      break
  else:
    m += 1
    if m == lm:
      p = K - m
      break

def main(mp, mm, plus, minus, mod, K):
  ans = 1
  for k in range(mp):
    ans = ans * plus[k] % mod
  for k in range(mm):
    ans = ans * (-1) * minus[k] % mod
  print(ans)
  exit()

if m%2 == 0:
  main(p, m, plus, minus, mod, K)
else:
  if p == lp:
    if m != lm:
      main(p - 1, m + 1, plus, minus, mod, K)
    else:
      if len(zero) > 0:
        print(0)
        exit()
      else:
        main(p, m, plus, minus, mod, K)
  elif m == lm:
    main(p + 1, m - 1, plus, minus, mod, K)
  elif p == 0:
    main(p + 1, m - 1, plus, minus, mod, K)
  else:
    if plus[p] * plus[p - 1] > minus[m - 1] * minus[m]:
      main(p + 1, m - 1, plus, minus, mod, K)
    else:
      main(p - 1, m + 1, plus, minus, mod, K)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort(key=lambda x: -abs(x))
mod=10**9+7
p=1
mm=0
for i in range(k):
    if a[i]<0:
        mm+=1
    p*=a[i]
    p%=mod
if n==k or mm%2==0:
    print(p)
    exit()
    
m=0
for i in a:
    if i<=0:
        m+=1
if m==n:
    p=1
    for i in range(k):
        p*=a[n-i-1]
        p%=mod
    print(p)
    exit()
b1=[]
b2=[]
for i in range(k):
    if len(b1)==0 and a[k-1-i]>=0:
        b1.append(a[k-1-i])
    if len(b2)==0 and a[k-1-i]<0:
        b2.append(a[k-1-i])
for i in range(n-k):
    if len(b1)==1 and a[k+i]<0:
        b1.append(a[k+i])
    if len(b2)==1 and a[k+i]>=0:
        b2.append(a[k+i])
f=0
if len(b1)==len(b2)==2:
    if b1[1]*b2[0]>=b1[0]*b2[1]:
        f=1
    else:
        f=2
elif len(b2)<2:
    f=1
else:
    f=2

if f==1:
    p*=b1[1]*pow(b1[0],mod-2,mod)
    print(p%mod)
    exit()
else:
    p*=b2[1]*pow(b2[0],mod-2,mod)
    print(p%mod)
    exit()

Submission status: Accepted

Solution code:
import sys

N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7


def main():

    N, K = map(int, sys.stdin.readline().rstrip().split())
    A = [int(x) for x in sys.stdin.readline().rstrip().split()]

    P, M = [], []
    # A を非負、負で振り分ける
    for i in range(N):
        n = A[i]
        if n < 0:
            M.append(n)
        else:
            P.append(n)

    # 絶対値の大きい方から並べる
    P.sort(reverse=True)
    M.sort()
    n_p = len(P)
    n_m = len(M)
    # print(P, M)

    # 全部使う
    if K == N:
        ans = 1
        for a in A:
            ans = ans * a % MOD
        print(ans)
        return

    # 全部負の場合
    if n_p == 0:
        if K % 2 == 1:  # 奇数なら小さな方から取る
            ans = 1
            for i in range(K):
                ans = ans * M[-(i + 1)] % MOD
            print(ans)
            return
        else:
            ans = 1
            for i in range(K):
                ans = ans * M[i] % MOD
            print(ans)
            return

    i, j = 0, 0
    if K % 2 == 1:
        i += 1
    
    while K > 1:
        p, m = 0, 0
        if i + 1 < n_p:
            p = P[i] * P[i + 1]
        if j + 1 < n_m:
            m = M[j] * M[j + 1]
        if p >= m:
            i += 2
        else:
            j += 2
        K -= 2

    # print(i, j)
    ans = 1
    for u in range(i):
        ans = ans * P[u] % MOD
    for v in range(j):
        ans = ans * M[v] % MOD

    print(ans)


main()

Submission status: Accepted

Solution code:
def solve():
    P.sort(reverse = True)
    M.sort()
    P.append(-1)
    M.append(1) # add endpoint
    p, m = [], []
    while len(p) + len(m) < k:
        if P[len(p)] < -M[len(m)]:
            m.append(M[len(m)])
        else:
            p.append(P[len(p)])
    if len(m)%2 == 0: return p + m

    exist_p = len(p) > 0
    exist_m = len(m) > 0
    remain_P = len(P) - 1 > len(p)
    remain_M = len(M) - 1 > len(m)
    if exist_p & remain_M & exist_m & remain_P:
        if abs(p[-1] * P[len(p)]) < abs(m[-1] * M[len(m)]):
            p.pop()
            m.append(M[len(m)])
        else:
            m.pop()
            p.append(P[len(p)])
    elif exist_p & remain_M:
        p.pop()
        m.append(M[len(m)])
    elif exist_m & remain_P:
        m.pop()
        p.append(P[len(p)])
    else:
        M.pop() # del endpoint
        m = sorted(M, reverse = True)[:k]
    return p + m

n, k = map(int, input().split())
P, M = [], [] # plus, minus
for a in map(int, input().split()):
    if a < 0: M.append(a)
    else: P.append(a)
ans, MOD = 1, 10**9 + 7
for a in solve(): ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def solve():
    P.sort(reverse = True)
    M.sort()
    P.append(-1)
    M.append(1) # add endpoint
    p, m = [], []
    while len(p) + len(m) < k:
        if P[len(p)] < -M[len(m)]:
            m.append(M[len(m)])
        else:
            p.append(P[len(p)])
    if len(m)%2 == 0: return p + m

    exist_p = len(p) > 0
    exist_m = len(m) > 0
    remain_P = len(P) - 1 > len(p)
    remain_M = len(M) - 1 > len(m)
    if exist_p & exist_m & remain_P & remain_M:
        if abs(p[-1] * P[len(p)]) < abs(m[-1] * M[len(m)]):
            p.pop()
            m.append(M[len(m)])
        else:
            m.pop()
            p.append(P[len(p)])
    elif exist_m & remain_P:
        m.pop()
        p.append(P[len(p)])
    elif exist_p & remain_M:
        p.pop()
        m.append(M[len(m)])
    else:
        M.pop() # del endpoint
        m = sorted(M, reverse = True)[:k]
    return p + m

n, k = map(int, input().split())
P, M = [], [] # plus, minus
for a in map(int, input().split()):
    if a < 0: M.append(a)
    else: P.append(a)
ans, MOD = 1, 10**9 + 7
for a in solve(): ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def solve():
    P.sort(reverse = True)
    M.sort()
    P.append(-1)
    M.append(1) # add endpoint
    p, m = [], []
    while len(p) + len(m) < k:
        if P[len(p)] < -M[len(m)]:
            m.append(M[len(m)])
        else:
            p.append(P[len(p)])

    if len(m)%2 == 0: return p + m

    exist_p = len(p) > 0
    exist_m = len(m) > 0
    remain_P = len(P) - 1 > len(p)
    remain_M = len(M) - 1 > len(m)
    if exist_p & exist_m & remain_P & remain_M:
        if abs(p[-1] * P[len(p)]) < abs(m[-1] * M[len(m)]):
            p.pop()
            m.append(M[len(m)])
        else:
            m.pop()
            p.append(P[len(p)])
    elif exist_m & remain_P:
        m.pop()
        p.append(P[len(p)])
    elif exist_p & remain_M:
        p.pop()
        m.append(M[len(m)])
    elif k%2:
        M.pop()
        m = sorted(M, reverse = True)[:k]
    return p + m

n, k = map(int, input().split())
P, M = [], [] # plus, minus
for a in map(int, input().split()):
    if a < 0: M.append(a)
    else: P.append(a)
ans, MOD = 1, 10**9 + 7
for a in solve(): ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def solve():
    if k == n: return P + M

    P.sort(reverse = True)
    M.sort()
    P.append(-1)
    M.append(1) # add endpoint
    p, m = [], []
    while len(p) + len(m) < k:
        if P[len(p)] < -M[len(m)]:
            m.append(M[len(m)])
        else:
            p.append(P[len(p)])

    if len(m)%2 == 0: return p + m

    exist_p = len(p) > 0
    exist_m = len(m) > 0
    remain_P = len(P) - 1 > len(p)
    remain_M = len(M) - 1 > len(m)
    if exist_p & exist_m & remain_P & remain_M:
        if abs(p[-1] * P[len(p)]) < abs(m[-1] * M[len(m)]):
            p.pop()
            m.append(M[len(m)])
        else:
            m.pop()
            p.append(P[len(p)])
    elif exist_m & remain_P:
        m.pop()
        p.append(P[len(p)])
    elif exist_p & remain_M:
        p.pop()
        m.append(M[len(m)])
    elif k%2:
        M.pop()
        m = sorted(M, reverse = True)[:k]

    return p + m

n, k = map(int, input().split())
P, M = [], [] # plus, minus
for a in map(int, input().split()):
    if a < 0: M.append(a)
    else: P.append(a)
ans, MOD = 1, 10**9 + 7
for a in solve(): ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def solve():
    if k==n: return P + M
    if len(M) == n: return sorted(M, reverse=k%2)[:k]

    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) - 1 > len(pa)
    remain_m = len(M) - 1 > len(ma)
    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

n, k = map(int, input().split())
P, M = [], [] # plus, minus
for a in map(int, input().split()):
    if a < 0: M.append(a)
    else: P.append(a)
ans, MOD = 1, 10**9 + 7
for a in solve(): ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def solve():
    if k==n: return A
    if len(M) == n: return sorted(M, reverse=k%2)[:k]

    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) - 1 > len(pa)
    remain_m = len(M) - 1 > len(ma)
    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

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)
ans, MOD = 1, 10**9 + 7
for a in solve(): ans *= a; ans %= MOD
ans += MOD; ans %= MOD
print(ans)

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); remain_m = len_m > len(ma)
    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:
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); remain_m = len_m > len(ma)
    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:
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); remain_m = len_m > len(ma)
    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)])
        return pa + ma
    if exist_ma & remain_p:
        ma.pop(); pa.append(P[len(pa)])
        return pa + ma
    if exist_pa & remain_m:
        pa.pop(); ma.append(M[len(ma)])
        return pa + 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)