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:
n,k=map(int, input().split())
a=sorted(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)
elif a[-1]<0 and k%2==1:
    ans=1
    a.sort(reverse=True)
    for i in range(k):
        ans*=a[i]
        ans%=mod
    print(ans)
else:
    a.sort(key=abs, reverse=True)
    ans=1
    for i in range(k):
        ans*=a[i]
        ans%=mod
    if ans>=0:
        print(ans)
    else:
        # 負の数を1つ取り除く
        tmp_i=0
        for i in range(k-1,0,-1):
            if a[i]<0:
                tmp_i=i
        # 正の数を1つ追加
        tmp_j=n-1
        for i in range(k,n):
            if a[i]>0:
                tmp_j=i
        ans1=1
        for i in range(k):
            if i!=tmp_i:
                ans1*=a[i]
                ans1%=mod
        ans1*=a[tmp_j]
        ans1%=mod

        # 正の数を1つ取り除く
        tmp_i=0
        for i in range(k-1,0,-1):
            if a[i]>0:
                tmp_i=i
        # 負の数を1つ追加
        tmp_j=n-1
        for i in range(k,n):
            if a[i]<0:
                tmp_j=i
        ans2=1
        for i in range(k):
            if i!=tmp_i:
                ans2*=a[i]
                ans2%=mod
        ans2*=a[tmp_j]
        ans2%=mod

        print(max(ans1, ans2))

Submission status: Wrong Answer

Solution code:
def myabs(n):
    n = int(n)
    if n>0:
        return [n,1]
    else:
        return [abs(n),-1]


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

def main(n,k,a,mod):
    flag = True
    for i in a:
        if i[1]==1:
            flag = False
            break
    if k%2==0:
        flag = False

    #All elements are negative and odd k
    if flag:
        ans = 1
        for i in range(n-1,n-1-k,-1):
            ans *= (a[i][0]*(-1))%mod
            ans %= mod 
        print(ans)
    else:
        ans = [1,1]
        neg_flag = False
        min_neg = -1
        min_pos = -1
        for i in range(k):
            if a[i][1]==-1:
                if neg_flag == True:
                    neg_flag = False
                    ans[1] *= a[i][0]
                    ans[0] = ans[1]
                else:
                    neg_flag = True
                    ans[1] *= a[i][0]
                    min_neg = i
            else:
                ans[0] *= a[i][0]
                ans[1] *= a[i][0]
                min_pos = i
            ans[0] %= mod
            ans[1] %= mod

        if neg_flag:
            next_pos = -1
            next_neg = -1
            for i in range(k,n):
                if next_pos==-1 and a[i][1]==1:
                    next_pos = a[i][0]
                elif next_neg==-1 and a[i][1]==-1:
                    next_neg = a[i][0]
                if next_pos>=0 and next_neg>=0:
                    break
            if min_pos==-1:
                ans[0] *= next_pos%mod
                ans[0] %= mod
                print(ans[0])
            elif a[min_neg][0]*next_neg>a[min_pos][0]*next_pos:
                fin_ans = 1
                for i in range(k):
                    if i!=min_pos:
                        fin_ans *= a[i][0]%mod
                        fin_ans %= mod
                fin_ans *= next_neg%mod
                fin_ans %= mod
                print(fin_ans)
            else:
                fin_ans = 1
                for i in range(k):
                    if i!=min_neg:
                        fin_ans *= a[i][0]%mod
                        fin_ans %= mod
                fin_ans *= next_pos%mod
                fin_ans %= mod
                print(fin_ans)
        else:
            print(ans[1])
            
                
    

if __name__=="__main__":
    main(N,K,A,Mod)

Submission status: Wrong Answer

Solution code:
def myabs(n):
    n = int(n)
    if n>0:
        return [n,1]
    else:
        return [abs(n),-1]


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

