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:
MOD = int(1e9+7)
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
flag = 0
for a in A:
    if a>0:
        flag = 1
        break
#すべてマイナスか0
if flag == 0 and K%2==1:
    A.sort(reverse = True)
    ans = 1
    for i in range(K):
        ans = (ans*A[i]) % MOD
    print(ans)
#それ以外
else:
    A = sorted(A, key=abs, reverse = True)
    last_pos = -1
    last_neg = -1
    count_neg = 0
    is_zero = 0
    ans = 1
    for i in range(K):
        ans = (ans*A[i]) % MOD
        if A[i]>0:
            last_pos = i
        elif A[i]<0:
            last_neg = i
            count_neg += 1
        else:
            is_zero = 1
            break
    if is_zero == 1:
        print(0)
    elif count_neg%2 == 0:
        print(ans)
    else:
        flag_pos = 0
        flag_neg = 0
        new_pos = -1
        new_neg = -1
        for i in range(K,N):
            if A[i]>0 and flag_pos==0:
                flag_pos = 1
                new_pos = i
            elif A[i]<0 and flag_neg==0:
                flag_neg = 1
                new_neg = i
            if flag_pos == 1 and flag_neg == 1:
                break

        if last_pos > -1 and last_neg > -1 and new_pos > -1 and new_neg > -1:
            f1 = - A[new_pos] / A[last_neg]
            f2 = - A[new_neg] / A[last_pos]
            if f1>f2:
                ans = 1
                for i in range(K):
                    if i != last_neg:
                        ans = (ans*A[i]) % MOD
                ans = (ans*A[new_pos]) % MOD
            else:
                ans = 1
                for i in range(K):
                    if i != last_pos:
                        ans = (ans*A[i]) % MOD
                ans = (ans*A[new_neg]) % MOD
        elif last_pos > -1 and new_neg > -1:
            ans = 1
            for i in range(K):
                if i != last_pos:
                    ans = (ans*A[i]) % MOD
            ans = (ans*A[new_neg]) % MOD
        elif last_neg > -1 and new_pos > -1:
            ans = 1
            for i in range(K):
                if i != last_neg:
                    ans = (ans*A[i]) % MOD
            ans = (ans*A[new_pos]) % MOD
        else:
            ans = 0
            
        print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N, K = input().split()
N, K = int(N), int(K)
li = input().split()
li = list(map(int,li))
n_li = []
for l in li:
    n_li.append(l % (10**9+7))
print(n_li)

Submission status: Wrong Answer

Solution code:
# import sys
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# N, M = map(int, input().split())
# As = list(map(int, input().split()))
# queries = (input() for _ in range(N))

from bisect import bisect_left


