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:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, K = LI()
A = LI()

def abssort(A):
    return sorted(A, key = lambda x:abs(x), reverse= True)

tmps = []
A_abs = abssort(A)
for i in range(K):
    # tmp *= A_abs[i]
    tmps.append(A_abs[i])

cnt = 0
for i in range(K):
    if tmps[i] < 0:
        cnt += 1
if cnt % 2 == 0:
    ans = 1
    for i in range(K):
        ans *= tmps[i]
        ans = ans % mod
    print(ans)
    sys.exit()
else:
    tmp_1 = copy.deepcopy(tmps)
    tmp_2 = copy.deepcopy(tmps)
    tmp_1.reverse()
    tmp_2.reverse()
    tmp_2_ = 0
    tmp_1_ = 0
    # -を一つ消す
    for i in range(K):
        if tmp_1[i] < 0:
            tmp_1.remove(tmp_1[i])
            break
    # + を一つたす
    for i in range(K, N):
        if A_abs[i] > 0:
            tmp_1.append(A_abs[i])
            tmp_1_ = 1
            break
    else:
        # +がなかった時
        tmp_1 = []
        tmp_1_ = -1 
        A_abs.reverse()
        for i in range(K):
            tmp_1.append(A_abs[i])

    # +を消して-を追加
    cnt = 0
    for i in range(K):
        if tmp_2[i] > 0:
            tmp_2.remove(tmp_2[i])
            cnt += 1
            break
    if cnt == 1:
        for i in range(K, N):
            if A_abs[i] < 0:
                tmp_2.append(A_abs[i])
                tmp_2_ = 1
                break
        else:
            tmp_2_ = 0
    else:
        tmp_2_ = -1
# print(tmp_1, tmp_2)



tmp_1_m = 1
tmp_2_m = 1
for i in range(K):
    tmp_1_m *= tmp_1[i]
    tmp_1_m = tmp_1_m % mod

if tmp_2_ == 0:
    pass
else:
    for i in range(K):
        tmp_2_m *= tmp_2[i]
        tmp_2_m = tmp_2_m % mod

# print(tmp_1_, tmp_2_)
if tmp_2_ == 0:
    print(tmp_1_m)
elif tmp_1_ == 1 and tmp_2_ == -1:
    print(tmp_1_m)
elif tmp_1_ == -1 and tmp_2_ == 1:
    print(tmp_2_m)
elif tmp_1_ == 1 and tmp_2_ == 1:
    for i in range(K):
        if tmp_1[i] == tmp_2[i]:
            pass
        elif abs(tmp_1[i]) > abs(tmp_2[i]):
            print(tmp_2_m)
            sys.exit()
        else:
            print(tmp_1_m)
            sys.exit()
else:
    print(tmp_1_m)
    # for i in range(K):
    #     if tmp_1[i] == tmp_2[i]:
    #         pass
    #     elif abs(tmp_1[i]) > abs(tmp_2[i]):
    #         print(tmp_2_m)
    #         sys.exit()
    #     else:
    #         print(tmp_1_m)
    #         sys.exit()

Submission status: Wrong Answer

Solution code:
from math import log, log10, log2

log = log2

def solve():
    MOD = 10**9 + 7

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

    numPos, num0, numNeg = 0, 0, 0
    for A in As:
        if A > 0:
            numPos += 1
        elif A == 0:
            num0 += 1
        else:
            numNeg += 1
#    print('numPos:', numPos, '/ num0:', num0, '/ numNeg:', numNeg)

    if numPos + numNeg < K:
        ans = 0
    else:
        posAs, negAs = [], []
        for A in As:
            if A > 0:
                posAs.append(A)
            elif A < 0:
                negAs.append(A)
        N = numPos + numNeg