def main(n,k,a,mod):
    flag = True
    for i in a:
        if i[1]==1:
            flag = False
            break
    if k%2==0:
        flag = False

    #All elements are negative and odd k
    if flag:
        ans = 1
        for i in range(n-1,n-1-k,-1):
            ans *= (a[i][0]*(-1))%mod
            ans %= mod 
        print(ans)
    else:
        ans = [1,1]
        neg_flag = False
        min_neg = -1
        min_pos = -1
        for i in range(k):
            if a[i][1]==-1:
                if neg_flag == True:
                    neg_flag = False
                    ans[1] *= a[i][0]
                    ans[0] = ans[1]
                else:
                    neg_flag = True
                    ans[1] *= a[i][0]
                    min_neg = i
            else:
                ans[0] *= a[i][0]
                ans[1] *= a[i][0]
                min_pos = i
            ans[0] %= mod
            ans[1] %= mod

        if neg_flag:
            next_pos = -1
            next_neg = -1
            for i in range(k,n):
                if next_pos==-1 and a[i][1]==1:
                    next_pos = a[i][0]
                elif next_neg==-1 and a[i][1]==-1:
                    next_neg = a[i][0]
                if next_pos>=0 and next_neg>=0:
                    break
            if a[min_neg][0]*next_neg>a[min_pos][0]*next_pos:
                fin_ans = 1
                for i in range(k):
                    if i!=min_pos:
                        fin_ans *= a[i][0]%mod
                        fin_ans %= mod
                fin_ans *= next_neg%mod
                fin_ans %= mod
                print(fin_ans)
            else:
                fin_ans = 1
                for i in range(k):
                    if i!=min_neg:
                        fin_ans *= a[i][0]%mod
                        fin_ans %= mod
                fin_ans *= next_pos%mod
                fin_ans %= mod
                print(fin_ans)
        else:
            print(ans[1])
            
                
    

if __name__=="__main__":
    main(N,K,A,Mod)

Submission status: Wrong Answer

Solution code:
def myabs(n):
    n = int(n)
    if n>=0:
        return [n,1]
    else:
        return [abs(n),-1]


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

def main(n,k,a,mod):
    flag = True
    for i in a:
        if i[1]==1:
            flag = False
            break
    if k%2==0:
        flag = False

    #All elements are negative and odd k
    if flag:
        ans = 1
        for i in range(n-1,n-1-k,-1):
            ans *= a[i][0]%mod
            ans %= mod
        ans *= -1
        ans %= mod 
        print(ans)
    else:
        ans = [1,1]
        neg_flag = False
        min_neg = -1
        min_pos = -1
        for i in range(k):
            if a[i][1]==-1:
                if neg_flag == True:
                    neg_flag = False
                    ans[1] *= a[i][0]
                    ans[0] = ans[1]
                else:
                    neg_flag = True
                    ans[1] *= a[i][0]
                    min_neg = i
            else:
                ans[0] *= a[i][0]
                ans[1] *= a[i][0]
                min_pos = i
            ans[0] %= mod
            ans[1] %= mod

        if neg_flag:
            next_pos = -1
            next_neg = -1
            for i in range(k,n):
                if next_pos==-1 and a[i][1]==1:
                    next_pos = a[i][0]
                elif next_neg==-1 and a[i][1]==-1:
                    next_neg = a[i][0]
                if next_pos>=0 and next_neg>=0:
                    break
            if a[min_neg][0]*next_neg>a[min_pos][0]*next_pos:
                fin_ans = 1
                for i in range(k):
                    if i!=min_pos:
                        fin_ans *= a[i][0]%mod
                        fin_ans %= mod
                fin_ans *= next_neg%mod
                fin_ans %= mod
                print(fin_ans)
            else:
                fin_ans = 1
                for i in range(k):
                    if i!=min_neg:
                        fin_ans *= a[i][0]%mod
                        fin_ans %= mod
                fin_ans *= next_pos%mod
                fin_ans %= mod
                print(fin_ans)
        else:
            print(ans[1])
            
                
    

if __name__=="__main__":
    main(N,K,A,Mod)

Submission status: Wrong Answer

Solution code:
def myabs(n):
    n = int(n)
    if n>=0:
        return [n,1]
    else:
        return [abs(n),-1]


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

