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 = list(map(int,input().split()))
MOD = 10**9+7

plus,minus,zero = 0,0,0
for i in range(N):
    if A[i] > 0:
        plus += 1
    elif A[i] < 0:
        minus += 1
    else:
        zero += 1

if N == K:
    ans = 1
    for i in range(N):
        ans *= A[i]
        ans %= MOD
    print(ans)

else:
    if K%2 == 1 and minus == N: # 負の場合
        A.sort(reverse=True)

        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= MOD
        print(ans)

    else: # そうじゃない場合
        l = []
        for i in range(N):
            if A[i] < 0:
                fugou = -1
            else:
                fugou = 1
            l.append((abs(A[i]),fugou))
        l.sort(reverse=True)
        #print(l)

        ans = 1
        fu = 0
        for i in range(K):
            if l[i][1] < 0:
                fu += 1
            ans *= l[i][0]
            ans %= MOD

        if fu%2 == 0:
            print(ans)
        elif ans == 0:
            print(0)
        else:
            sei_suteru = -1
            fu_suteru = -1
            for i in range(K)[::-1]:
                if sei_suteru == -1:
                    if l[i][1] > 0:
                        sei_suteru = l[i][0]
                if fu_suteru == -1:
                    if l[i][1] < 0:
                        fu_suteru = l[i][0]
                
            sei_ireru = -1
            fu_ireru = -1
            for i in range(K,N):
                if sei_ireru == -1:
                    if l[i][1] > 0:
                        sei_ireru = l[i][0]
                if fu_ireru == -1:
                    if l[i][1] < 0:
                        fu_ireru = l[i][0]

            #print(ans)
            #print(sei_suteru,fu_suteru,sei_ireru,fu_ireru)
            if sei_suteru >= 0 and fu_suteru >= 0 and sei_ireru >= 0 and fu_ireru >= 0:
                if sei_ireru/fu_suteru <= fu_ireru/sei_suteru or (fu_suteru == -1 or sei_ireru == -1): # 正を捨てて負を入れる方がいいとき
                    ans = -ans * -fu_ireru * pow(sei_suteru,MOD-2,MOD)
                    ans %= MOD
                else: # 負を捨てて正を入れる方がいいとき
                    ans = -ans * sei_ireru * pow(-fu_suteru,MOD-2,MOD)
                    ans %= MOD
            print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N,K = map(int,input().split())
L = list(map(int,input().split()))
L = sorted(L)

MOD=10**9+7

ans=1
if L[-1]<=0:#全部負
    if K%2==1:
        #小さい方からKこ
        for l in L[-K:]:
            ans*=l
            ans%=MOD
    else:
        #大きい方からKこ
        for l in L[:K]:
            ans*=l
            ans%=MOD
elif L[0]>=0:#全部生
    for l in L[-K:]:
        ans*=l
        ans%=MOD
else:#生徒ふが入り混じり
    absL = sorted(L,key=lambda x:-abs(x))
    cand=[v for v in absL[:K]]
    
    ans_cand=cand[-K:]
    remain=cand[:-K]

    ans_hugou=1
    for a in ans_cand:
        if a<0:
            ans_hugou*=-1

    if ans_hugou>=0:
        for a in ans_cand:
            ans*=a
            ans%=MOD
    else:
        #負の数をans_candから一つ取り除き、remain_candから一つ正の数を取ってくる
        ans_cand_min_neg = None
        for a in ans_cand:
            if a<0:
                ans_cand_min_neg=a
                break

        remain_cand_max_pos=None
        for a in remain:
            if a>0:
                remain_cand_max_pos=a

        #正の数をans_candから一つ取り除いき、remain_candから負の数を一つ取ってくる
        ans_cand_min_pos=None
        remain_cand_max_neg=None

        for a in ans_cand:
            if a>0:
                ans_cand_min_pos=a
                break
        for a in remain:
            if a<0:
                remain_cand_max_neg=a

        NG=None
        if not None in {ans_cand_min_pos,ans_cand_min_neg,remain_cand_max_neg,remain_cand_max_pos}:
            A = abs(ans_cand_min_neg*remain_cand_max_pos)
            B = abs(ans_cand_min_pos*remain_cand_max_neg)
            if A>=B:
                ans_cand.append(remain_cand_max_pos)
                NG=ans_cand_min_neg
            else:
                ans_cand.append(remain_cand_max_neg)
                NG=ans_cand_min_pos
        elif not None in {ans_cand_min_pos,remain_cand_max_neg}:
            ans_cand.append(remain_cand_max_neg)
            NG=ans_cand_min_pos
        elif not None in {ans_cand_min_neg,remain_cand_max_pos}:
            ans_cand.append(remain_cand_max_pos)
            NG=ans_cand_min_neg

        for a in ans_cand:
            if a!=NG:
                ans*=a
                ans%=MOD
