Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

We will choose exactly K of these elements. Find the maximum possible product of the chosen elements.

Then, print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Constraints

1 \leq K \leq N \leq 2\times 10^5

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

Print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

The possible products of the two chosen elements are 2, -3, -4, -6, -8, and 12, so the maximum product is 12.

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

The possible products of the three chosen elements are -24, -12, -8, and -6, so the maximum product is -6.

We print this value modulo (10^9+7), that is, 1000000001.

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

The possible products of the one chosen element are -1 and 1000000000, so the maximum product is 1000000000.

Sample Input 4

10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1

Sample Output 4

999983200

Be sure to print the product modulo (10^9+7).



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Wrong Answer

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K = map(int, readline().split())
A = list(map(int,readline().split()))
MOD = 10**9 +7
B = []
C = []
for a in A:
    if a >= 0:
        B.append(a)
    else:
        C.append(-a)

ans = 1
if len(B) == 0:
    C = sorted(C)
    for i in range(K):
        ans *= C[i]
        ans %= MOD
    if K % 2 == 1:
        ans *= -1
        ans %= MOD
    print(ans)
    sys.exit()
      
negs_p = 0
non_negs_p = 0
for i in range(K):
    if negs_p == len(C):
        non_negs_p += 1
    elif non_negs_p == len(B):
        negs_p += 1
    elif C[negs_p] > B[non_negs_p]:
        negs_p += 1
    else:
        non_negs_p += 1
B = sorted(B,reverse = True)
C = sorted(C,reverse = True)

if N == K or negs_p % 2 == 0:
    for i in range(non_negs_p):
        ans = ans * B[i] % MOD
    for i in range(negs_p):
        ans = ans * -C[i] % MOD
    print(ans)
    sys.exit()

if negs_p % 2 == 1:
    if negs_p == len(C) or non_negs_p == 0:
        negs_p -= 1
        non_negs_p += 1 
        for i in range(non_negs_p):
            ans = ans * B[i] % MOD
        for i in range(negs_p):
            ans = ans * -C[i] % MOD
    elif non_negs_p == len(B) or negs_p == 0:
        negs_p += 1
        non_negs_p -= 1 
        for i in range(non_negs_p):
            ans = ans * B[i] % MOD
        for i in range(negs_p):
            ans = ans * -C[i] % MOD
    else:
        a,b,c,d = C[negs_p],C[negs_p-1],B[non_negs_p],B[non_negs_p-1]
        if a*b > c*d:
            negs_p += 1
            non_negs_p -= 1
        else:   
            negs_p -= 1
            non_negs_p += 1
        for i in range(non_negs_p):
            ans = ans * B[i] % MOD
        for i in range(negs_p):
            ans = ans * -C[i] % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K = map(int, readline().split())
A = list(map(int,readline().split()))
MOD = 10**9 +7
B = []
C = []
BC = []
for a in A:
    if a >= 0:
        B.append(a)
        BC.append(a)
    else:
        C.append(-a)
        BC.append(-a)
ans = 1
if len(B) == 0:
    C = sorted(C)
    for i in range(K):
        ans *= C[i]
        ans %= MOD
    if K % 2 == 1:
        ans *= -1
        ans %= MOD
    print(ans)
    sys.exit()
      
negs_p = 0
non_negs_p = 0
for i in range(K):
    if negs_p == len(C):
        non_negs_p += 1
    elif non_negs_p == len(B):
        negs_p += 1
    elif C[negs_p] > B[non_negs_p]:
        negs_p += 1
    else:
        non_negs_p += 1
B = sorted(B,reverse = True)
C = sorted(C,reverse = True)
BC = sorted(BC,reverse = True)
if N == K or negs_p % 2 == 0:
    for i in range(non_negs_p):
        ans = ans * B[i] % MOD
    for i in range(negs_p):
        ans = ans * -C[i] % MOD
    print(ans)
    sys.exit()