def main(n,k,a,mod):
    flag = True
    for i in a:
        if i[1]==1:
            flag = False
            break
    if k%2==0:
        flag = False

    #All elements are negative and odd k
    if flag:
        ans = 1
        for i in range(n-1,n-1-k,-1):
            ans *= (a[i][0]*(-1))%mod
            ans %= mod 
        print(ans)
    else:
        ans = [1,1]
        neg_flag = False
        min_neg = -1
        min_pos = -1
        for i in range(k):
            if a[i][1]==-1:
                if neg_flag == True:
                    neg_flag = False
                    ans[1] *= a[i][0]
                    ans[0] = ans[1]
                else:
                    neg_flag = True
                    ans[1] *= a[i][0]
                    min_neg = i
            else:
                ans[0] *= a[i][0]
                ans[1] *= a[i][0]
                min_pos = i
            ans[0] %= mod
            ans[1] %= mod

        if neg_flag:
            next_pos = -1
            next_neg = -1
            for i in range(k,n):
                if next_pos==-1 and a[i][1]==1:
                    next_pos = a[i][0]
                elif next_neg==-1 and a[i][1]==-1:
                    next_neg = a[i][0]
                if next_pos>=0 and next_neg>=0:
                    break
            if a[min_neg][0]*next_neg>a[min_pos][0]*next_pos:
                fin_ans = 1
                for i in range(k):
                    if i!=min_pos:
                        fin_ans *= a[i][0]%mod
                        fin_ans %= mod
                fin_ans *= next_neg%mod
                fin_ans %= mod
                print(fin_ans)
            else:
                fin_ans = 1
                for i in range(k):
                    if i!=min_neg:
                        fin_ans *= a[i][0]%mod
                        fin_ans %= mod
                fin_ans *= next_pos%mod
                fin_ans %= mod
                print(fin_ans)
        else:
            print(ans[1])
            
                
    

if __name__=="__main__":
    main(N,K,A,Mod)

Submission status: Wrong Answer

Solution code:
def myabs(n):
    n = int(n)
    if n>=0:
        return [n,1]
    else:
        return [abs(n),-1]


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

def main(n,k,a,mod):
    flag = True
    for i in a:
        if i[1]==1:
            flag = False
            break
    if k%2==0:
        flag = False

    #All elements are negative and odd k
    if flag:
        ans = 1
        for i in range(n-1,n-1-k,-1):
            ans *= (a[i][0]*(-1))%mod
            ans %= mod 
        print(ans)
    else:
        ans = [1,1]
        neg_flag = False
        for i in range(k):
            if a[i][1]==-1:
                if neg_flag == True:
                    neg_flag = False
                    ans[1] *= a[i][0]
                    ans[0] = ans[1]
                else:
                    neg_flag = True
                    ans[1] *= a[i][0]
            else:
                ans[0] *= a[i][0]
                ans[1] *= a[i][0]
            ans[0] %= mod
            ans[1] %= mod

        if neg_flag:
            print(ans[0])
        else:
            print(ans[1])
            
                
    

if __name__=="__main__":
    main(N,K,A,Mod)

Submission status: Wrong Answer

Solution code:
N = 10 ** 9 + 7
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

npos = sum([x > 0 for x in a])
b = [abs(x) for x in a]
b.sort()

ans = 1
if npos == 0 and k % 2 == 1:
    ans = -1
    for i in range(k):
        ans *= b[i]
        ans %= N
else:
    for i in range(k):
        ans *= b[-i-1]
        ans %= N
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = sorted(a,reverse = True)
c = sorted(a)
result1 = 1
result2 = 1
for i in range(0,k):
    result1 *= b[i]
    result2 *= c[i]
print(max(result1,result2) % (10**9+7))

Submission status: Wrong Answer

Solution code:
#E_Multiplication4
N,K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 1000000007
#ソート
arr = []
j = 0
i = 0
seki = 1
gyaku = 1
minuscount = 0
minusposition = 0

def modpow(a,n,mod):
    res = 1
    while n > 0 :
        if n & 1 :
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res
def modinv(a,mod):
    return modpow(a, mod - 2, mod)
 
arr = sorted(A,reverse = True)
 
