Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

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

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

Constraints

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

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

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

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

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

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

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

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

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

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

Sample Input 4

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

Sample Output 4

999983200

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



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Wrong Answer

Solution code:
import sys,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)
        st=30
        if m%2==1:
            zp=sorted(b,key=lambda x:abs(x)*(x>0))
            zm=sorted(b,key=lambda x:abs(x)*(x<0))
            
            p_can=zp[-1] if zp and zp[-1]>0 else None
            m_can=zm[-1] if zm else None
            
            if p_can!=None and m_can!=None:
                if p_can/abs(mn_m) > m_can/abs(mn_p):
                    rt*=pow(-mn_m,mo-2,mo)
                    rt*=p_can
                    rt%=mo
                    st=31
                    return rt,(st,(p_can,m_can))
                else:# p_can/abs(mn_m) < m_can/abs(mn_p):
                    rt*=pow(-mn_p,mo-2,mo)
                    rt*=m_can
                    rt%=mo
                    st=32
                    return rt,st
            elif p_can!=None and m_can==None:
                rt*=pow(mn_m,mo-2,mo)
                rt*=p_can
                rt%=mo
                st=33
                return rt,st
            elif p_can==None and m_can!=None:
                rt*=pow(mn_p,mo-2,mo)
                rt*=m_can
                rt%=mo
                st=34
                return rt,st
    
            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,st
        return rt,st
    
    #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,st=maximize(b,k)
        #st=3

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

Submission status: Wrong Answer

Solution code:
from collections import deque
CONST = 10**9 + 7
n, k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()

if k == 1:
    print(a[-1] % CONST)
    exit()

a2 = deque(a)

mini = a2.popleft()
maxi = a2.pop()

if maxi < 0 or mini > 0:
    a2.appendleft(mini)
    ans = maxi % CONST
    for i in range(k-1):
        ans = (ans * a2.pop()) %CONST
    print(ans)
    exit()


ans = 1
ans2 = 1
for i in range(k-1):
    if len(a2) == 0:
        ans2 = (ans2 * maxi) % CONST
        ans2 = (ans2 * mini) % CONST
        print(ans)
        exit()

    if abs(mini) < abs(maxi):
        ans *= maxi
        ans2 = ans2 * maxi % CONST
        maxi = a2.pop()
    else:
        ans *= mini
        ans2 = ans2 * mini % CONST
        mini = a2.popleft()
print(ans, ans2, maxi, mini)
if ans * maxi < ans * mini:
    print((ans2*mini)%CONST)
else:
    print((ans2*maxi)%CONST)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
INF = 10**10
N ,K = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

def get_pos_num():
    lb = -1
    ub = N

    while ub - lb > 1:
        mid = (ub + lb) // 2
        if A[mid] > 0:
            ub = mid
        else:
            lb = mid

    return ub

def get_neg_num():
    lb = -1
    ub = N

    while ub - lb > 1:
        mid = (ub + lb) // 2
        if A[mid] >= 0:
            ub = mid
        else:
            lb = mid

    return lb

pos_num = get_pos_num()
neg_num = get_neg_num()
# A[0], A[1], ... , A[neg_num] <- negative number
# A[neg_num + 1], ..., A[pos_num - 1] <- 0
# A[pos_num], ..., A[N-1] <- positive number

neg_ind = 0
pos_ind = N-1
ans = 1

if (N-1) - neg_ind > K or K % 2 == 0:
    if not ((K <= (N-1 - pos_num + 1)) or (K%2==0 and neg_num > K) ) :
        ans = 0
        K = 0

    while K > 0:
        if K >= 2:
            if pos_ind < pos_num:
                pos_tmp = -1*INF
            else:
                pos_tmp = A[pos_ind]*A[pos_ind-1]

            if neg_ind > neg_num:
                neg_tmp = -1 * INF
            else:
                neg_tmp = A[neg_ind]*A[neg_ind+1]

            if pos_tmp == -1*INF and neg_tmp == -1*INF:
                ans = 0
                K = 0

            elif pos_tmp < neg_tmp:
                neg_ind += 2
                ans = (ans * neg_tmp + MOD) % MOD

                # ans *= neg_tmp
                K -= 2
            else:
                pos_ind -= 2
                ans = (ans * pos_tmp + MOD) % MOD

                # ans *= pos_tmp
                K -= 2
        
        else:
            ans = (ans * A[pos_ind] + MOD) % MOD
            # ans *= A[pos_ind]
            K -= 1