print(ans)

Submission status: Wrong Answer

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

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
p = 10 ** 9 + 7
A.sort(key = lambda x : abs(x)) # 絶対値小→大
A_zpos = [a for a in A if a >= 0]
A_neg = [a for a in A if a < 0]

# 非負にできるか判定
nneg_en = False
if A_zpos:
    if K == N:
        if len(A_neg) % 2 == 0:
            nneg_en = True
    else:
        nneg_en = True
else:
    if K % 2 == 0:
        nneg_en = True


if nneg_en: # 非負にできる
    if K % 2 == 1:
        ans = A_zpos.pop() # 一番大きい正の数を確保
        K -= 1
    else:
        ans = 1

    while K > 0:
        # 2個ずつ取る
        next_zpos = -1 if len(A_zpos) < 2 else A_zpos[-1] * A_zpos[-2] % p
        next_neg = -1 if len(A_neg) < 2 else A_neg[-1] * A_neg[-2] % p
        if next_zpos >= next_neg:
            ans = ans * A_zpos.pop() * A_zpos.pop() % p
        else:
            ans = ans * A_neg.pop() * A_neg.pop() % p
        K -= 2
else:
    ans = 1
    for i in range(K):
        ans = ans * A[i] % p

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N,K = map(int,input().split())
L = list(map(int,input().split()))
L = sorted(L)

MOD=10**9+7

ans=1
if L[-1]<=0:#全部負
    if K%2==1:
        #小さい方からKこ
        for l in L[-K:]:
            ans*=l
            ans%=MOD
    else:
        #大きい方からKこ
        for l in L[:K]:
            ans*=l
            ans%=MOD
elif L[0]>=0:#全部生
    for l in L[-K:]:
        ans*=l
        ans%=MOD
else:#生徒ふが入り混じり
    absL = sorted(L,key=lambda x:-abs(x))
    cand=[v for v in absL[:K]]
    
    ans_cand=cand[-K:]
    remain=cand[:-K]

    ans_hugou=1
    for a in ans_cand:
        if a<0:
            ans_hugou*=-1

    if ans_hugou>=0:
        for a in ans_cand:
            ans*=a
            ans%=MOD
    else:
        #負の数をans_candから一つ取り除き、remain_candから一つ正の数を取ってくる
        ans_cand_min_neg = None
        for a in ans_cand:
            if a<0:
                ans_cand_min_neg=a

        remain_cand_max_pos=None
        for a in remain:
            if a>0:
                remain_cand_max_pos=a

        #正の数をans_candから一つ取り除いき、remain_candから負の数を一つ取ってくる
        ans_cand_min_pos=None
        remain_cand_max_neg=None

        for a in ans_cand:
            if a>0:
                ans_cand_min_pos=a
                break
        for a in remain:
            if a<0:
                remain_cand_max_neg=a
                break

        NG=None
        if not None in {ans_cand_min_pos,ans_cand_min_neg,remain_cand_max_neg,remain_cand_max_pos}:
            A = abs(ans_cand_min_neg*remain_cand_max_pos)
            B = abs(ans_cand_min_pos*remain_cand_max_neg)
            if A>=B:
                ans_cand.append(remain_cand_max_pos)
                NG=ans_cand_min_neg
            else:
                ans_cand.append(remain_cand_max_neg)
                NG=ans_cand_min_pos
        elif not None in {ans_cand_min_pos,remain_cand_max_neg}:
            ans_cand.append(remain_cand_max_neg)
            NG=ans_cand_min_pos
        elif not None in {ans_cand_min_neg,remain_cand_max_pos}:
            ans_cand.append(remain_cand_max_pos)
            NG=ans_cand_min_neg

        for a in ans_cand:
            if a!=NG:
                ans*=a
                ans%=MOD