while (i + j) < K:
    if arr[(N - j -1)] > 0 :
        seki = seki * arr[i] % MOD
        i += 1
    else:
        if arr[i] < 0 :
            if K % 2 == 0:
                minuscount += 1
                minusposition = N - j -1
                seki = seki *  arr[(N - j -1)] % MOD
                j += 1
            else:
                minuscount += 1
                minusposition = i
                seki = seki * arr[i] % MOD
                i += 1
        else:
            if (i + j + 1) < K :
                if arr[i] > (arr[(N - j -1)] * arr[(N - j -2)]):
                    seki = seki * arr[i] % MOD
                    i += 1
                else:
                    minuscount += 2
                    minusposition = N - j -2
                    seki = (seki * arr[(N - j -1)] % MOD) * arr[(N - j -2)] % MOD
                    j += 2
            else:
                if abs(arr[i]) > abs( arr[(N - j -1)]) :
                    seki = seki * arr[i] % MOD
                    i += 1
                else:               
                    minuscount += 1
                    minusposition = N - j -1
                    seki = seki * arr[(N - j -1)] % MOD
                    j += 1
if (minuscount % 2) != 0:
    if minusposition != (i - 1):
        gyaku = modinv(arr[minusposition],MOD)
        seki  = seki * gyaku % MOD
        seki  = seki * arr[i] % MOD
print(seki)

Submission status: Wrong Answer

Solution code:
#E_Multiplication4
N,K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 1000000007
#ソート
arr = []
j = 0
i = 0
seki = 1
gyaku = 1
minuscount = 0
minusposition = 0

def modpow(a,n,mod):
    res = 1
    while n > 0 :
        if n & 1 :
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res
def modinv(a,mod):
    return modpow(a, mod - 2, mod)
 
arr = sorted(A,reverse = True)
 
while (i + j) < K:
    if arr[(N - j -1)] > 0 :
        seki = seki * arr[i] % MOD
        i += 1
    else:
        if arr[i] < 0 :
            if K % 2 == 0:
                minuscount += 1
                minusposition = N - j -1
                seki = seki *  arr[(N - j -1)] % MOD
                j += 1
            else:
                minuscount += 1
                minusposition = i
                seki = seki * arr[i] % MOD
                i += 1
        else:
            if abs(arr[i]) > abs( arr[(N - j -1)]) :
                seki = seki * arr[i] % MOD
                i += 1
            else:
                minuscount += 1
                minusposition = N - j -1
                seki = seki * arr[(N - j -1)] % MOD
                j += 1
if (minuscount % 2) != 0:
    if (i - 1) != minusposition:
        gyaku = modinv(arr[minusposition],MOD)
        seki  = seki * gyaku % MOD
        seki  = seki * arr[i] % MOD
print(seki)

Submission status: Wrong Answer

Solution code:
#E_Multiplication4
N,K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 1000000007
#ソート
arr = []
j = 0
i = 0
seki = 1
gyaku = 1
minusflag  = 0
zeroflag   = 0
minuscount = 0
minusposition = 0
zerocount  = 0
zeroposition = []
hashi = 0

def modpow(a,n,mod):
    res = 1
    while n > 0 :
        if n & 1 :
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res
def modinv(a,mod):
    return modpow(a, mod - 2, mod)

arr = sorted(A,reverse = True)
 