else:
    for i in range(K):
        ans = (ans * A[N-1-i] + MOD) % MOD
        # ans *= A[N-1-i]

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

m = 10 ** 9 + 7

A,B = map(int,input().split())
L = list(map(int, input().split()))
S = sorted(L,reverse=True)

v = np.prod(S[:B])

print(v%m)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
MOD = 10**9 + 7
N, K = map(int, input().split())
A = list(map(int, (input().split())))
ap = []
neg_cnt = 0
pos_cnt = 0
zero_cnt = 0
for a in A:
    if a<0:
        ap.append((-a, 1))     # sortで先に来るようマイナスを1にする
        neg_cnt += 1
    elif a==0:
        ap.append((0, 0))
        zero_cnt += 1
    else:
        ap.append((a, -1))
        pos_cnt += 1
ap.sort(reverse=True)
# print(ap)
ans = 1
if neg_cnt==N and K%2:      # 全てが負で奇数個選ぶので、答えは負
    for i in range(K):
        ans *= ap[N-i-1][0] * ap[N-i-1][1] * -1
        ans %= MOD
else:                       # 答えは正
    neg_num = 0
    pos_num = 0
    for i in range(K):
        if ap[i][1] == 1:
            neg_num += 1
        elif ap[i][1] == -1:
            pos_num += 1
    if neg_num % 2:     # 負の数が奇数だったら、-1して偶数回にし、正が出るまで見る
        if pos_num == pos_cnt:
            pos_flg = True
            neg_num += 1    # もう正がない
        else:
            neg_num -= 1
    i = 0
    cnt = 0
    while cnt < K and i < N:
    # for i in range(K):
        if ap[i][1] == 1:  # 負の数だったら、neg_num回まで
            if neg_num == 0:
                i += 1
                continue
            else:
                neg_num -= 1
        if ap[i][1] == -1: 
            if pos_num == 0:
                i += 1
                continue
            else:
                pos_num -= 1
        ans *= ap[i][0] * ap[i][1] * -1
        ans %= MOD
        cnt += 1
        i += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), key=abs, reverse=True)

mod = 10**9+7
res = 1
last_plus_index = -1
last_minus_index = -1
p_c = 0
m_c = 0

from collections import deque
# d = deque(A)

for i in range(K):
    t = A[i]
    # res *= t
    if t < 0:
        last_minus_index = i
        m_c += 1
    if t > 0:
        last_plus_index = i
        p_c += 1

if m_c % 2 == 0:
    for i in range(K):
        t = A[i]
        res += t
        res = res % mod
    print(res)
    exit()

# if K-1 == last_minus_index:
#     for i in range(K, N):
#         if A[i] > 0:
#             res = res // A[last_minus_index] * A[i]
#             print(res % mod)
#             exit()
#         if i == N-1:
#             if last_plus_index != -1:
#                 res = res // A[last_plus_index] * A[K]
#                 print(res % mod)
#                 exit()
#             else:
#                 # 解が0以下
#                 A = sorted(A, reverse=True)
#                 res = 1
#                 for i in range(K):
#                     res *= A[i]
#                 print(res % mod)
#                 exit()
#
# else:
#     for i in range(K, N):
#         if A[i] < 0:
#             res = res // A[K-1] * A[i]
#             print(res % mod)
#             exit()
#         if i == N-1:
#             res = res // A[last_minus_index] * A[K]
#             print(res % mod)
#             exit()

Submission status: Wrong Answer

Solution code:
from collections import Counter, deque

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

MOD = 10 ** 9 + 7

c = Counter()
for a in A:
    if a == 0:
        c['0'] += 1
    elif a < 0:
        c['-'] += 1
    else:
        c['+'] += 1

if c['-'] + c['+'] < K:
    print(0)
elif (c['-'] == N and K % 2 == 1) or (N == K and c['-'] % 2 == 1):
    def f(x):
        if x == 0:
            return 10 ** 9
        else:
            return abs(x)


    A = sorted(A, key=f)
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD

    print(ans)