if negs_p % 2 == 1:
    if negs_p == len(C) or non_negs_p == 0:
        negs_p -= 1
        non_negs_p += 1 
        for i in range(non_negs_p):
            ans = ans * B[i] % MOD
        for i in range(negs_p):
            ans = ans * C[i] % MOD
    elif non_negs_p == len(B) or negs_p == 0:
        negs_p += 1
        non_negs_p -= 1 
        for i in range(non_negs_p):
            ans = ans * B[i] % MOD
        for i in range(negs_p):
            ans = ans * C[i] % MOD
    else:
        a,b,c,d = C[negs_p],C[negs_p-1],B[non_negs_p],B[non_negs_p-1]
        if a*b > c*d:
            negs_p += 1
            non_negs_p -= 1
        else:   
            negs_p -= 1
            non_negs_p += 1
        for i in range(non_negs_p):
            ans = ans * B[i] % MOD
        for i in range(negs_p):
            ans = ans * C[i] % MOD
print(ans)

Submission status: Wrong Answer

Solution code:

INF = 10 ** 9 + 7
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

if K == 1:
    print(a[0])
    exit()

if K == N:
    ans = 1
    for i in a:
        ans *= i
        ans %= INF
    print(ans)
    exit()

if a[0] < 0:
    ans = 1
    if K % 2 == 1:
        for i in range(K):
            ans *= a[i]
            ans %= INF
    else:
        for i in range(K):
            ans *= a[-i - 1]
            ans %= INF
    print(ans)
    exit()

sei = []
hu = []
for i in a:
    if i >= 0:
        sei.append(i)
    else:
        hu.append(i)

seis = []
hus = []
total = []
ans = 1
if K % 2 != 0 and len(hus) > 1:
    ans = sei[0] % INF
    for i in range(2, len(sei), 2):
        seis.append(sei[i] * sei[i - 1] % INF)
else:
    for i in range(1, len(sei), 2):
        seis.append(sei[i] * sei[i - 1] % INF)
for i in range(1, len(hu), 2):
    hus.append(hu[i] * hu[i - 1] % INF)

total = seis + hus
total.sort(reverse=True)