#        print('posAs:', posAs, '/ negAs:', negAs)

        if K == N:
            if num0 > 0:
                ans = 0
            else:
                ans = 1
                for A in posAs:
                    ans *= A
                    ans %= MOD
                for A in negAs:
                    ans *= A
                    ans %= MOD

        elif K%2 != 0 and numPos == 0:
            if num0 > 0:
                ans = 0
            else:
                negAs.sort(reverse=True)
#                print('negAs:', negAs)
                ans = 1
                for A in negAs[:K]:
                    ans *= A
                    ans %= MOD

        else:
            posAs.sort(reverse=True)
            negAs.sort()
            acc = 0
            accPoss = [acc]
            for A in posAs:
                acc += log(A)
                accPoss.append(acc)
            acc = 0
            accNegs = [acc]
            for A in negAs:
                acc += log(-A)
                accNegs.append(acc)
#            print('accPoss:', accPoss)
#            print('accNegs:', accNegs)

            ans = -(10**12)
            xMax = -1
            for x in range(0, K+1, 2):
                y = K - x
                if x > numNeg or y > numPos:
                    continue
                prod = accNegs[x] + accPoss[y]
                if prod > ans:
                    ans = prod
                    xMax = x

            ans = 1
            for A in negAs[:xMax]:
                ans *= A
                ans %= MOD
            for A in posAs[:K-xMax]:
                ans *= A
                ans %= MOD

    print(ans % MOD)


solve()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
A.sort(key=lambda x:-abs(x))
mod=10**9+7


ans=1
flg=1
flgcnt=0
save=1

if k==1:
    print(max(A)%mod)
elif max(A)<0:
    ans=1
    for i in range(k):
        ans=ans*A[n-1-i]%mod
    print(ans)
else:
    
    for i in range(k-2):
        now=A[i]
        if now <0:
            flg*=-1
            flgcnt+=1
        ans=ans*now%mod
        if i==k-3:
            save=ans
            
    pl=[]
    mi=[]
    for i in range(k-2,n):
        now=A[i]
        if now<0:
            if len(mi)<2:
                mi.append(now)
        else:
            if len(pl)<2:
                pl.append(now)
        if len(pl)==2 and len(mi)==2:
            break
    
    ck=pl+mi
    can=[]
    for i in range(len(ck)-1):
        for q in range(i+1,len(ck)):
            can.append(ck[i]*ck[q])
    can.sort()
    
    if flg>0:
        print(save*can[-1]%mod)
    else:
        print(save*can[0]%mod)
            
    
    """
    #print(ans,flg)
    for i in range(k-1,n):
        now=A[i]
        if now >=0:
            lasflg=1
        else:
            lasflg=-1
        if flg*lasflg==1:
            print(ans*now%mod)
            break
    else:
        if flgcnt==k-1 and k>=2:
            ans=save
            two=2
            for i in range(k-2,n):
                now=A[i]
                if now>=0:
                    two-=1
                    ans=ans*now%mod
                if two==0:
                    print(ans)
                    break
            else:
                ans=1
                for i in range(k):
                    ans=ans*A[n-1-i]%mod
                print(ans)
                
        else:
            ans=1
            for i in range(k):
                ans=ans*A[n-1-i]%mod
            print(ans)
            
        """

Submission status: Wrong Answer

Solution code:
import numpy as np