while (1) :
    if arr[i] > 0 :
        if arr[(N - j -1)] > 0 :
            seki = seki * arr[i] % MOD
            i += 1
            hashi = 0
        else:
            if arr[(N - j -1)] == 0 :
                zeroflag = 1
                zerocount += 1
                zeroposition.append((N - j -1))
                j += 1
                hashi = 1
            else:
                if arr[(N - j -1)] < 0 :
                    if abs(arr[i]) > abs( arr[(N - j -1)]) :
                        seki = seki * arr[i] % MOD
                        i += 1
                        hashi = 0
                    else:
                        minusflag = 1
                        minuscount += 1
                        seki = seki * arr[(N - j -1)] % MOD
                        minusposition = N - j -1
                        j += 1
                        hashi = 1
    else:
        if arr[i] == 0 :
            if arr[(N - j -1)] == 0 :
                zeroflag = 1
                zerocount += 2
                zeroposition.append(i)
                zeroposition.append((N - j -1))
                i += 1
                j += 1
            else:
                if arr[(N - j -1)] < 0 :
                    zeroflag = 1
                    zerocount += 2
                    zeroposition.append(i)
                    i += 1
                    minusflag = 1
                    minuscount += 1
                    seki = seki * arr[(N - j -1)] % MOD
                    minusposition = N - j -1
                    j += 1
                    hashi = 1
        else:
            if arr[i] < 0 :
                if arr[(N - j -1)] < 0 :
                    minusflag = 1
                    minuscount += 1
                    if K % 2 == 0:
                        seki = seki *  arr[(N - j -1)] % MOD
                        minusposition = N - j -1
                        j += 1
                        hashi = 1
                    else:
                        seki = seki * arr[i] % MOD
                        minusposition = i
                        i += 1
                        hashi = 0
    if (i + j) >= K:break

if minusflag == 1:
    if minuscount % 2 != 0:
        gyaku = modinv(arr[minusposition],MOD)
        seki =  seki * gyaku % MOD
        if minusposition == (N - j):
            seki = seki * arr[i] % MOD
        else:
            seki = seki * arr[i-1] % MOD

print(seki)

Submission status: Wrong Answer

Solution code:
#E_Multiplication4
N,K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 1000000007
#ソート
arr = []
j = 0
i = 0
seki = 1
gyaku = 1
def modpow(a,n,mod):
    res = 1
    while n > 0 :
        if n & 1 :
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res
def modinv(a,mod):
    return modpow(a, mod - 2, mod)

arr = sorted(A,reverse = True)
 
while (i + j) < K:
    if arr[(N - j -1)] > 0 :
        seki = seki * arr[i] % MOD
        i += 1
    else:
        if arr[i] < 0 :
            if K % 2 == 0:
                seki = seki *  arr[(N - j -1)] % MOD
                j += 1
            else:
                seki = seki * arr[i] % MOD
                i += 1
        else:
            if abs(arr[i]) > abs( arr[(N - j -1)]) :
                seki = seki * arr[i] % MOD
                i += 1
            else:
                seki = seki * arr[(N - j -1)] % MOD
                j += 1
if seki <= 0:
    gyaku = modinv(arr[(N - j -2)],MOD)
    seki =  seki * gyaku % MOD
    seki = seki * arr[i] % MOD
print(seki)

Submission status: Wrong Answer

Solution code:
x = list(input().split())
a = list((int(i) for i in input().split()))
n, k = int(x[0]), int(x[1])
#import random
import queue
#n = 9999
#k = random.choice(range(1, n))
#a = random.choices(range(-100000000, 100000000, 1), k=n)

MOD = 10**9 + 7

# check negative mode
neg = True
for i in range(n):
    if a[i] > 0:
        neg = False
if not (neg and k%2==1): neg = False
if neg: flag = 1
else: flag = -1

res = queue.PriorityQueue()
for i in range(n): res.put((flag * abs(a[i]), a[i]))
ans = 1
ansq = []

if neg: # negative case
    for i in range (k):
        (acur, cur) =  res.get()
        ans = ans * cur % MOD
        ansq.append(ans)

else: # positive case
    sm_pos, sm_neg, lg_pos, lg_neg = MOD, MOD, 0, 0
    for i in range (k):
        (acur, cur) = res.get()
        ans = ans * cur % MOD
        ansq.append(cur)
        if cur > 0 and sm_pos > acur: sm_pos = acur
        elif cur < 0 and sm_neg > acur: sm_neg = acur
    while res.qsize() > 0:
        (acur, cur) = res.get()
        if cur > 0 and lg_pos > acur: lg_pos = acur
        elif cur < 0 and lg_neg > acur: lg_neg = acur
        if lg_pos != 0 and lg_neg != 0: break
#    print (sm_pos, sm_neg, lg_pos, lg_neg, ans)
    if ans < 0:
        if lg_neg/sm_pos>lg_pos/sm_neg and lg_neg!=0 and sm_pos!=MOD:
            ans = ans * lg_neg / sm_pos
        elif lg_pos!=0 and sm_neg!=MOD:
            ans = ans * lg_pos / sm_neg
        else:
            print("panic")