print(ans)

Submission status: Wrong Answer

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

mainasu=[]
purasu=[]
for aa in a:
    if aa>=0:
        purasu.append(aa)
    else:
        mainasu.append(aa*(-1))



mod=10**9+7

#回答がプラスになるケース
if (k<n and len(purasu)>0) or (k<n and k%2==0) or (k==n and len(mainasu)%2==0):
    p_pos=0
    m_pos=0
    mainasu.sort(reverse=True)
    purasu.sort(reverse=True)
    ans=1
    cnt=0
    while cnt<k:
        ans=ans%mod
        #どっちからでも選べる
        if p_pos<len(purasu) and m_pos+1 < len(mainasu) and cnt<k-1:
            #もし最後から2つ目
            if cnt<=k-2:
                if p_pos==len(purasu)-1:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
                elif purasu[p_pos]*purasu[p_pos+1]>mainasu[m_pos]*mainasu[m_pos+1]:
                    ans*=purasu[p_pos]%mod
                    p_pos+=1
                    ans*=purasu[p_pos]%mod
                    p_pos+=1
                    cnt+=2
                else:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
            else:
                if purasu[p_pos]>mainasu[m_pos+1]:
                    ans=ans*purasu[p_pos]%mod
                    cnt+=1
                    p_pos+=1
                else:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
        elif p_pos<len(purasu):
            ans=ans*purasu[p_pos]%mod
            cnt+=1
            p_pos+=1
        else:
            ans*=mainasu[m_pos]%mod
            m_pos+=1
            ans*=mainasu[m_pos]%mod
            m_pos+=1
            cnt+=2
    print(ans%mod)









#回答がマイナスになるケース
else:
    pm=purasu+mainasu
    pm.sort()
    ans=1
    for i in range(k):
        ans=ans*pm[i]%mod
        ans=ans%mod
    #print(-1*ans)
    print((-1*ans)%mod)

Submission status: Wrong Answer

Solution code:
import heapq

N,K = map(int,input().split())
L = list(map(int,input().split()))
L = sorted(L)

MOD=10**9+7

ans=1
if L[-1]<=0:#全部負
    if K%2==1:
        #小さい方からKこ
        for l in L[-K:]:
            ans*=l
            ans%=MOD
    else:
        #大きい方からKこ
        for l in L[:K]:
            ans*=l
            ans%=MOD
elif L[0]>=0:#全部生
    for l in L[-K:]:
        ans*=l
        ans%=MOD
else:#生徒ふが入り混じり
    absL = sorted(L,key=lambda x:-abs(x))
    cand=[v for v in absL[:K]]
    
    ans_cand=cand[-K:]
    remain=cand[:-K]

    ans_hugou=1
    for a in ans_cand:
        if a<0:
            ans_hugou*=-1

    if ans_hugou>=0:
        for a in ans_cand:
            ans*=a
            ans%=MOD
    else:
        pass



    
print(ans%MOD)

Submission status: Wrong Answer

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

mainasu=[]
purasu=[]
for aa in a:
    if aa>=0:
        purasu.append(aa)
    else:
        mainasu.append(aa*(-1))



mod=10**9+7