def kmaxprod_v2(data, k):
    if len(data) < k:
        return np.nan
    data = np.asanyarray(data)
    # for integer dtypes convert to python ints to have unlimited range for the
    # final product
    dfp = data.astype(object) if data.dtype in (
        int, np.int64, np.int32, np.int16, np.int8) else data
    # np.argpartition raises an exception if len(data) == k, therefore
    if len(data) == k:
        return np.prod(dfp)
    neg = data <= 0
    # if k is odd and there are no positive elements we must settle for the
    # least negative
    if k % 2 == 1 and np.count_nonzero(neg) == len(data):
        return np.prod(-np.partition(-data, k)[:k].astype(dfp.dtype))
    # now n > k and we have at least one positive element
    ap = np.argpartition(-np.absolute(data), k)
    low, high = ap[k:], ap[:k]
    # try multiplying the k with highest absolute value
    greedy = np.prod(dfp[high])
    if greedy >= 0:
        return greedy
    # there are two possible ways of fixing the sign:
    # either swap the worst negative inside for the best positive outside
    # or swap the worst positive inside for the best negative outside
    # compute both and compare
    # bpo in, wni out
    bpo = np.max(dfp[low])
    if bpo <= 0:
        spfn = 0
    else:
        neg_high = np.where(neg[high])[0]
        wni_ind = np.argmax(data[high[neg_high]])
        # translate to index in high
        wni_ind = neg_high[wni_ind]
        spfn = bpo*np.prod(dfp[high[:wni_ind]])*np.prod(dfp[high[wni_ind+1:]])
        spfn %= 1000000007
    # bno in, wno out
    pos_high = np.where(~neg[high])[0]
    if len(pos_high) == 0:
        snfp = 0
    else:
        wpi_ind = np.argmin(data[high[pos_high]])
        wpi_ind = pos_high[wpi_ind]
        bno = np.min(dfp[low])
        snfp = bno*np.prod(dfp[high[:wpi_ind]])*np.prod(dfp[high[wpi_ind+1:]])
        snfp %= 1000000007
    return max(spfn, snfp)
  
n,k = map(int,input().split())
li = list(map(int,input().split()))
a = kmaxprod_v2(li, k)
print(a % 1000000007)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    A_neg = [a for a in A if a < 0]
    A_zero = [a for a in A if a == 0]
    A_pos = [a for a in A if a > 0]

    A_neg.sort(reverse=True)
    A_pos.sort()

    if K > len(A_neg) + len(A_pos):
        print(0)
        return
    elif len(A_pos) == 0:
        if len(A_zero) > 0:
            print(0)
            return
        elif K % 2:
            ans = 1
            for a in A_neg[:K]:
                ans = (ans * a) % MOD
            print(ans)
            return
        else:
            ans = 1
            for a in A_neg[-K:]:
                ans = (ans * a) % MOD
            print(ans)
            return

    tmp_pos = []
    tmp_neg = []

    ans = 1
    neg = 0
    for i in range(K):
        if not A_neg:
            tmp_pos.append(A_pos[-1])
            ans = ans * A_pos.pop() % MOD
        elif not A_pos:
            tmp_neg.append(A_neg[-1])
            ans = ans * A_neg.pop() % MOD
            neg = 1 - neg
        elif -A_neg[-1] > A_pos[-1]:
            tmp_neg.append(A_neg[-1])
            ans = ans * A_neg.pop() % MOD
            neg = 1 - neg
        else:
            tmp_pos.append(A_pos[-1])
            ans = ans * A_pos.pop() % MOD

    if neg:
        if A_pos:
            ans = ans * pow(tmp_neg[-1], MOD - 2, MOD) * A_pos.pop() % MOD
        elif A_neg and tmp_pos:
            ans = ans * pow(tmp_pos[-1], MOD - 2, MOD) * A_neg.pop() % MOD
        elif len(A_zero) > 0:
            ans = 0

    print(ans % MOD)

    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

N,K=(int(x) for x in input().rstrip('\n').split())
As=[int(x) for x in input().rstrip('\n').split()]
Bs = [x for x in As if x>0]
Bs = sorted(Bs,reverse=True)
Cs = [-x for x in As if x<0]
Cs=sorted(Cs,reverse=True)
m = 10**9+7
if len(Bs)>0:
  c = len(Cs)//2
  res = []
  for i in range(c+1):
    r=1
    if i==0:
      for x in Bs[:K]:
        r = r*x
      res.append(r%m)
    else:
      for x in Bs[:K-2*i]:
        r = r*x
      for x in Cs[:2*i]:
        r = r*x
      res.append(r%m)
  print(max(res))