for i in range(K // 2):
    ans *= total[i]
    ans %= INF

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline

def answer(lst):
    ans=1
    for i in lst:
        gomi,ans=divmod(ans*i,1000000007)
    print(ans)
    exit()

n,k=map(int,input().split())
if n==k:
    lst=list(map(int,input().split()))
    answer(lst)

plus=[]
minus=[]
lst=list(map(int,input().split()))
for i in range(n):
    if lst[i]>=0:
        plus.append(lst[i])
    else:
        minus.append(lst[i])

if len(minus)==n:
    if k%2==1:
        lst=sorted(lst,reverse=True)
        answer(lst[:k])
    else:
        lst=sorted(lst)
        answer(lst[:k])

lst=sorted(lst,key=lambda x:abs(x),reverse=True)
temp_lst=lst[:k]
minus_count=0
for i in temp_lst:
    if i<0:
        minus_count+=1
if minus_count%2==0:
    answer(temp_lst)
else:
    for i in range(k-1,-1,-1):
        if temp_lst[i]<0:
            temp_lst.remove(temp_lst[i])
            break
    for i in range(k,n):
        if lst[i]>=0:
            temp_lst.append(lst[i])
            break
    answer(temp_lst)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jul  5 21:49:24 2020

@author: NEC-PCuser
"""

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

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

A.sort()

minus_list = []
plus_list = []
for i in range(len(A)):
    if (A[i] <= 0):
        minus_list.append(A[i])
    else:
        plus_list.append(A[i])

ans = 1
mod = 10 ** 9 + 7   
if N == K:
    for i in A:
        ans = (ans * i) % mod
elif 0 == len(plus_list) and  K % 2 == 1:
    minus_list.sort(reverse=True)
    for i in range(K):
        ans = (ans * minus_list[i]) % mod
else:
    minus_list.sort()
    plus_list.sort(reverse=True)
    if K % 2 == 1:
        ans = plus_list.pop(0)
    print(ans)
    for i in range(K // 2):
        if (len(plus_list) < 2):
            ans = (minus_list.pop(0) * ans) % mod
            ans = (minus_list.pop(0) * ans) % mod
        elif (len(minus_list) < 2):
            ans = (plus_list.pop(0) * ans) % mod
            ans = (plus_list.pop(0) * ans) % mod
        elif (plus_list[0] * plus_list[1] > minus_list[0] * minus_list[1]):
            ans = (plus_list.pop(0) * ans) % mod
            ans = (plus_list.pop(0) * ans) % mod
        else:
            ans = (minus_list.pop(0) * ans) % mod
            ans = (minus_list.pop(0) * ans) % mod
        print(ans)

print(ans)

Submission status: Wrong Answer

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

MOD = 10 ** 9 + 7

AA = sorted(A, key=lambda x: -abs(x))

nega1 = []
posi1 = []
for a in AA[:k]:
  if a < 0:
    nega1.append(a)
  else:
    posi1.append(a)

nega2 = []
posi2 = []
for a in AA[k:]:
  if a < 0:
    nega2.append(a)
  else:
    posi2.append(a)

if all(a < 0 for a in A) and k % 2 == 1:
  AA = sorted(A, key=lambda x: abs(x))
  nega1 = []
  posi1 = []
  for a in AA[:k]:
    nega1.append(a)

elif n == k:
  pass

elif len(nega1) % 2 != 0:
  if posi1 and nega2 and posi2:
    if abs(nega1[-1] * nega2[0]) > abs(posi1[-1] * posi2[0]):
      del nega1[-1]
      nega1.append(posi2[0])
    else:
      del posi1[-1]
      posi1.append(nega2[0])
  elif not posi1 or not nega2:
    del nega1[-1]
    nega1.append(posi2[0])
  elif not posi2:
    del posi1[-1]
    posi1.append(nega2[0])
  
a = 1
for m in posi1:
  a = (a * m) % MOD
for p in nega1:
  a = (a * p) % MOD
 
print(a)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jul  5 21:49:24 2020

@author: NEC-PCuser
"""

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

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

A.sort()

minus_list = []
plus_list = []
for i in range(len(A)):
    if (A[i] <= 0):
        minus_list.append(A[i])
    else:
        plus_list.append(A[i])

ans = 1
mod = 10 ** 9 + 7   
if N == K:
    for i in A:
        ans = (ans * i) % mod
elif 0 == len(plus_list) and  K % 2 == 1:
    minus_list.sort(reverse=True)
    for i in range(K):
        ans = (ans * minus_list[i]) % mod
else:
    minus_list.sort()
    plus_list.sort(reverse=True)
    if K % 2 == 1:
        ans = plus_list.pop()
    print(ans)
    for i in range(K // 2):
        if (len(plus_list) < 2):
            ans = (minus_list.pop(0) * ans) % mod
            ans = (minus_list.pop(0) * ans) % mod
        elif (len(minus_list) < 2):
            ans = (plus_list.pop(0) * ans) % mod
            ans = (plus_list.pop(0) * ans) % mod
        elif (plus_list[0] * plus_list[1] > minus_list[0] * minus_list[1]):
            ans = (plus_list.pop(0) * ans) % mod
            ans = (plus_list.pop(0) * ans) % mod
        else:
            ans = (minus_list.pop(0) * ans) % mod
            ans = (minus_list.pop(0) * ans) % mod
        print(ans)

print(ans)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     

def pow(x, n):
    ans = 1
    while(n > 0):
        if(bin(n & 1) == bin(1)):
            ans = ans*x
            ans %= mod
        x = x*x
        x %= mod
        n = n >> 1
    return ans

def gyaku(n):
    return pow(n, mod-2)

def main():
    N, K = LI()
    A = LI()
    sort_A = []
    for a in A:
        sort_A.append((abs(a), a))
    sort_a = sorted(sort_A, key=lambda x: x[0])[::-1]
    all_neg = True
    for a in A:
        if a >= 0:
            all_neg = False
            break
    if K % 2 == 1:
        if all_neg:
            ans = 1
            for a in A[:K]:
                ans *= a
                ans %= mod
            print(ans)
            return

    ans = 1
    plus = True
    for pair in sort_a[:K]:
        if pair[1] < 0:
            plus = not plus
        ans *= pair[1]
        ans %= mod
    if plus:
        print(ans)
        return

    pright = -inf
    nright = -inf
    pleft = -inf
    nleft = -inf

    for i in range(K, N):
        e = sort_A[i][1]
        if e >= 0:
            pright = e
            break

    for i in range(K, N):
        e = sort_A[i][1]
        if e < 0:
            nright = e
            break

    for i in range(K)[::-1]:
        e = sort_A[i][1]
        if e < 0:
            nleft = e
            break

    for i in range(K)[::-1]:
        e = sort_A[i][1]
        if e >= 0:
            pleft = e
            break
    c1, c2 = -inf, -inf
    if pright != -inf and nleft != -inf:
        c1 = ans
        c1 *= gyaku(pleft)
        c1 %= mod
        c1 *= nright

    elif pleft != -inf and nright != -inf:
        c2 = ans
        c2 *= gyaku(nleft)
        c2 %= mod
        c2 *= pright
    else:
        pass
    ans = max(ans, max(c1, c2))
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
z=-1
p=-1
mod=10**9+7
ans=1
for i in range(n):
    if a[i]==0:
        z=i
    elif a[i]>0:
        p=i
        break
a_abs=sorted(a,key=abs,reverse=True)
if p==-1 or n==k:
    for i in range(k):
        ans*=a[n-1-i]
    print(ans%mod)
else:
    lp=-1
    lm=-1
    for i in range(k):
        ans*=a_abs[i]
        if a_abs[i]>=0:
            lp=i
        else:
            lm=i
    if ans>=0:
        print(ans%mod)
    else:
        fp=-1
        fm=-1
        check_p=False
        check_m=False
        for i in range(k,n):
            if not check_p and a_abs[i]>=0:
                fp=i
                check_p=True
            elif not check_m and a_abs[i]<0:
                fm=i
                check_m=True
            if check_m and check_p:
                break
        if lp!=-1:
            if fp==-1:
                ans=ans//a_abs[lp]*a_abs[fm]
            elif fm==-1:
                ans=ans//a_abs[lm]*a_abs[fp]
            else:
                if a_abs[fm]*a_abs[lm]>=a_abs[fp]*a_abs[lp]:
                    ans=ans//a_abs[lp]*a_abs[fm]
                else:
                    ans=ans//a_abs[lm]*a_abs[fp]
        else:
            ans=ans//a_abs[lm]*a_abs[fp]
        print(ans%mod)

Submission status: Wrong Answer

Solution code:
from collections import deque
MOD = 10 ** 9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(key=lambda x: abs(x), reverse=True)
res = 1
cnt = sum(1 if a <= 0 else 0 for a in A)
if cnt == N:
    if K % 2 == 0:
        for a in A[:K]:
            res *= a
            res %= MOD
    else:
        for a in A[N-1:N-K-1:-1]:
            res *= a
            res %= MOD
else:
    plus = MOD
    minus = -MOD
    cnt = 0
    for a in A[:K]:
        res *= a
        if a > 0:
            plus = a
        else:
            cnt += 1
            minus = a
    if cnt % 2 == 1:
        p = -1
        m = 1
        for a in A[K:]:
            if a >= 0 and p < 0:
                p = a
            if a < 0 and m > 0:
                m = a
            if p >= 0 and m < 0:
                break
        if plus * p < minus * m:
            res *= pow(plus, MOD-2, MOD)
            res %= MOD
            res *= m
            res %= MOD
        else:
            res *= pow(minus, MOD-2, MOD)
            res %= MOD
            res *= p
            res %= MOD
print(res)

Submission status: Wrong Answer

Solution code:

INF = 10 ** 9 + 7
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

if K == 1:
    print(a[0])
    exit()

if K == N:
    ans = 1
    for i in a:
        ans *= i
        ans %= INF
    print(ans)
    exit()

if a[0] < 0:
    ans = 1
    if K % 2 == 1:
        for i in range(K):
            ans *= a[i]
            ans %= INF
    else:
        for i in range(K):
            ans *= a[-i - 1]
            ans %= INF
    print(ans)
    exit()

sei = []
hu = []
for i in a:
    if i >= 0:
        sei.append(i)
    else:
        hu.append(i)

seis = []
hus = []
total = []
ans = 1
if K % 2 != 0:
    ans = sei[0] % INF
    for i in range(2, len(sei), 2):
        seis.append(sei[i] * sei[i - 1] % INF)
else:
    for i in range(1, len(sei), 2):
        seis.append(sei[i] * sei[i - 1] % INF)
for i in range(1, len(hu), 2):
    hus.append(hu[i] * hu[i - 1] % INF)

total = seis + hus
total.sort(reverse=True)

for i in range(K // 2):
    ans *= total[i]
    ans %= INF

print(ans)

Submission status: Wrong Answer

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(k):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()
minus=[i for i in a if i<0]
plus=[i for i in a if i>=0]
from collections import deque
minus=deque(sorted(minus))
plus=deque(sorted(plus,reverse=True))

n_minus=len(minus)
n_plus=len(plus)
if n_minus==n:
    ans=1
    if k%2==0:
        for i in range(k):
            ans*=minus.popleft()
            ans+=mod
            ans%=mod
        print(ans)
        exit()
    else:
        for i in range(k):
            ans*=minus.pop()
            ans+=mod
            ans%=mod
        print(ans)
        exit()

ans=1
while k>1:
    if n_minus>1 and n_plus>1:
        if minus[0]*minus[1]>=plus[0]*plus[1]:
            n_minus-=2
            k-=2
            for _ in range(2):
                ans*=minus.popleft()
                ans%=mod
        else:
            n_plus-=2
            k-=2
            for _ in range(2):
                ans*=plus.popleft()
                ans%=mod
    elif n_minus>1:
        n_minus-=2
        k-=2
        for _ in range(2):
            ans*=minus.popleft()
            ans%=mod
    elif n_plus>1:
        n_plus-=2
        k-=2
        for _ in range(2):
            ans*=plus.popleft()
            ans%=mod

if k==1:
    if plus:
        ans*=plus.popleft()
        ans%=mod


print(ans)

Submission status: Wrong Answer

Solution code:
n, k = [int(x) for x in input().split()]
l = [int(x) for x in input().split()]
p = list(filter(lambda x: x>=0, l))
n = list(filter(lambda x: x<0, l))
p.sort()
n.sort()
pIndex = len(p)-1
nIndex = len(n)-1
ans = 1
nThere = True

if pIndex>0:
    pp = p[pIndex]*p[pIndex-1]
else:
    pp=-1
    
if nIndex>0:
    np = n[nIndex]*n[nIndex-1]
else:
    np = 1
    nThere = False
    
while(k>0):
    if k>1 and nThere:
        k-=2
        if np>pp:
            ans*=np%1000000007
            nIndex-=2
            if nIndex>0:
                np=n[nIndex]*n[nIndex-1]
            else:
             	nThere = False
        else:
            ans*=pp%1000000007
            pIndex-=2
            if pIndex>0:
                pp=p[pIndex]*p[pIndex-1]
            else:
              	pp=-1
    elif pIndex>-1:
        k-=1
        ans*=p[pIndex]%1000000007
        pIndex-=1
        if pIndex>0:
                pp=p[pIndex]*p[pIndex-1]
        else:
          		pp=-1
    else:
        k-=1
        ans*=n[nIndex]%1000000007
        nIndex-=1
        
print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jul  5 21:49:24 2020

@author: NEC-PCuser
"""

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

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

A.sort()

minus_list = []
plus_list = []
for i in range(len(A)):
    if (A[i] <= 0):
        minus_list.append(A[i])
    else:
        plus_list.append(A[i])

ans = 1
mod = 10 ** 9 + 7   
if N == K:
    for i in A:
        ans = (ans * i) % mod
elif 0 == len(plus_list) and  K % 2 == 1:
    minus_list.sort(reverse=True)
    for i in range(K):
        ans = (ans * minus_list[i]) % mod
else:
    minus_list.sort()
    plus_list.sort(reverse=True)
    if K % 2 == 1:
        ans = plus_list.pop()
    for i in range(K // 2):
        if (len(plus_list) < 2):
            ans = (minus_list.pop() * ans) % mod
            ans = (minus_list.pop() * ans) % mod
        elif (len(minus_list) < 2):
            ans = (plus_list.pop() * ans) % mod
            ans = (plus_list.pop() * ans) % mod
        elif (plus_list[0] * plus_list[1] > minus_list[0] * minus_list[1]):
            ans = (plus_list.pop() * ans) % mod
            ans = (plus_list.pop() * ans) % mod
        else:
            ans = (minus_list.pop() * ans) % mod
            ans = (minus_list.pop() * ans) % mod

print(ans)

Submission status: Wrong Answer

Solution code:

INF = 10 ** 9 + 7
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

if K == 1:
    print(a[0])
    exit()

if K == N:
    ans = 1
    for i in a:
        ans *= i
        ans %= INF
    print(ans)
    exit()

if a[0] < 0:
    ans = 1
    if K % 2 == 1:
        for i in range(K):
            ans *= a[i]
            ans %= INF
    else:
        for i in range(K):
            ans *= a[-i - 1]
            ans %= INF
    print(ans)
    exit()

sei = []
hu = []
for i in a:
    if i >= 0:
        sei.append(i)
    else:
        hu.append(i)

seis = []
hus = []
total = []
ans = 1
if K % 2 != 0:
    ans = sei[0] % INF
    for i in range(2, len(sei)):
        seis.append(sei[i] * sei[i - 1] % INF)
else:
    for i in range(1, len(sei)):
        seis.append(sei[i] * sei[i - 1] % INF)
for i in range(1, len(hu)):
    hus.append(hu[i] * hu[i - 1] % INF)

total = seis + hus
total.sort(reverse=True)

for i in range(K // 2):
    ans *= total[i]
    ans %= INF

print(ans)

Submission status: Wrong Answer

Solution code:
###==================================================
### import
import bisect
#from collections import Counter, deque, defaultdict
#from copy import deepcopy
#from functools import reduce, lru_cache
#from heapq import heappush, heappop
#import itertools
#import math
#import string
import sys
### stdin
def input(): return sys.stdin.readline().rstrip()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip('\n') for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]
### stdout
def OutH(lst, deli=' '): print(deli.join(map(str, lst)))
def OutV(lst): print('\n'.join(map(str, lst)))
### setting
sys.setrecursionlimit(10 ** 6)
### utils
int1 = lambda x: int(x) - 1
### constants
INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)
###---------------------------------------------------

N, K = iInM()
A = iInLH()

A.sort(key=lambda x: abs(x), reverse=True)

if N == K:
    ans = 1
    for i in range(K):
        ans = ans * A[i] % MOD
    print(ans)
    exit()
elif len([x for x in A if x < 0]) == N:
    ans = 1
    for i in range(K):
        ans = ans * A[N-1-i] % MOD
    print(ans)
    exit()

ans = 1
n_minus = 0
min_plus = -1
min_minus = 1
for i in range(K):
    ans = ans * A[i] % MOD
    if A[i] > 0:
        min_plus = A[i]
    elif A[i] < 0:
        min_minus = A[i]
        n_minus += 1
    else:
        ans = 0
        print(0)
        exit()
if n_minus % 2 == 0:
    print(ans)
    exit()
else:
    ## K番目以降を探してプラスとマイナスのものを見つけにいく
    next_plus = -1
    next_minus = 1
    for i in range(K, N):
        if A[i] >= 0:
            next_plus = A[i]
            break
    for i in range(K, N):
        if A[i] <= 0:
            next_minus = A[i]
            break
    ## これから数の入れ替えを行う
    if min_plus == -1: ## 初めのK個にplusがない場合
        ans = ans * pow(min_minus, MOD-2, MOD) * next_plus % MOD
    elif min_minus == 1: ## 初めのK個にminusがない場合 ## てかこれそもそもありえない
        ans = ans * pow(min_plus, MOD-2, MOD) * next_minus % MOD
    else: ## 初めのK個にplusもminusもある場合
        ## ここまでで必ずmin_plus>0, min_minus<0, next_plus>=0, next_minus<=0
        if next_plus * min_plus <= next_minus * min_minus:
            ans = ans * pow(min_minus, MOD-2, MOD) * next_plus % MOD
        else:
            ans = ans * pow(min_plus, MOD-2, MOD) * next_minus % MOD
    #print(min_plus, min_minus, next_plus, next_minus)
    print(ans)

Submission status: Wrong Answer

Solution code:

INF = 10 ** 9 + 7
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

if K == 1:
    print(a[0])
    exit()

if K == N:
    ans = 1
    for i in a:
        ans *= i
        ans %= INF
    print(ans)
    exit()

if a[0] < 0:
    ans = 1
    if K % 2 == 1:
        for i in range(K):
            ans *= a[i]
            ans %= INF
    else:
        for i in range(K):
            ans *= a[-i - 1]
            ans %= INF
    print(ans)
    exit()

sei = []
hu = []
for i in a:
    if i >= 0:
        sei.append(i)
    else:
        hu.append(i)

seis = []
hus = []
total = []
ans = 1
if K % 2 != 0:
    ans = sei[0] % INF
    for i in range(2, len(sei)):
        seis.append(sei[i] * sei[i - 1] % INF)
else:
    for i in range(1, len(sei)):
        seis.append(sei[i] * sei[i - 1] % INF)
for i in range(1, len(hu)):
    hus.append(hu[i] * hu[i - 1] % INF)

total = seis + hus
total.sort(reverse=True)

for i in range(K // 2):
    print(total[i])
    ans *= total[i]
    ans %= INF

print(ans)

Submission status: Wrong Answer

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K = map(int, readline().split())
A = list(map(int,readline().split()))
MOD = 10**9 +7
B = []
C = []
BC = []
for a in A:
    if a >= 0:
        B.append(a)
        BC.append(a)
    else:
        C.append(-a)
        BC.append(-a)
ans = 1
if len(B) == 0:
    C = sorted(C)
    for i in range(K):
        ans *= C[i]
        ans %= MOD
    if K % 2 == 1:
        ans *= -1
        ans %= MOD
    print(ans)
    sys.exit()
if N == K:
    for i in range(K):
        ans *= BC[i]
        ans %= MOD
    if len(C) % 2 == 1:
        ans *= -1
        ans %= MOD
    print(ans)
    sys.exit()  
negs_p = 0
non_negs_p = 0
for i in range(K):
    if negs_p == len(C):
        non_negs_p += 1
    elif non_negs_p == len(B):
        negs_p += 1
    elif C[negs_p] > B[non_negs_p]:
        negs_p += 1
    else:
        non_negs_p += 1
B = sorted(B,reverse = True)
C = sorted(C,reverse = True)
BC = sorted(BC,reverse = True)

for i in range(K):
    ans *= BC[i]
    ans %= MOD

if negs_p % 2 == 1:
    if negs_p == len(C) or non_negs_p == 0:      
        b,c = C[negs_p-1],B[non_negs_p]
        ans = (ans*MOD // b) * c % MOD
    elif non_negs_p == len(B) or negs_p == 0:
        a,d = C[negs_p],B[non_negs_p-1]
        ans = (ans*MOD // d) * a % MOD
    else:
        a,b,c,d = C[negs_p],C[negs_p-1],B[non_negs_p],B[non_negs_p-1]
        if a*b > c*d:
            ans = (ans*MOD // d) * a % MOD
        else:
            ans = (ans*MOD // b) * c % MOD
print(ans)

Submission status: Wrong Answer

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(k):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()
minus=[i for i in a if i<0]
plus=[i for i in a if i>=0]
from collections import deque
minus=deque(sorted(minus))
plus=deque(sorted(plus,reverse=True))

n_minus=len(minus)
n_plus=len(plus)
if n_minus==n:
    ans=1
    if k%2==0:
        for i in range(k):
            ans*=minus.popleft()
            ans+=mod
            ans%=mod
        print(ans)
        exit()
    else:
        for i in range(k):
            ans*=minus.pop()
            ans+=mod
            ans%=mod
        print(ans)
        exit()

ans=1
while k>1:
    if n_minus>1 and n_plus>1:
        if minus[0]*minus[1]>plus[0]*plus[1]:
            n_minus-=2
            k-=2
            for _ in range(2):
                ans*=minus.popleft()
                ans%=mod
        else:
            n_plus-=2
            k-=2
            for _ in range(2):
                ans*=plus.popleft()
                ans%=mod
    elif n_minus>1:
        n_minus-=2
        k-=2
        for _ in range(2):
            ans*=minus.popleft()
            ans%=mod
    elif n_plus>1:
        n_plus-=2
        k-=2
        for _ in range(2):
            ans*=plus.popleft()
            ans%=mod

if k==1:
    if plus:
        ans*=plus.popleft()
        ans%=mod

print(ans)

Submission status: Wrong Answer

Solution code:
###==================================================
### import
import bisect
#from collections import Counter, deque, defaultdict
#from copy import deepcopy
#from functools import reduce, lru_cache
#from heapq import heappush, heappop
#import itertools
#import math
#import string
import sys
### stdin
def input(): return sys.stdin.readline().rstrip()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip('\n') for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]
### stdout
def OutH(lst, deli=' '): print(deli.join(map(str, lst)))
def OutV(lst): print('\n'.join(map(str, lst)))
### setting
sys.setrecursionlimit(10 ** 6)
### utils
int1 = lambda x: int(x) - 1
### constants
INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)
###---------------------------------------------------

N, K = iInM()
A = iInLH()

A.sort(key=lambda x: abs(x), reverse=True)

if N == K:
    ans = 1
    for i in range(K):
        ans = ans * A[i] % MOD
    print(ans)
    exit()
elif len([x for x in A if x < 0]) == N:
    ans = 1
    for i in range(K):
        ans = ans * A[N-1-i] % MOD
    print(ans)
    exit()

ans = 1
n_minus = 0
min_plus = -1
min_minus = 1
for i in range(K):
    ans = ans * A[i] % MOD
    if A[i] > 0:
        min_plus = A[i]
    elif A[i] < 0:
        min_minus = A[i]
        n_minus += 1
    else:
        ans = 0
        print(0)
        exit()
if n_minus % 2 == 0:
    print(ans)
    exit()
else:
    ## K番目以降を探してプラスとマイナスのものを見つけにいく
    next_plus = -1
    next_minus = 1
    for i in range(K, N):
        if A[i] >= 0:
            next_plus = A[i]
            break
    for i in range(K, N):
        if A[i] <= 0:
            next_minus = A[i]
            break
    ## これから数の入れ替えを行う
    if min_plus == -1: ## 初めのK個にplusがない場合
        ans = ans * pow(min_minus, MOD-2, MOD) * next_plus % MOD
    elif min_minus == 1: ## 初めのK個にminusがない場合 ## てかこれそもそもありえない
        ans = ans * pow(min_plus, MOD-2, MOD) * next_minus % MOD
    else: ## 初めのK個にplusもminusもある場合
        ## ここまでで必ずmin_plus>0, min_minus<0, next_plus>=0, next_minus<=0
        if next_plus * min_plus >= next_minus * min_minus:
            ans = ans * pow(min_minus, MOD-2, MOD) * next_plus % MOD
            ans = 1
        else:
            ans = ans * pow(min_plus, MOD-2, MOD) * next_minus % MOD
    #print(min_plus, min_minus, next_plus, next_minus)
    print(ans)