#回答がプラスになるケース
if (k<n and len(purasu)>0) or (k<n and k%2==0) or (k==n and len(mainasu)%2==0):
    p_pos=0
    m_pos=0
    mainasu.sort(reverse=True)
    purasu.sort(reverse=True)
    ans=1
    cnt=0
    while cnt<k:
        ans=ans%mod
        #どっちからでも選べる
        if p_pos<len(purasu) and m_pos+1 < len(mainasu) and cnt<k-1:
            #もし最後から2つ目
            if cnt==k-2:
                if p_pos==len(purasu)-1:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
                elif purasu[p_pos]*purasu[p_pos+1]>mainasu[m_pos]*mainasu[m_pos+1]:
                    ans*=purasu[p_pos]%mod
                    p_pos+=1
                    ans*=purasu[p_pos]%mod
                    p_pos+=1
                    cnt+=2
                else:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
            else:
                if purasu[p_pos]>mainasu[m_pos+1]:
                    ans=ans*purasu[p_pos]%mod
                    cnt+=1
                    p_pos+=1
                else:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
        elif p_pos<len(purasu):
            ans=ans*purasu[p_pos]%mod
            cnt+=1
            p_pos+=1
        else:
            ans*=mainasu[m_pos]%mod
            m_pos+=1
            ans*=mainasu[m_pos]%mod
            m_pos+=1
            cnt+=2
    print(ans%mod)









#回答がマイナスになるケース
else:
    pm=purasu+mainasu
    pm.sort()
    ans=1
    for i in range(k):
        ans=ans*pm[i]%mod
        ans=ans%mod
    #print(-1*ans)
    print((-1*ans)%mod)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
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 = 0
m1 = MOD
p2 = MOD
for a in A[:K]:
    res *= a
    res %= MOD
    if a < 0:
        m1 = a
        cnt ^= 1
    if a > 0:
        p2 = a
if cnt & 1:
    m2 = MOD
    p1 = MOD
    for a in A[K:]:
        if a >= 0 and p1 == MOD:
            p1 = a
        if a <= 0 and m2 == MOD:
            m2 = a
        if p1 != MOD and m2 != MOD:
            break
    f1 = (m1 != MOD) and (p1 != MOD)
    f2 = (m2 != MOD) and (p2 != MOD)
    if f1 and f2:
        if p1 * p2 > m1 * m2:
            res = res * p1 // m1
        else:
            res = res * m2 // p2
    elif f1:
        res = res * p1 // m1
    elif f2:
        res = res * m2 // p2
    else:
        res = 1
        for a in A[N-1:N-K-1:-1]:
            res *= a
            res %= MOD
print(res)

Submission status: Wrong Answer

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

mainasu=[]
purasu=[]
for aa in a:
    if aa>=0:
        purasu.append(aa)
    else:
        mainasu.append(aa*(-1))



mod=10**9+7

#回答がプラスになるケース
if (k<n and len(purasu)>0) or (k<n and k%2==0) or (k==n and len(mainasu)%2==0):
    p_pos=0
    m_pos=0
    mainasu.sort(reverse=True)
    purasu.sort(reverse=True)
    ans=1
    cnt=0
    while cnt<k:
        ans=ans%mod
        #どっちからでも選べる
        if p_pos<len(purasu) and m_pos+1 < len(mainasu):
            #もし最後から2つ目
            if cnt==k-2:
                if p_pos==len(purasu)-1:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
                elif purasu[p_pos]*purasu[p_pos+1]>mainasu[m_pos]*mainasu[m_pos+1]:
                    ans*=purasu[p_pos]%mod
                    p_pos+=1
                    ans*=purasu[p_pos]%mod
                    p_pos+=1
                    cnt+=2
                else:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
            else:
                if purasu[p_pos]>mainasu[m_pos+1]:
                    ans=ans*purasu[p_pos]%mod
                    cnt+=1
                    p_pos+=1
                else:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
        elif p_pos<len(purasu):
            ans=ans*purasu[p_pos]%mod
            cnt+=1
            p_pos+=1
        else:
            ans*=mainasu[m_pos]%mod
            m_pos+=1
            ans*=mainasu[m_pos]%mod
            m_pos+=1
            cnt+=2
    print(ans%mod)