print (int(ans % MOD))

Submission status: Wrong Answer

Solution code:
x = list(input().split())
a = list((int(i) for i in input().split()))
n, k = int(x[0]), int(x[1])
#import random
import queue
#n = 9999
#k = random.choice(range(1, n))
#a = random.choices(range(-100000000, 100000000, 1), k=n)

MOD = 10**9 + 7

# check negative mode
neg = True
for i in range(n):
    if a[i] > 0:
        neg = False
if not (neg and k%2==1): neg = False
if neg: flag = 1
else: flag = -1

res = queue.PriorityQueue()
for i in range(n): res.put((flag * abs(a[i]), a[i]))
ans = 1
ansq = []

if neg: # negative case
    for i in range (k):
        (acur, cur) =  res.get()
        ans = ans * cur % MOD
        ansq.append(ans)

else: # positive case
    sm_pos, sm_neg, lg_pos, lg_neg = MOD, MOD, 0, 0
    for i in range (k):
        (acur, cur) = res.get()
        ans = ans * cur % MOD
        ansq.append(cur)
        if cur > 0 and sm_pos > acur: sm_pos = acur
        elif cur < 0 and sm_neg > acur: sm_neg = acur
    while res.qsize() > 0:
        (acur, cur) = res.get()
        if cur > 0 and lg_pos > acur: lg_pos = acur
        elif cur < 0 and lg_neg > acur: lg_neg = acur
        if lg_pos != 0 and lg_neg != 0: break
#    print (sm_pos, sm_neg, lg_pos, lg_neg, ans)
    if ans < 0:
        if lg_neg / sm_pos > lg_pos / sm_neg:
            ans = ans * lg_neg / sm_pos
        else:
            ans = ans * lg_pos / sm_neg

print (int(ans % MOD))

Submission status: Wrong Answer

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


def prod(L):
    ans = 1
    for i in range(len(L)):
        ans *= L[i]
        ans = ans % (10**9+7)
    print(ans)
    exit()


if K == N:
    prod(A)
B = sorted(A)
if K % 2 == 1 and B[-1] <= 0:
    B = B[N-K:]
    prod(B)

A.sort(key=lambda x: abs(x), reverse=True)
# print(A)
D = A[:K]
# print(D)
if D[-1] == 0:
    print(0)
    exit()

ct = 0
for i in range(K):
    if D[i] < 0:
        ct += 1
if ct % 2 == 0:
    prod(D)
c = D.pop()
c = c//abs(c)
for j in range(K, N):
    if c*A[j] < 0:
        D.append(A[j])
        prod(D)
        break
else:
    print(0)

Submission status: Wrong Answer

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


def prod(L):
    ans = 1
    for i in range(len(L)):
        ans *= L[i]
        ans = ans % (10**9+7)
    print(ans)
    exit()


if K == N:
    prod(A)
B = sorted(A)
if K % 2 == 1 and B[-1] <= 0:
    B = B[N-K:]
    prod(B)

A.sort(key=lambda x: abs(x), reverse=True)
# print(A)
D = A[:K]
# print(D)
if D[-1] == 0:
    print(0)
    exit()

ct = 0
for i in range(K):
    if D[i] < 0:
        ct += 1
if ct % 2 == 0:
    prod(D)
c = D.pop()
c = c//abs(c)
for j in range(K, N):
    if c*A[j] > 0:
        D.append(A[j])
        prod(D)
        break
else:
    print(0)

Submission status: Wrong Answer

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

MOD = 10**9+7
N, K = map(int, readline().split())
A = list(map(int, readline().split()))
posi = [(a, 0) for a in A if a >= 0]
nega = [(-a, 1) for a in A if a < 0]
B = posi + nega
B.sort(reverse = True)

if N == len(nega):
    if K & 1:
        A.sort(reverse = True)
    else:
        A.sort()
    ans = 1
    
    for i in range(K):
        ans = (ans*A[i]) % MOD  
    print(ans)