else:
  As2=sorted(As)
  r = 1
  for x in As[:K]:
    r = r*x
  print(r%m)

Submission status: Wrong Answer

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

mod = 10**9 + 7

Am, Ap = [], []
pm = [0, 0, 0]
Flag = True

for x in A:
  if x < 0:
    Am.append(-x)
    pm[0] += 1
  elif x == 0:
    pm[1] += 1
  else:
    Ap.append(x)
    pm[2] += 1

Am.sort()
Ap.sort()
ans = 1

if N-K < pm[1]:
  print(0)
  exit()

if pm[0] == N:
  for i in range(K):
    ans *= Am[i]
    ans %= mod
  ans *= (-1)
  print(ans%mod)
  exit()

if K == 1:
  print(Ap[-1])
  exit()

Bm = sorted(zip(Am, [1]*pm[0]))
Bp = sorted(zip(Ap, [0]*pm[2]))

B = Bm + Bp
B.sort(reverse = True)
cnt = 0

for i in range(K):
  if i == K-1:
    cnt %= 2
    if cnt != B[i][1]:
      break
    else:
      ans *= B[i][0]
      ans %= mod
      print(ans)
      exit()
  else:
    ans *= B[i][0]
    ans %= mod
    cnt += B[i][1]

ans1 = ans
ans2 = ans * B[K-1][0] % mod

mcnt1 = 0
for i in range(K, N-pm[1]):
  if B[i][1] == cnt:
    mcnt1 += 1
    ans1 *= B[i][0]
    ans1 %= mod
    break

mcnt2 = 0
for i in range(K-2, -1, -1):
  if B[i][1] == cnt:
    mcnt2 += 1
    r = pow(B[i][0], mod-2, mod)
    ans1 *= r
    ans1 %= mod
    break

if mcnt1 == 1 and mcnt2 == 1:
  print(max(ans1, ans2))
elif mcnt1 == 1:
  print(ans1)
elif mcnt2 == 1:
  print(ans2)
else:
  ans *= B[K][0]
  ans %= mod
  print(ans)

Submission status: Wrong Answer

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

sr = sorted(vals, reverse=True, key= lambda x: abs(x))

md = 10**9 + 7


def sign(i_):
    if i_ > 0:
        return 1
    else:
        return -1

def find_all(arr):
    plus = 0
    minus = 0
    candidate = 1
    values = []


    for i in range(k):
        i_ = arr[i]

        if i == k - 1:
            sgn = sign(i_)
            if candidate * sgn < 0:
                if i == n - 1:
                    break
                for v in vals[i + 1:]:
                    if candidate * sign(v) > 0:
                        candidate = (candidate * (v))
                        return candidate


        candidate = (candidate * (i_))

        if i_ > 0:
            plus += 1
        else:
            minus += 1

        values.append(i_)
    return candidate

candidate = find_all(sr)

if sign(candidate) < 0:
    minusCandidate = find_all(list(reversed(sr)))
    print(minusCandidate % md)
    exit()

print(candidate % md)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    a = LI()
    a.sort(key = lambda x:-abs(x))
    c = 0
    p = 0
    m = 0
    for i in a:
        if i != 0:
            c += 1
        if i > 0:
            p += 1
        if i < 0:
            m += 1
    if c < k:
        print(0)
        return
    f = 1
    for x in range(p+1):
        y = k-x
        if y < 0 or y > m:
            continue
        if not y&1:
            f = 0
            break
    if f:
        a.sort(key = lambda x:abs(x))
        ans = 1
        for i in a[:k]:
            ans *= i
            ans %= mod
        print(ans)
        return
    minus = [(1,[n,n])]
    a.sort()
    s = 1
    s2 = 1
    k1 = 0
    k2 = 0
    ind = [None]*2
    ind2 = [None]*2
    for j in range(n):
        i = a[j]
        if i != 0:
            if i < 0:
                ind[k1] = j
                k1 ^= 1
                s *= -i
                if not k1:
                    minus.append((s,ind))
                    s = 1
            else:
                ind2[k2] = j
                k2 ^= 1
                s2 *= i
                if not k2:
                    minus.append((s2,ind2))
                    s2 = 1
    ans = 1
    x = k>>1
    minus.sort(reverse = True)
    f = [1]*(n+1)
    for i in range(x):
        m,indi = minus[i]
        for j in indi:
            f[j] = 0
        ans *= m
        ans %= mod
    if (k-2*x)&1:
        b = [a[i] for i in range(n) if f[i]]
        p = max(b)
        ans *= p
    print(ans%mod)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:

def inverse(a): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

import sys
N,K = map(int,input().split())
A = list(map(int,input().split()))

B = []
zero = 0
pl = 0
mi = 0
for i in A:
    if i == 0:
        zero += 1
    else:
        B.append( ( abs(i) , i // abs(i) ) )
        if i < 0:
            mi += 1
        else:
            pl += 1

last_pl = None

B.sort()
B.reverse()
mod = 10**9+7

if N - zero < K:
    print (0)
    sys.exit()

if pl == 0:

    if K % 2 == 0:
        now = 1
        for i in range(K):
            now *= B[i][0]
            now %= mod
        print (now % mod)
        sys.exit()
    else:
        now = 1
        if zero > 0:
            print (0)
            sys.exit()
        
        for i in range(K):
            now *= B[N-i-1][0] * B[N-i-1][1]
            now %= mod
        print (now % mod)
        sys.exit()


lasp = None
lasm = None

now = 1
for i in range(K):
    now *= B[i][0] * B[i][1]

    if now >= 0:
        now %= mod
    else:
        now = now % mod - mod

    if B[i][1] > 0:
        lasp = B[i][0]
    else:
        lasm = -1 * B[i][0]

#print (lasp,lasm)
if now > 0:
    print (now % mod)
    sys.exit()

else:

    if lasp == None:
        change2 = float("-inf")
        a2 = 0
    else:
        a2 = now * inverse(lasp)
        change2 = 1 / lasp
        for i in range(K+1,len(B)):
            if B[i][1] < 0:
                a2 *= -1 * B[i][0]
                change2 *= B[i][0]
                break
        else:
            change2 = float("-inf")

    if lasm == None:
        change3 = float("-inf")
        a3 = 0
    else:
    
        a3 = now * inverse(lasm % mod)
        change3 = 1 / abs(lasm)
        for i in range(K+1,len(B)):
            if B[i][1] > 0:
                a3 *= B[i][0]
                change3 *= B[i][0]
                break
        else:
            change3 = float("-inf")

    #print (a2,a3)
    if change2 > change3:
        print (a2 % mod)
    else:
        print (a3 % mod)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
ans = 1
mod = 10**9+7
tmp_K = K
if min(A) > 0:
    A.sort(reverse=True)
    for i in A[:K]:
        ans = (ans*i)%mod
 
elif max(A) < 0:
 
    if K%2 == 0:
        A.sort()
        for i in A[:K]:
            ans = (ans*i)%mod
    else:
        A.sort(reverse=True)
        for i in A[:K]:
            ans = (ans*i)%mod

else:
    z = []
    p = []
    m = []
    for i in A:
        if i == 0:
            z.append([i,1])
        elif i > 0:
            p.append([i,1])
        else:
            m.append([i,1])
    m.sort()
    mm = []
    for i in range(0,len(m),2):
        try:
            mm.append([m[i][0]*m[i+1][0],2])
        except:
            pass
    
    tot = p+z+mm+m
 
    tot.sort(reverse=True)
    flag_m = False
    for v,cost in tot:
        if K <= 0:
            break
        if v < 0:
            flag_m = True
        if K - cost >= 0:
            ans = (ans*v)%mod
            K -= cost
        else:
            continue
    
    if flag_m and len(z) == 0:##値が負になる．絶対値の最小化を行う．
        b = sorted(list([[abs(i),i] for i in A]))
        bb = list(i for _,i in b)
        res = 1
        for i in range(tmp_K):
            res = (res*bb[i])
        print(res)
        exit()
print(ans%mod)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
p=[]
m=[]
z=0
a.sort(reverse=True)
for i in range(n):
    if a[i]>0:
        p.append(a[i])
    elif a[i]==0:
        z+=1
    else:
        m.append(a[i])
nump=len(p)
numm=len(m)
ans=1
if nump+numm<k:
    print(0)
elif numm<2 and nump>=k:
    for i in range(k):
        ans*=p[i]
        ans%=10**9+7
    print(ans)
elif 2*(numm//2)+nump<k: #2
    if z!=0:
        print(0)
    else:
        for i in range(n):
            a[i]=abs(a[i])
        a.sort()
        ans=-1
        for i in range(k):
            ans*=a[i]
            ans%=10**9+7
        print(ans)
elif  nump==0: #8?
    if z!=0 and k%2==1:
        print(0)
    elif z!=0 and numm<k:
        print(0)
    else:
        if k%2==0:
            m.sort()
            for i in range(k):
                ans*=m[i]
                ans%=10**9+7
        else:
            m.sort(reverse=True)
            for i in range(k):
                ans*=m[i]
                ans%=10**9+7
        print(ans)
else:
    if k%2==1:
        ans*=p[0]
    m.sort()
    p.sort(reverse=True)
    nump=(nump-1)//2
    numm=numm//2
    nump1=0
    nump2=0
    numm1=0
    numm2=0
    for i in range(k//2):
        if nump2==nump:
            nump1=-1
        else:
            nump1=p[nump2*2+1]*p[nump2*2+2]
        if numm2==numm:
            numm1=-1
        else:
            numm1=m[numm2*2]*m[numm2*2+1]
        if numm1>=nump1:
            num=numm1
            numm2+=1
        else:
            num=nump1
            nump2+=1
        ans*=num
        ans%=10**9+7
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip() # input string
ni = lambda: int(readline().rstrip()) # input int
nm = lambda: map(int, readline().split()) # input multiple int 
nl = lambda: list(map(int, readline().split())) # input multiple int to list

n, k = nm()
pos = []
neg = []
zero = 0
ans = 1
MOD = 10**9 + 7

for a in nl():
    if a == 0:
        zero += 1
    elif a > 0:
        pos.append(a)
    else:
        neg.append(a)

if zero >= (n-k+1) or ( ( len(pos) + len(neg) == k ) and ( len(neg) % 2 == 1 ) ):
    print(0)
    exit(0)
elif len(pos) == 0 and k % 2 == 1:
    neg.sort()
    for _ in range(k):
        ans *= neg.pop()
        ans %= MOD
else:
    pos = [0] + sorted(pos)
    neg = [0] + sorted(neg, reverse=True) #absが大きい順にpopで取れるようにする
    c_pos = []
    c_neg = []
    for _ in range(k):
        if pos[-1] <= - neg[-1]: #negのabsの方が大きい
            c_neg.append(neg.pop())
        else:
            c_pos.append(pos.pop())
    if len(c_neg) % 2 == 1:
        c_neg.pop()
        c_pos.append(pos.pop())
    for c in c_neg:
        ans *= -c
        ans %= MOD
    for c in c_pos:
        ans *= c
        ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
MOD = 10 ** 9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
S = sorted(A, key=abs, reverse=True)
X = 1
pm = 0
for i in range(K - 1):
    if S[i] < 0:
        pm = 1 - pm
    X = X * abs(S[i]) % MOD
    X = X % MOD
for i in range(K - 1, N):
    if pm == 0:
        if S[i] > 0:
            Y = X * S[i] % MOD
            print(Y % MOD)
            sys.exit()
    else:
        if S[i] < 0:
            Y = X * abs(S[i]) % MOD
            print(Y % MOD)
            sys.exit()

for i in range(K - 2, -1, -1):
    if K % 2 == 0:
        if S[i] < 0:
            X = 1
            for j in range(K):
                if j == i:
                    continue
                X = X * abs(S[j]) % MOD
                X = X % MOD
            print(X % MOD)
            sys.exit()
    if K % 2 == 1:
        if S[i] > 0:
            X = 1
            for j in range(K):
                if j == i:
                    continue
                X = X * abs(S[j]) % MOD
                X = X % MOD
            print(X % MOD)
            sys.exit()

X = 1
S = S[::-1]
for i in range(K):
    X = X * abs(S[i]) % MOD
X *= -1
print(X % MOD)

Submission status: Wrong Answer

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

A = sorted(A, reverse=True)

temp = A.copy()

B = []

for _ in range(K):
    if A[-1] < 0:
        if A[0] < abs(A[-1]):
            B.append(A.pop(-1))
        else:
            B.append(A.pop(0))
    else:
        B.append(A.pop(0))

A = temp[:K]

a = 1
b = 1

for num in A:
    a *= num

for num in B:
    b *= num

if a > b:
    print(a % (10**9 + 7))
else:
    print(b % (10**9 + 7))

Submission status: Wrong Answer

Solution code:
import bisect
N ,K = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
mod = 10 ** 9 + 7
# ans = 0
if A.count(0) > (N - K):
  print(0)
  quit()
  
# ans = minus
plus = bisect.bisect_right(A, 0)
minus = bisect.bisect_left(A, 0) 
if N == K:
  ans = 1
  for i in range(N):
    ans *= A[i]
    ans %= mod
  print(ans % mod)
  quit()
  
if minus == N:
  ans = 1
  for i in range(1, K + 1):
    ans *= A[-i]
    ans %= mod
  print(ans % mod)
  quit()
  
ans = 1

count = 0
i = 0
j = -1
while count < K:
  if K - count >= 2:
    fo = A[i] * A[i + 1]
    re = A[j] * A[j - 1]
    #print(fo, re)
    if fo > re:
      ans *= (fo % mod) 
      ans %= mod
      i += 2
    elif (A[j - 1] < 1) or (A[j - 2] < 1):
      if (K % 2 == 0):
        ans *= (re % mod)
        ans %= mod
        j -= 2
      else:  
        ans *= (fo % mod) 
        ans %= mod
        i += 2      
    else:
      ans *= (re % mod)
      ans %= mod
      j -= 2
    count += 2  
  else:
    count += 1
    ans *= A[j]
      
  #print(ans)
print(ans % mod)

Submission status: Wrong Answer

Solution code:
#coding: UTF-8
import itertools
from scipy.special import comb

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

maxList,minList = [],[]

list.sort(inList)
for i in range(k):
    minList.append(inList[i])
list.sort(inList, reverse=True)
for i in range(k):
    maxList.append(inList[i])
inList2 = minList+maxList

out = 0
for v in itertools.combinations(inList2, 2):
    tmp = 1
    for i in range(len(v)):
        tmp = tmp*v[i]
    if tmp > out: out = tmp
print(out)

Submission status: Wrong Answer

Solution code:
from bisect import *
n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
b = a[:] 
mod = 10 ** 9 + 7
ans = 1
for i in range(n // 2):
    if a[i] < 0:
        if i % 2 == 0:
            index = bisect_left(b, -a[i])
            if index > len(b) - k:
                b.insert(index, -a[i])
        if i % 2 == 1:
            index_ = bisect_left(b, -a[i])
            if index_ > len(b) - k:
                b.insert(index_, -a[i])
            else:
                b.pop(index)
    else:
        break

    """
    if k >= 2:
        if a[i * 2 + 1] < 0:
            index = bisect_left(b, -a[i * 2 + 1])
            print(index)
            if index > len(b) - k:
                insort_left(b, -a[i * 2])
                insort_left(b, -a[i * 2 + 1])
                k -= 2
        if a[i * 2 + 1] >= 0:
            break
    print(b)
    """

b = b[::-1]
cnt_ = 0
for i in range(n):
    if b[i] != 0:
        cnt_ += 1
    if cnt_ == k:
        break

if b[i] >= 0:
    cnt = 0
    for i in range(n):
        if b[i] != 0:
            ans *= b[i]
            ans %= mod
            cnt += 1
        if cnt == k:
            break  
    print(ans)
elif 0 in a and b[i] < 0:
    print(0)
else:
    cnt = 0
    a = a[::-1]
    for i in range(n):
        if a[i] != 0:
            ans *= a[i]
            ans %= mod
            cnt += 1
        if cnt == k:
            break  
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, K = LI()
A = LI()

def abssort(A):
    return sorted(A, key = lambda x:abs(x), reverse= True)

tmps = []
A_abs = abssort(A)
for i in range(K):
    # tmp *= A_abs[i]
    tmps.append(A_abs[i])

cnt = 0
for i in range(K):
    if tmps[i] < 0:
        cnt += 1
if cnt % 2 == 0:
    ans = 1
    for i in range(K):
        ans *= tmps[i]
        ans = ans % mod
    print(ans)
    sys.exit()
else:
    tmp_1 = copy.deepcopy(tmps)
    tmp_2 = copy.deepcopy(tmps)
    tmp_1.reverse()
    tmp_2.reverse()
    tmp_2_ = 0
    tmp_1_ = 0
    # -を一つ消す
    for i in range(K):
        if tmp_1[i] < 0:
            tmp_1.remove(tmp_1[i])
            break
    # + を一つたす
    for i in range(K, N):
        if A_abs[i] > 0:
            tmp_1.append(A_abs[i])
            tmp_1_ = 1
            break
    else:
        # +がなかった時
        tmp_1 = []
        tmp_1_ = -1 
        A_abs.reverse()
        for i in range(K):
            tmp_1.append(A_abs[i])

    # +を消して-を追加
    cnt = 0
    for i in range(K):
        if tmp_2[i] > 0:
            tmp_2.remove(tmp_2[i])
            cnt += 1
            break
    if cnt == 1:
        for i in range(K, N):
            if A_abs[i] < 0:
                tmp_2.append(A_abs[i])
                tmp_2_ = 1
                break
        else:
            tmp_2_ = 0
    else:
        tmp_2_ = -1
# print(tmp_1, tmp_2)



tmp_1_m = 1
tmp_2_m = 1
for i in range(K):
    tmp_1_m *= tmp_1[i]
    tmp_1_m = tmp_1_m % mod

if tmp_2_ == 0:
    pass
else:
    for i in range(K):
        tmp_2_m *= tmp_2[i]
        tmp_2_m = tmp_2_m % mod

# print(tmp_1_, tmp_2_)
if tmp_2_ == 0:
    print(tmp_1_m)
elif tmp_1_ == 1 and tmp_2_ == -1:
    print(tmp_1_m)
elif tmp_1_ == -1 and tmp_2_ == 1:
    print(tmp_2_m)
elif tmp_1_ == 1 and tmp_2_ == 1:
    for i in range(K):
        if tmp_1[i] == tmp_2[i]:
            pass
        elif abs(tmp_1[i]) > abs(tmp_2[i]):
            print(tmp_1_m)
            sys.exit()
        else:
            print(tmp_2_m)
            sys.exit()
else:
    print(tmp_1_m)
    # for i in range(K):
    #     if tmp_1[i] == tmp_2[i]:
    #         pass
    #     elif abs(tmp_1[i]) > abs(tmp_2[i]):
    #         print(tmp_2_m)
    #         sys.exit()
    #     else:
    #         print(tmp_1_m)
    #         sys.exit()