#回答がマイナスになるケース
else:
    pm=purasu+mainasu
    pm.sort()
    ans=1
    for i in range(k):
        ans=ans*pm[i]%mod
        ans=ans%mod
    #print(-1*ans)
    print((-1*ans)%mod)

Submission status: Wrong Answer

Solution code:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
p = 10**9+7
Aplus = []
Nplus = 0
Aminus = []
Nminus = 0
Aabs = []
for i in range(N):
    if A[i]>=0:
        Aplus.append(A[i])
        Nplus += 1
    else:
        Aminus.append(A[i])
        Nminus += 1
Aplus.sort(reverse=True)
Aminus.sort(reverse=False)

if K==N:
    out=1
    for i in range(K):
        out = out*A[i]%p
    print(out)
elif Nminus==N:
    out=1
    for i in range(K):
        out = out*Aminus[N-i-1]%p
    print(out)
else:

    l=0
    r=0
    out=1
    inf = float('inf')
    while K>0:
        if l+1<=Nplus-1:
            cand1 = Aplus[l]*Aplus[l+1]
        elif l==Nplus-1:
            cand1 = Aplus[l]
        else:
            cand1 = -1*inf

        if r+1<=Nminus-1:
            cand2 = Aminus[r]*Aminus[r+1]
        elif r==Nminus-1:
            cand2 = Aminus[r]
        else:
            cand2 = -1*inf

        if cand1>cand2 or K==1:
            out=out*Aplus[l]%p
            K += -1
            l+=1
        else:
            out=out*Aminus[r]*Aminus[r+1]%p
            K += -2
            r+=2
    print(out)

Submission status: Wrong Answer

Solution code:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
p = 10**9+7
Aplus = []
Nplus = 0
Aminus = []
Nminus = 0
Aabs = []
for i in range(N):
    if A[i]>=0:
        Aplus.append(A[i])
        Nplus += 1
    else:
        Aminus.append(A[i])
        Nminus += 1
Aplus.sort(reverse=True)
Aminus.sort(reverse=False)

if K==N:
    out=1
    for i in range(K):
        out = out*A[i]%p
    print(out)
elif Nminus==N:
    out=1
    for i in range(K):
        out = out*Aminus[N-i-1]%p
    print(out)
else:

    l=0
    r=0
    out=1
    inf = float('inf')
    while K>0:
        if l+1<=Nplus-1:
            cand1 = Aplus[l]*Aplus[l+1]
        elif l==Nplus-1:
            cand1 = Aplus[l]
        else:
            cand1 = -1*inf

        if r+1<=Nminus-1:
            cand2 = Aminus[r]*Aminus[r+1]
        elif r==Nminus-1:
            cand2 = Aminus[r]
        else:
            cand2 = -1*inf

        if cand1>cand2 or K==1:
            out=out*Aplus[l]%p
            K += -1
            l+=1
        else:
            if r==Nminus-1 :
                out=out*Aminus[r]%p
                K += -1
                r+=1
            elif r+1<=Nminus-1:
                out=out*Aminus[r]*Aminus[r+1]%p
                K += -2
                r+=2
    print(out)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 1
if max(a)==0:
  print(0)
  exit()
elif max(a)<0 and k%2==1:
  a = sorted(a)[::-1]
  for i in range(k):
    ans *= a[i]
    if ans>(10**9+7):
      ans %= (10**9+7)
    elif ans<(10**9+7):
      ans += (10**9+7)
  ans %= (10**9+7)
  print(abs(ans))
  exit()

a_abs = [[a_, abs(a_)] for a_ in a]
a_abs = sorted(a_abs, key=lambda x: -x[-1])

cnt = 0
for i in range(k):
  if a_abs[i][0]<0:
    cnt += 1