else:
    A = sorted(A, key=lambda x: abs(x), reverse=True)
    plus = deque()
    minus = deque()

    for i in range(K):
        if A[i] >= 0:
            plus.append(A[i])
        else:
            minus.append(A[i])

    is_minus = False
    if len(minus) % 2 == 1:
        p = None
        m = None
        for i in range(K, N):
            if A[i] >= 0 and p is None:
                p = A[i]
            if A[i] < 0 and m is None:
                m = A[i]
            if p is not None and m is not None:
                break
        if m is None and p is None:
            pass
        elif len(plus) == 0:
            is_minus = True
            print(0)
        elif m is None and p is not None:
            minus.pop()
            plus.append(p)
        elif m is not None and p is None:
            plus.pop()
            minus.append(m)
        elif minus[-1] * m > plus[-1] * p:
            plus.pop()
            minus.append(m)
        else:
            minus.pop()
            plus.append(p)

    ans = 1
    while plus:
        ans *= plus.popleft()
        ans %= MOD
    while minus:
        ans *= minus.popleft()
        ans %= MOD

    if not is_minus:
        print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
A.reverse()
ans=1
inf=10**9+7
pos=sum(1 for x in A if x>=0)

if K%2==0:
    temp=list(abs(ai) for ai in A)
    temp.sort()
    temp.reverse()
    for i in range(K):
        ans*=temp[i]
        if i%2==1:
            ans=ans%inf
elif K<=pos:
    for i in range(int((K-1)/2)):
        small=A[0]*A[1]
        big=A[len(A)-2]*A[len(A)-1]
        if small<=big:
            ans*=big
            del A[len(A)-2:len(A)]
        else:
            ans*=small
            del A[0:2]
        if i%2==1:
            ans=ans%inf   
    ans*=max(A[0],A[len(A)-1])
    ans=ans%inf
elif pos==0:
    temp=list(abs(ai) for ai in A)
    temp.sort()
    for i in range(K):
        ans*=temp[i]
        if i%2==1:
            ans=ans%inf
    ans*=-1
    ans=ans%inf
else:
    for i in range(int((K-1)/2)):
        small=A[0]*A[1]
        big=A[len(A)-2]*A[len(A)-1]
        if small<=big:
            ans*=big
            del A[len(A)-2:len(A)]
        else:
            ans*=small
            del A[0:2]
        if i%2==1:
            ans=ans%inf   
    ans*=max(A[0],A[len(A)-1])
    ans=ans%inf

print(ans)

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, K = getlist()
	A = getlist()
	B = []
	for i in range(N):
		val = abs(A[i])
		if A[i] > 0:
			B.append([val , 1])
		elif A[i] < 0:
			B.append([val, -1])
		else:
			B.append([val, 0])
	B = sorted(B)

	M = 0; p = 0; m = 0; Aplus = []; Aminus = []; zerocnt = 0
	for i in A:
		if i == 0:
			zerocnt += 1
		elif i > 0:
			Aplus.append(i)
			M += 1; p += 1
		else:
			Aminus.append(i)
			M += 1; m += 1
	Aplus.sort()
	Aminus.sort()

	# 0が絶対に入る場合
	if K > M:
		print(0)
		return
	# マイナスになるから絶対ゼロを入れる場合
	if zerocnt > 0 and M == m and K % 2 == 1:
		print(0)
		return
	# マイナスのみの時の処理
	if m == N:
		if K % 2 == 0:
			ans = 1
			for i in range(K):
				ans *= Aminus[i]
				ans %= con
			print(ans)
			return
		else:
			ans = 1
			for i in range(K):
				ans *= Aminus[-1 - i]
				ans %= con
			print(ans)
			return

	# マイナスと0のとき
	if m == M:
		if K % 2 == 0:
			ans = 1
			for i in range(K):
				ans *= Aminus[i]
				ans %= con
			print(ans)
			return
		else:
			print(0)
			return

	pindPre = -100; pindAfter = INF
	mindPre = -100;	mindAfter = INF
	# print(B)

	for i in range(N - K):
		if B[i][1] == 1:
			pindPre = i
		elif B[i][1] == -1:
			mindPre = i

	for i in range(N - 1, N - K - 1, -1):
		if B[i][1] == 1:
			pindAfter = i
		elif B[i][1] == -1:
			mindAfter = i

	cnt = 0
	ans = 1
	for i in range(K):
		ans *= B[-1 - i][0]
		ans %= con
		if B[-1 - i][1] == -1:
			cnt += 1

	if cnt % 2 == 0:
		print(ans)
		return
	else:
		# ans *= -1
		ans % con
		if mindPre >= 0 and pindPre >= 0 and pindAfter <= N and mindAfter <= N:		
			if B[mindPre][0] * B[mindAfter][0] <= B[pindPre][0] * B[pindAfter][0]:
				ans *= B[pindPre][0] * pow(B[pindAfter][0], con - 2, con)
				ans %= con
			else:
				ans *= B[mindPre][0] * pow(B[mindAfter][0], con - 2, con)
				ans %= con

			print(ans)
			return

		elif pindPre >= 0 and pindAfter <= N:
			ans *= B[pindPre][0] * pow(B[pindAfter][0], con - 2, con)
			ans %= con
			print(ans)
			return
		else:
			ans *= B[mindPre][0] * pow(B[mindAfter][0], con - 2, con)
			ans %= con
			print(ans)
			return


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