def solve():
    N, K = map(int, input().split())

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

    As.sort()
    index = bisect_left(As, 1)

    # neg = As[:index]
    # pos = As[index:]
    # pos = pos[bisect_left(pos, 1):]
    # pos.sort(reverse=True)
    # print(pos, neg)

    pos = sorted(As, reverse=True)
    ans = 1
    mod = 10 ** 9 + 7

    if N == K:
        for p in pos:
            ans *= p
            ans %= mod
        return ans

    if index == N:
        for p in pos[:K]:
            ans *= p
            ans %= mod
        return ans

    pl = 0
    pr = N - 1

    for i in range(K//2):
        left = pos[pl] * pos[pl+1]
        right = pos[pr] * pos[pr-1]

        if left > right:
            ans *= left
            ans %= mod
            pl += 2
        else:
            ans *= right
            ans %= mod
            pr -= 2

    if K % 2:
        ans *= max(pos[pl], pos[pr])
        ans %= mod

    return ans


def main():
    print(solve())


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

div = 10 ** 9 + 7

n, k = map(int, input().split())
A = deque(sorted([int(x) for x in input().split()]))
maxA = A[-1]
ans = 1
for i in range(k // 2):
    l1 = A[0]
    l2 = A[1]
    r1 = A[-1]
    r2 = A[-2]
    l = l1 * l2
    r = r1 * r2
    if k % 2 == 1 and maxA < 0:
        ans *= r
        ans %= div
        A.pop()
        A.pop()
    else:
        if l < r:
            ans *= r
            ans %= div
            A.pop()
            A.pop()
        else:
            ans *= l
            ans %= div
            A.popleft()
            A.popleft()
if k % 2 == 1:
    ans *= A[-1]
print(ans)

Submission status: Wrong Answer

Solution code:
a = list(map(int, input().split(" ")))
N = a[0]
K = a[1]
if K % 2 == 1:
    k = int(K / 2 - 1)
    end = 1
else:
    k = int(K / 2)
    end = 0
max = 1
mi = 0
pl = 0
A = list(map(int, input().split(" ")))
if N == K:
    for i in range(N):
        max *= A[i]
else:
    if K % 2 == 1 and A[-1] <= 0:
        for i in range(K):
            max *= A[i]
    else:
        for i in range(k):
            if A[0] * A[1] == A[-1] * A[-2]:
                try:
                    if A[2] * A[3] >= A[-3] * A[-4]:
                        max *= A[0] * A[1]
                        A.pop(0)
                        A.pop(1)
                    else:
                        max *= A[-1] * A[-2]
                        A.pop(-1)
                        A.pop(-2)
                except IndexError:
                    max *= A[0] * A[1]
                    A.pop(0)
                    A.pop(1)
            elif A[0] * A[1] > A[-1] * A[-2]:
                max *= A[0] * A[1]
                A.pop(0)
                A.pop(1)
            elif A[0] * A[1] <= A[-1] * A[-2]:
                max *= A[-1] * A[-2]
                A.pop(-2)
                A.pop(-1)
        if end == 1:
            max *= A[-1]
print(max % 1000000007)

Submission status: Wrong Answer

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=1):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.node_size=len(ls)+1
                self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.node_size=int(input())
        else:
            self.node_size=inp_size
        self.edges,_=GI(self.node_size,self.node_size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.node_size=len(ls)+1
        self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def dfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def bfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.popleft()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def parent(self,x):
        return self.dfs(0,func=lambda pr,prv,nx,dist:pr,root_v=-1)
 
    def topological_sort(self,x):  # return topological sort of the tree
        tps=[]
        q=deque([x])
        v=[None]*self.node_size
        v[x]=0
        while q:
            c=q.popleft()
            tps.append(c)
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=0
        return tps
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.node_size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.node_size
        self.ETout=[-1]*self.node_size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def doubling_LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.depth=[None]*self.node_size
            self.depth=self.bfs(0,func=lambda pr,prv,nxt,dist:prv+1)
            self.par=self.bfs(0,func=lambda pr,prv,nxt,dist:pr)
            self.db=[self.par]
            for i in range(self.node_size.bit_length()):
                #show(self.db)
                self.db+=[[self.db[-1][self.db[-1][i]] for i in range(self.node_size)]]
            self.LCA_init_stat=True
        dx=self.depth[x]
        dy=self.depth[y]
        if dx>dy:
            dx,dy=dy,dx
        c=self.node_size.bit_length()
        while c>0:
            if dx+c<=dy:
                x=self.db[c][x]
                dx+=1<<c
            c>>=1
        
        if x==y:
            return x
        
        c=self.node_size.bit_length()
        while c>0:
            if self.db[c][x]!=self.db[c][y]:
                x=self.db[c][x]
                y=self.db[c][y]
            c>>=1
        
        return self.par[x]
        
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        #self.st=SegTree(self.node_size*2-1,self.ETdepth,function=min,ide=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
    def __str__(self):
        return  str(self.edges)
 
    def show(self):
        if all([all([d==1 for nd,d in e]) for e in self.edges]):
            print( [[nd for nd,d in e] for e in self.edges] )
        else:
            print(self)
 
    def dfs2(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        dfs_tr=[x]
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
                    dfs_tr+=nb,
        return v,dfs_tr

class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    # return boundary index of r such that func({table[i]} =< x , i in [pos,r]
    def right_bound(self,pos,x):
        k=(self.size-pos).bit_length()
        for j in range(k)[::-1]:
            nx=pos+(1<<j)
            if nx<n and self.query(pos,nx+1)<=x:
                pos+=(1<<j)
        return pos
    
    # return boundary index of l such that func({table[i]} =< x , i in [l,pos]
    def left_bound(self,pos,x):
        k=pos.bit_length()
        for j in range(k)[::-1]:
            nx=pos-(1<<j)
            if 0<=nx and self.query(nx,pos+1)<=x:
                pos-=(1<<j)
        return pos

    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)

show_flg=False
show_flg=True

ans=0

#h,w,K=LI()
n,k=LI()
b=LI()
a=sorted(b)
b.sort(key=lambda x:abs(x))

def naive(a,b,n,k):
    ans=-inf
    for p in permutations(range(n)):
        tmp=1
        for i in range(k):
            tmp*=a[p[i]]
        ans=max(tmp,ans)
    return ans

def solve(a,b,n,k):
    pl,mn,zr=[],[],[]
    for i in a:
        if i>0:
            pl+=i,
        elif i<0:
            mn+=i,
        else:
            zr+=i,
        
    def maximize(b,k):
        p,m=0,0
        mn_p,mn_m=inf,inf
        rt=1
        for i in range(k):
            x=b.pop()
            if x>0:
                p+=1
                if mn_p>x:
                    mn_p=x
                    #show('mn_p',mn_p,x)
            elif x<0:
                m+=1
                if mn_m>x:
                    mn_m=-x
                    #show('mn_n',mn_m,x)
            rt*=x
            rt%=mo
        #show(rt)
        if m%2==1:
            while b:
                x=b.pop()
                if x>0:
                    #show('?',rt,rt//mn_m,mn_m,x)
                    rt*=pow(-mn_m,mo-2,mo)
                    #rt//=mn_m
                    rt*=x
                    rt%=mo
                    return rt
                elif x<0 and p>0:
                    rt*=pow(mn_p,mo-2,mo)
                    #rt//=mn_p
                    rt*=x
                    rt%=mo
                    return rt
        return rt
    
    #M=maximize(b,k)
    #show(M,(M-mo))
    '''
    0 1000000005 -2 ([-1, 1, 1, 1, 2], [-1, 1, 1, 1, 2], 5, 5)
    3 1 2 ([-2, -1, 0, 1, 1], [0, -1], 5, 2)
    '''
    if k+len(zr)==n:
        al=1
        for i in pl:
            al*=i
            al%=mo
        for i in mn:
            al*=i
            al%=mo
        ans=al
        if len(mn)%2==1 and len(zr)>0:
            ans=0
        st=0
    elif k+len(zr)>n:
        ans=0
        st=1
    elif k%2==1 and len(pl)==0: # minus case
        ans=1
        for i in range(k):
            x=b[i]
            ans*=x
            ans%=mo
        if len(zr)>0:
            ans=0
        st=2
    else:
        ans=maximize(b,k)
        st=3

    return ans,st
ans,st=solve(a,b,n,k)
print(ans)

Submission status: Wrong Answer

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

a.sort(reverse=True)
b = False
for i in a[n-k:]:
    if i < 0:
        b = True
        break

if b and k % 2 == 0:
    a.reverse()

d = a[0:k]
e = 1
for i in d:
    e *= i

f = e % 1000000007
print(f)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,k = map(int,readline().split())
a = list(map(int,readline().split()))
mod = 10**9+7

p = []
P = 0
z = False
for i in a:
  if i > 0:
    p.append((i,1))
    P += 1
  elif i == 0:
    p.append((0,0))
    z = True
  else:
    p.append((-i,-1))
    
if P == 0:
  ans = 1
  p.sort()
  for i in range(k):
    ans *= -p[i][0]
    ans %= mod
  print(ans)
  exit()

p.sort(reverse=True)
mi_p = 0
ma_m = 0
c = 0
for i in range(k):
  if p[i][1] > 0:
    mi_p = i
  elif p[i][1] == 0:
    print(0)
    exit()
  else:
    ma_m = i
    c += 1
    
if c%2 == 0:
  ans = 1
  for i in range(k):
    ans *= p[i][0]
    ans %= mod
  print(ans)
elif c%2 == 1 and n == k:
  ans = 1
  for i in range(k):
    ans *= p[i][0]
    ans %= mod
  print(-ans)
else:
  ma_p = 0
  mi_m = 0
  for i in range(n-k):
    L = p[k+i]
    if L[1] > 0 and ma_p == 0:
      ma_p = p[k+i][0]
    if L[1] < 0 and mi_m == 0:
      mi_m = p[k+i][0]
    if ma_p*mi_m != 0:
      break
  ans_p = 1
  ans_m = 1
  for i in range(k):
    if i == ma_m:
      ans_p *= p[i][0]
    elif i == mi_p:
      ans_m *= p[i][0]
    else:
      ans_p *= p[i][0]
      ans_m *= p[i][0]
    ans_p %= mod
    ans_m %= mod
  print(max(ans_p*mi_m%mod,ans_m*ma_p%mod))

Submission status: Wrong Answer

Solution code:
import functools
import operator
import sys

prod = functools.partial(functools.reduce, operator.mul)

n, k = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a, reverse=True, key=lambda i: abs(i))

current = 0
for i in range(n-k+1):
    current = prod(a[i:k+i])
    if current >= 0:
        break

print(current % (10**9 + 7))

Submission status: Wrong Answer

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

mod = pow(10,9)+7

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

A_plus = []
A_minus = []
A_zero = []
for i in range(N):
    if A[i] > 0:
        A_plus.append(A[i])
    elif A[i] < 0:
        A_minus.append(A[i])
    else:
        A_zero.append(A[i])
A_plus.sort()
A_minus.sort()

# 基本は絶対値の大きい順に
# マイナスは偶数個になるように取り出さないといけない
# どう選んでもマイナスを奇数個にしかできない場合はマイナスを少ない順に選ぶ
# ...全部マイナスのとき
# どう選んでも0を含んでしまう時は0を出力

# 同じ場合
if N==K:
    ans_list = A
# 0以外からぴったし選べる場合
elif len(A_plus)+len(A_minus) == K:
    if len(A_minus)%2==1:
        print(0)
        exit(0)
    else:
        ans_list = A_plus
        ans_list.extend(A_minus)
# 個数が足りない場合
elif len(A_plus)+len(A_minus) < K:
    print(0)
    exit(0)
# プラスが0個の場合
elif len(A_plus) == 0:
    # 絶対値の小さい方から
    if K%2 == 1:
        A_minus = A_minus[::-1]
        ans_list = A_minus[:K]
    else:
        ans_list = A_minus[:K]
else:
    A_plus = A_plus[::-1]
    plus_pos = 0
    minus_pos = 0
    for k in range(K):
        if minus_pos >= len(A_minus):
            plus_pos += 1
        elif plus_pos >= len(A_plus):
            minus_pos += 1
        elif abs(A_plus[plus_pos]) < abs(A_minus[minus_pos]):
            minus_pos += 1
        else:
            plus_pos += 1

    if minus_pos%2==1:
        if minus_pos >= len(A_minus) or plus_pos == 0:
            minus_pos -= 1
            plus_pos += 1
        elif plus_pos >= len(A_plus):
            plus_pos -= 1
            minus_pos += 1
        else:
            add_plus = abs(A_plus[plus_pos]/A_minus[minus_pos-1])
            add_minus = abs(A_minus[minus_pos]/A_plus[plus_pos-1])
            if add_plus > add_minus:
                plus_pos += 1
                minus_pos -= 1
            else:
                plus_pos -= 1
                minus_pos += 1
    
    if plus_pos == 0:
        ans_list = A_minus[:K]
    elif minus_pos == 0:
        ans_list = A_plus[:K]
    else:
        ans_list = A_plus[:plus_pos]
        ans_list.extend(A_minus[:minus_pos])

ans = 1
print(ans_list)
for ans_i in ans_list:
    ans = ans*ans_i%mod

print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
P=[]
Z=[]
N=[]
for i in range(n):
  if a[i]>0:
    P.append(a[i])
  elif a[i]==0:
    Z.append(a[i])
  else:
    N.append(-a[i])
P.sort()
P3=[1]
for i in range(len(P)):
  P3.append(P3[-1]*P[i]%mod)
P.reverse()
P2=[1]
for i in range(len(P)):
  P2.append(P2[-1]*P[i]%mod)
N.sort()
N3=[1]
for i in range(len(N)):
  N3.append(N3[-1]*N[i]%mod)
N.reverse()
N2=[1]
for i in range(len(N)):
  N2.append(N2[-1]*N[i]%mod)

if n==k:
  ans=1
  for i in range(n):
    ans*=a[i]
    ans%=mod
  print(ans)
  exit()

if len(P)+len(N)<k:
  print(0)
  exit()

if len(N)==0:
  print(P2[k])
  exit()

if len(P)+len(N)==k:
  if len(N)%2==0:
    print(P2[-1]*N2[-1]%mod)
    exit()
  else:
    if len(Z)!=0:
      print(0)
    else:
      print(-P2[-1]*N2[-1]%mod)
    exit()

if k%2==0:
  ans=1
  xp=0
  xn=0
  for i in range(k//2):
    if xp+1<len(P):
      xa=P[xp]*P[xp+1]
    else:
      xa=0
    if xn+1<len(N):
      xb=N[xn]*N[xn+1]
    else:
      xb=0
    if xa<xb:
      xn+=2
      ans*=xb
      ans%=mod
    else:
      xp+=2
      ans*=xa
      ans%=mod
  print(ans)

else:
  ans=1
  xp=0
  xn=0
  ctP=0
  ctN=0
  for i in range(k//2):
    if xp+1<len(P):
      xa=P[xp]*P[xp+1]
    else:
      xa=0
    if xn+1<len(N):
      xb=N[xn]*N[xn+1]
    else:
      xb=0
    if xa<xb:
      xn+=2
      ans*=xb
      ans%=mod
      ctN+=1
    else:
      xp+=2
      ans*=xa
      ans%=mod
      ctP+=1
  if ctP*2+1<=len(P):
    ans*=P[ctP*2]
    ans%=mod
    print(ans)
  else:
    N.reverse()
    P.reverse()
    ans=1
    xp=0
    xn=0
    ctP=0
    ctN=0
    for i in range(k//2):
      if xp+1<len(P):
        xa=P[xp]*P[xp+1]
      else:
        xa=0
      if xn+1<len(N):
        xb=N[xn]*N[xn+1]
      else:
        xb=0
      if xa<xb:
        xn+=2
        ans*=xb
        ans%=mod
        ctN+=1
      else:
        xp+=2
        ans*=xa
        ans%=mod
        ctP+=1
    ans*=N[ctN*2]
    ans%=mod
    if len(Z)!=0:
      print(0)
    else:
      print(-ans%mod)

Submission status: Wrong Answer

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

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

B=[]
C=[]
Z=[]

for a in A:
    if a>0:
        B.append(a)
    elif a<0:
        C.append(-a)
    else:
        Z.append(0)

B.sort(reverse=True)
C.sort(reverse=True)

if K==len(B)+len(C):
    ANS=1
    for b in B:
        ANS=ANS*b%mod
    for c in C:
        ANS=ANS*(-c)%mod

    if len(C)%2==1 and Z!=[]:
        print(0)
    else:
        print(ANS)
    sys.exit()

if K>len(B)+len(C):
    print(0)
    sys.exit()

if B==[]:
    if Z==[] and K%2==0:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
            
    elif Z==[] and K%2==1:
        C.reverse()
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
        print(-ANS%mod)
        
    elif K%2==1:
        print(0)
    else:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod

    sys.exit()

if K<=len(B):
    S=1
    for i in range(K):
        S=S*B[i]%mod

    ind=0
    while True:
        if ind+1<len(C) and K-2-ind>=0 and C[ind]*C[ind+1]>B[K-1-ind]*B[K-2-ind]:
            S=S*C[ind]*C[ind+1]*pow(B[K-1-ind]*B[K-2-ind],mod-2,mod)%mod
            ind+=2
        else:
            break

    print(S%mod)

else:
    if (K-len(B))%2==0:
        S=1
        for i in range(len(B)):
            S=S*B[i]%mod

        for j in range(K-len(B)):
            S=S*C[j]%mod

        ind=K-len(B)

        while True:
            if ind+1<len(C) and len(B)-2-ind>=0 and C[ind]*C[ind+1]>B[len(B)-1-ind]*B[len(B)-2-ind]:
                S=S*C[ind]*C[ind+1]*pow(B[len(B)-1-ind]*B[len(B)-2-ind],mod-2,mod)%mod
                ind+=2
            else:
                break

    else:
        S=1
        for i in range(len(B)-1):
            S=S*B[i]%mod

        for j in range(K-len(B)+1):
            S=S*C[j]%mod

        ind=K-len(B)+1
        

        while True:
            if ind+1<len(C) and len(B)-3-ind>=0 and C[ind]*C[ind+1]>B[len(B)-2-ind]*B[len(B)-3-ind]:
                S=S*C[ind]*C[ind+1]*pow(B[len(B)-2-ind]*B[len(B)-3-ind],mod-2,mod)%mod
                ind+=2
            else:
                break

    print(S%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:
    if z!=0:
        print(0)
    else:
        for i in range(k):
            ans*=a[i]
            ans%=10**9+7
        print(ans)
elif  nump==0:
    if z!=0:
        print(0)
    else:
        for i in range(k):
            ans*=m[i]
            ans%=10**9+7
        print(ans)
else:
    if k%2==1:
        ans*=p[0]
    m.sort()
    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=0
        else:
            nump1=p[nump2*2]*p[nump2*2+1]
        if numm2==numm:
            numm1=0
        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:
N,K = map(int,input().split())
A = list(map(int,input().split()))
mod = 10**9+7
P = []
M = []
zero = []
for a in A:
    if a>0:
        P.append(a)
    elif a<0:
        M.append(a)
    else:
        zero.append(a)
if N==K and zero: print(0);exit()

P.sort(reverse=True)
M.sort(reverse=True)
if K==1:
    A.sort()
    print(A[-1]);exit()
if len(P)>=K:
    ans = 1
    P = P[:K]
    for i in range(K):
        ans *=P[i]
        ans %=mod
    while P:
        while len(M)>=2:
            a1 = M.pop()
            a2 = M.pop()
            b1 = P.pop()
            b2 = P.pop()
            if a1*a2 > b1*b2:
                ans = ans/b1
                ans = ans/b2
                ans *=a1*a2
                ans %=mod
            else:
                break
        break
else:
    ans = 1
    P.sort()
    for i in range(len(P)):
        ans *=P[i]
        ans %=mod
    K -=len(P)
    if K>len(M):print(0);exit()
    else:
        if K%2!=0:
            if zero:print(0);exit()
            else:
                M.sort(reverse=True)
                for i in range(K):
                    ans *=M[i]
                    ans %=mod
        else:
            for i in range(K):
                ans *=M[i]
                ans %=mod
print(int(ans%mod))

Submission status: Wrong Answer

Solution code:
def main():
    M=10**9+7
    n,k,*a=map(int,open(0).read().split())
    x,y=[],[]
    for i in a:
        if i>0:x.append(i)
        if i<0:y.append(i)
    if len(x)+len(y)<k or len(x)<k and len(y)<k and (k-len(x))%2 and len(x)+len(y)<n:
        print(0)
        exit()
    if len(x)<k and len(y)<k and (k-len(x))%2:
        x=sorted(x+[-i for i in y])[:k]
        x[0]*=-1
        c=1
        for i in x:
            c=c*i%M
        print(c)
        exit()
    x=sorted(x)[::-1][:k]
    y.sort()
    m=len(y)
    i=len(x)
    j=0
    if i<k:
        j=k-i
        x+=y[:j]
        j+=1
    while i>1 and j+1<m and x[i-1]*x[i-2]<y[j]*y[j+1]:
        x[i-1],x[i-2]=y[j],y[j+1]
        i-=2
        j+=2
    c=1
    for i in x:
        c=c*i%M
    print(c)
main()