if cnt%2==0:
  for i in range(k):
    ans *= a_abs[i][0]
    if ans>(10**9+7):
      ans %= (10**9+7)
    elif ans<(10**9+7):
      ans += (10**9+7)
  ans %= (10**9+7)
  print(ans)
  exit()
  
p1 = -1
p2 = -1
for i in range(k-1,-1,-1):
  if p1==-1 and a_abs[i][0] > 0:
    p1 = i
  elif p2==-1 and a_abs[i][0] < 0:
    p2 = i
  elif p1!=-1 and p2!=-1:
    break

ans1 = 1
ans2 = -1
for i in range(k):
  if i!=p1:
    ans1 *= a_abs[i][0]
  if i!=p2:
    ans2 *= a_abs[i][0]
  if ans1>(10**9+7):
    ans1 %= (10**9+7)
  elif ans1<(10**9+7):
    ans1 += (10**9+7)
  if ans2>(10**9+7):
    ans2 %= (10**9+7)
  elif ans2<(10**9+7):
    ans2 += (10**9+7)

flag1 = 0
flag2 = 0
for i in range(k, n):
  if flag1==0 and a_abs[i][0]<0:
    ans1 *= a_abs[i][0]
    ans1 %= (10**9+7)
    flag1 = 1
  if flag2==0 and a_abs[i][0]>0:
    ans2 *= a_abs[i][0]
    ans2 %= (10**9+7)
    flag2 = 1
  if flag1==1 and flag2==1:
    break

print(max(ans1, ans2))

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:
    temp_lst.reverse()
    for i in temp_lst:
        if i==0:
            print(0)
            exit()
        elif i>0:
            switch=0
            for j in range(k,n):
                if lst[j]>=0:
                    switch+=1
                if lst[j]<0:
                    switch-=1
            if switch==n-k:
                for j in temp_lst:
                    if j<0:
                        temp_lst.remove(j)
                        break
                temp_lst.append(lst[k+1])
                answer(temp_lst)
            elif switch==k-n:
                for j in temp_lst:
                    if j>0:
                        temp_lst.remove(j)
                        break
                temp_lst.append(lst[k+1])
                answer(temp_lst)
            else:
                for j in range(k):
                    if temp_lst[j]>=0:
                        rem1=temp_lst[j]
                        break
                for j in range(k):
                    if temp_lst[j]<0:
                        rem2=temp_lst[j]
                        break
                for j in range(k,n):
                    if lst[j]<0:
                        rem3=lst[j]
                        break
                for j in range(k,n):
                    if lst[j]>=0:
                        rem4=lst[j]
                        break
                if abs(rem3/rem1)>=abs(rem4/rem2):
                    temp_lst.remove(rem1)
                    temp_lst.append(rem3)
                    answer(temp_lst)
                else:
                    temp_lst.remove(rem2)
                    temp_lst.append(rem4)
                    answer(temp_lst)
            
    plus=sorted(plus)        
    temp_lst.remove(temp_lst[0])
    temp_lst.append(plus[-1])
    answer(temp_lst)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect


class ModInt(int):

    MOD = 10 ** 9 + 7

    def __add__(self, other):
        self = ModInt(int.__add__(self, other) % ModInt.MOD)
        return self

    def __mul__(self, other):
        self = ModInt(int.__mul__(self, other) % ModInt.MOD)
        return self

def solve_all(data):
    #print('F') # debug
    ans = ModInt(1)
    for d in data:
        ans *= ModInt(d)
    return ans

def solve_minus(ms, k):
    #print('G') # debug
    ms = list(reversed(ms))
    ans = ModInt(1)
    for i in range(k):
        #print('ms[i]', ms[i]) # debug
        ans *= ModInt(ms[i])
    return ans

def take_p(pk, mk):
    return pk + 1, mk

def take_m(pk, mk):
    return pk, mk + 1

def take(ps, pk, ms, mk):
    if not takable(ps, pk):
        return take_m(pk, mk)
    if not takable(ms, mk):
        return take_p(pk, mk)
    p = ps[pk]
    m = ms[mk]
    if p > -1 * m:
        return take_p(pk, mk)
    else:
        return take_m(pk, mk)