mod = 10**9+7

cp = 0
cm = 0
for i in range(N):
    n = 1
    if A[i] < 0:
        n = -1
    elif A[i] == 0:
        n = 0
    A[i] = (abs(A[i]), n)
    if n > 0:
        cp += 1
    elif n < 0:
        cm += 1

f = -1
for i in range(0, K+1, 2):
    if i <= cm and K-i <= cp:
        f = 1
        break


if K > cp+cm:
    ans = 0
elif f == -1:
    A.sort()
    ans = 1
    for i in range(K):
        ans *= A[i][0]
        ans %= mod
    ans *= -1
    ans %= mod
else:
    A.sort(reverse=True)
    c1 = 0
    c2 = 0
    ans = 1
    for i in range(K):
        ans *= A[i][0]
        ans %= mod
        if A[i][1] < 0:
            c1 += 1
        elif A[i][1] > 0:
            c2 += 1

    if c1 % 2 == 1:
        a1 = 1
        if c1 < cm and c2 > 0:
            for i in range(K, N):
                if A[i][1] < 0:
                    a1 *= A[i][0]
                    break
            for i in range(K-1, -1, -1):
                if A[i][1] > 0:
                    a1 /= A[i][0]
                    break
        else:
            a1 = -1
        a2 = 1
        if c2 < cp and c1 > 0:
            for i in range(K, N):
                if A[i][1] > 0:
                    a2 *= A[i][0]
                    break
            for i in range(K-1, -1, -1):
                if A[i][1] < 0:
                    a2 /= A[i][0]
                    break
        else:
            a2 = -1
        if a1 > a2:
            for i in range(K, N):
                if A[i][1] < 0:
                    ans *= A[i][0]
                    ans %= mod
                    break
            for i in range(K-1, -1, -1):
                if A[i][1] > 0:
                    ans *= pow(A[i][0], mod-2, mod)
                    ans %= mod
                    break
        elif a2 > a1:
            for i in range(K, N):
                if A[i][1] > 0:
                    ans *= A[i][0]
                    ans %= mod
                    break
            for i in range(K-1, -1, -1):
                if A[i][1] < 0:
                    ans *= pow(A[i][0], mod-2, mod)
                    ans %= mod
                    break
        else:
            ans = 0

print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
    def addans(i, ans):
        return ans * i % mod
    import sys
    import bisect
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    inf = float("inf")
    n, k = map(int, input().split())
    a = sorted(list(map(int, input().split())))
    l = bisect.bisect_left(a, 0)
    r = bisect.bisect_right(a, 0)
    ans = 1
    minus = a[::-1]
    plus = a[:]
    if r == n:
        ans = 1
        for i in range(k):
            ans = addans(a[-i - 1], ans)
        print(ans)
        return
    if k % 2 == 1:
        ans = plus.pop()
        k -= 1
    try:
        m = minus.pop() * minus.pop()
    except:
        m = -inf
    try:
        p = plus.pop() * plus.pop()
    except:
        p = -inf
    for _ in range(k // 2):
        if p >= m:
            ans = addans(p, ans)
            try:
                p = plus.pop() * plus.pop()
            except:
                p = -inf
        else:
            ans = addans(m, ans)
            try:
                m = minus.pop() * minus.pop()
            except:
                m = -inf
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
n, k = [int(x) for x in input().split()]
nums = [int(x) for x in input().split()]

print(n,k)
print(nums)

# 絶対値を求める
numsabs = [abs(nums[x]) for x in range(len(nums))]