else:
    cnt = 0
    for i in range(K):
        _, s = B[i]
        cnt ^= s
    
    res, _ = map(list, zip(*B[:K]))
    if cnt:
        pf, nf, ps, ns = None, None, 0, 0
        for i in range(K):
            b, s = B[i]
            if s:
                nf = b
            else:
                pf = b
        
        for i in range(K, N):
            b, s = B[i]
            if s:
                ns = b
                break
        for i in range(K, N):
            b, s = B[i]
            if not s:
                ps = b
                break
        
        if pf is None:
            res.remove(nf)
            res.append(ps)
        elif nf is None:
            res.remove(pf)
            res.append(ns)
        elif ns*nf >= pf*ps:
            res.remove(pf)
            res.append(ns)
        else:
            res.remove(nf)
            res.append(ps)
        
    ans = 1
    for r in res:
        ans = (ans*r)%MOD
        
    print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import collections
import math
import heapq
import sys


def solve(n, k, aaa):
    pos = []
    neg = []
    MOD = 10 ** 9 + 7
    for a in aaa:
        if a > 0:
            pos.append(a)
        elif a < 0:
            neg.append(a)
    if len(pos) + len(neg) < k:
        return 0
    if len(pos) == 0:
        if k % 2 == 1:
            if len(neg) < n:
                return 0
            neg.sort(reverse=True)
        else:
            neg.sort()
        ans = 1
        for a in neg[:k]:
            ans = ans * a % MOD
        return ans
    if len(pos) + len(neg) == k:
        if n > k and len(neg) % 2 == 1:
            return 0
        ans = 1
        for a in pos:
            ans = ans * a % MOD
        for a in neg:
            ans = ans * a % MOD
        return ans

    pos.sort()
    neg.sort(reverse=True)

    ans = 1
    r = k
    while r >= 2:
        if len(pos) <= 1:
            ans = ans * neg.pop() * neg.pop() % MOD
        elif len(neg) <= 1:
            ans = ans * pos.pop() * pos.pop() % MOD
        else:
            pm = pos[-1] * pos[-2]
            nm = neg[-1] * neg[-2]
            if pm > nm:
                ans = ans * pm % MOD
                pos.pop()
                pos.pop()
            else:
                ans = ans * nm % MOD
                neg.pop()
                neg.pop()
        r -= 2

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

    return ans


n, k, *aaa = map(int, sys.stdin.buffer.read().split())
print(solve(n, k, aaa))

"""
#### 入力例 ####
N, X = map(int, input().split())

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

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())
"""
"""
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10**9 +7

def main():
    ans = 1
    A.sort(reverse=True)
    if N == K:
        for n in range(N):
            ans*=A[n]
        print(ans % mod)
        return
    
    M = collections.deque()
    P = collections.deque()
    for n in range(N):
        if A[n] < 0:
            M.append(A[n])
        elif 0 < A[n]:
            P.append(A[n])
    if len(P) + len(M) < K:
        print(0)
        return
    if len(P) == 0:
        if(K%2 == 1):
            if (len(M)< N):
                print(0)
                return
            for k in range(K):
                ans = ans * M.popleft() % mod
            print(ans)
            return
        else:
            for k in range(K):
                ans = ans * M.pop() % mod
            print(ans)
            return
    if len(P) + len(M) == K:
        if K < N and len(M) % 2 == 1:
            print(0)
            return
        ans = 1
        while not len(P) == 0:
            ans = ans * P.popleft() % mod
        while not len(M) == 0:
            ans = ans * M.pop() % mod
        print(ans)
        return 
    k = 0
    while k <= K-2:
        if len(P) < 2:
            ans *= M.pop() * M.pop() % mod
        elif len(M) <2:
            ans *= P.pop() * P.pop() % mod
        else:
            if (P[0]*P[1] <= M[-1]*M[-2]):
                ans *= M.pop() * M.popleft() % mod
            else:
                ans *= P.pop() * P.pop() % mod
        k+=2
    if k == K-1:
        ans *= P.pop() % mod

    print(ans)
    return

if __name__ == '__main__':
    main()
"""