def ans_is_minus(mk):
    if mk % 2 == 0:
        return False
    else:
        return True

def factorize(ps, pk, ms, mk):
    ans = ModInt(1)
    for i in range(pk):
        #print('ps[i]', ps[i]) # debug
        ans *= ModInt(ps[i])
    for i in range(mk):
        #print('ms[i]', ms[i]) # debug
        ans *= ModInt(ms[i])
    return ans

def takable(s, k):
    if k < len(s):
        return True
    else:
        return False

def rm_m_add_p(pk, mk):
    return pk + 1, mk - 1

def rm_p_add_m(pk, mk):
    return pk - 1, mk + 1

def adjust(ps, pk, ms, mk):
    if not takable(ps, pk):
        #print("A") # debug
        return rm_p_add_m(pk, mk)
    if not takable(ms, mk):
        #print("B") # debug
        return rm_m_add_p(pk, mk)
    rm_p = ps[pk - 1]
    add_p = ps[pk]
    rm_m = ms[mk - 1]
    add_m = ms[mk]
    if add_p * rm_p > add_m * rm_m: # ans * add_p / abs(rm_m) > ans * abs(add_m) / rm_p
        #print("C") # debug
        return rm_m_add_p(pk, mk)
    else:
        #print("D") # debug
        return rm_p_add_m(pk, mk)


def solve_main(ps, ms, k):
    pk = 0
    mk = 0
    while k > 0:
        pk, mk = take(ps, pk, ms, mk)
        k -= 1
    if not ans_is_minus(mk):
        #print('E') # debug
        return factorize(ps, pk, ms, mk)
    pk, mk = adjust(ps, pk, ms, mk)
    return factorize(ps, pk, ms, mk)



def mysplit(data):
    ps = []
    ms = []
    for d in data:
        if d >= 0:
            ps.append(d)
        else:
            ms.append(d)
    ps = list(reversed(sorted(ps)))
    ms = sorted(ms)
    return ps, ms

def solve(data, k):
    if len(data) == k:
        return solve_all(data)
    ps, ms = mysplit(data)
    if len(ps) == 0 and k % 2 != 0:
        return solve_minus(ms, k)
    return solve_main(ps, ms, k)


if __name__ == '__main__':
    n, k = list(map(int, input().split()))
    data = list(map(int, input().split()))
    ans = solve(data, k)
    #print('ans') # debug
    print(ans)

    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect


class ModInt(int):

    MOD = 10 ** 9 + 7

    def __add__(self, other):
        self = ModInt(int.__add__(self, other) % ModInt.MOD)
        return self

    def __mul__(self, other):
        self = ModInt(int.__mul__(self, other) % ModInt.MOD)
        return self

def solve_all(data):
    #print('F') # debug
    ans = ModInt(1)
    for d in data:
        ans *= ModInt(d)
    return ans

def solve_minus(ms, k):
    #print('G') # debug
    ms = list(reversed(ms))
    ans = ModInt(1)
    for i in range(k):
        #print('ms[i]', ms[i]) # debug
        ans *= ModInt(ms[i])
    return ans

def take_p(pk, mk):
    return pk + 1, mk

def take_m(pk, mk):
    return pk, mk + 1

def take(ps, pk, ms, mk):
    if not takable(ps, pk):
        return take_m(pk, mk)
    if not takable(ms, mk):
        return take_p(pk, mk)
    p = ps[pk]
    m = ms[mk]
    if p > -1 * m:
        return take_p(pk, mk)
    else:
        return take_m(pk, mk)

def ans_is_minus(mk):
    if mk % 2 == 0:
        return False
    else:
        return True

def factorize(ps, pk, ms, mk):
    ans = ModInt(1)
    for i in range(pk):
        #print('ps[i]', ps[i]) # debug
        ans *= ModInt(ps[i])
    for i in range(mk):
        #print('ms[i]', ms[i]) # debug
        ans *= ModInt(ms[i])
    return ans

def takable(s, k):
    if k < len(s):
        return True
    else:
        return False

def rm_m_add_p(pk, mk):
    return pk + 1, mk - 1

def rm_p_add_m(pk, mk):
    return pk - 1, mk + 1

def adjust(ps, pk, ms, mk):
    if not takable(ps, pk):
        #print("A") # debug
        return rm_p_add_m(pk, mk)
    if not takable(ms, mk):
        #print("B") # debug
        return rm_m_add_p(pk, mk)
    rm_p = ps[pk - 1]
    add_p = ps[pk]
    rm_m = ms[mk - 1]
    add_m = ms[mk]
    if add_p * rm_p > add_m * rm_m: # ans * add_p / abs(rm_m) > ans * abs(add_m) / rm_p
        #print("C") # debug
        return rm_m_add_p(pk, mk)
    else:
        #print("D") # debug
        return rm_p_add_m(pk, mk)


def solve_main(ps, ms, k):
    pk = 0
    mk = 0
    while k > 0:
        pk, mk = take(ps, pk, ms, mk)
        k -= 1
    if not ans_is_minus(mk):
        print('E')
        return factorize(ps, pk, ms, mk)
    pk, mk = adjust(ps, pk, ms, mk)
    return factorize(ps, pk, ms, mk)



def mysplit(data):
    ps = []
    ms = []
    for d in data:
        if d >= 0:
            ps.append(d)
        else:
            ms.append(d)
    ps = list(reversed(sorted(ps)))
    ms = sorted(ms)
    return ps, ms

def solve(data, k):
    if len(data) == k:
        return solve_all(data)
    ps, ms = mysplit(data)
    if len(ps) == 0 and k % 2 != 0:
        return solve_minus(ms, k)
    return solve_main(ps, ms, k)


if __name__ == '__main__':
    n, k = list(map(int, input().split()))
    data = list(map(int, input().split()))
    ans = solve(data, k)
    #print('ans') # debug
    print(ans)

    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 1
if max(a)==0:
  print(0)
  exit()
elif max(a)<0 and k%2==1:
  a = sorted(a)[::-1]
  for i in range(k):
    ans *= a[i]
    if ans>0:
      ans %= (10**9+7)
  ans %= (10**9+7)
  print(abs(ans))
  exit()

a_abs = [[a_, abs(a_)] for a_ in a]
a_abs = sorted(a_abs, key=lambda x: -x[-1])

cnt = 0
for i in range(k):
  if a_abs[i][0]<0:
    cnt += 1

if cnt%2==0:
  for i in range(k):
    ans *= a_abs[i][0]
    if ans>(10**9+7):
      ans %= (10**9+7)
  ans %= (10**9+7)
  print(ans)
  exit()
  
p1 = -1
p2 = -1
for i in range(k-1,-1,-1):
  if p1==-1 and a_abs[i][0] > 0:
    p1 = i
  elif p2==-1 and a_abs[i][0] < 0:
    p2 = i
  elif p1!=-1 and p2!=-1:
    break

ans1 = 1
ans2 = -1
for i in range(k):
  if i!=p1:
    ans1 *= a_abs[i][0]
  if i!=p2:
    ans2 *= a_abs[i][0]
  if ans1 > (10**9+7):
    ans1 %= (10**9+7)
  if ans2 > (10**9+7):
    ans2 %= (10**9+7)

flag1 = 0
flag2 = 0
for i in range(k, n):
  if flag1==0 and a_abs[i][0]<0:
    ans1 *= a_abs[i][0]
    ans1 %= (10**9+7)
    flag1 = 1
  if flag2==0 and a_abs[i][0]>0:
    ans2 *= a_abs[i][0]
    ans2 %= (10**9+7)
    flag2 = 1
  if flag1==1 and flag2==1:
    break

print(max(ans1, ans2))