Submission #10928876

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import math
import sys
import bisect
stdin = sys.stdin
def bisectf_left(f,val,start,end):
    fs = f(start)
    if val <= fs:
        return start
    fe = f(end-1)
    if fe < val:
        return end    
    # Now fs < val and val <= fe
    while True:
        if (end - start) <= 2:
            return end - 1
        mid = (start + end )// 2 
        fm = f(mid)
        if val <= fm :
            end = mid + 1
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import math
import sys
import bisect
stdin = sys.stdin

def bisectf_left(f,val,start,end):
    fs = f(start)
    if val <= fs:
        return start
    fe = f(end-1)
    if fe < val:
        return end    
    # Now fs < val and val <= fe

    while True:
        if (end - start) <= 2:
            return end - 1
        mid = (start + end )// 2 
        fm = f(mid)
        if val <= fm :
            end = mid + 1
        else: 
            start = mid
        continue

def bisectf_right(f,val,start,end):
    fs = f(start)
    if val < fs:
        return start
    fe = f(end-1)
    if fe <= val:
        return end
    # Now fs <= val and val < fe 
    while True:
        # print(start,end)
        if (end - start) <= 2:
            return end - 1
        mid = (start + end )// 2 
        fm = f(mid)
        if fm > val:
            end = mid + 1
        else:
            start = mid
        continue

def bisectf_bool(f,start,end):
    fs = f(start)
    if fs == True:
        return start
    fe = f(end-1)
    if fe == False:
        return end
    # Now fs == False and  fe == True 
    while True:
        # print(start,end)
        if (end - start) <= 2:
            return end - 1
        mid = (start + end )// 2 
        fm = f(mid)
        if fm == True:
            end = mid + 1
        else:    
            start = mid
        continue



ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
mod = 10**9 + 7 
sys.setrecursionlimit(1000010)

N,K = nm()
A  = nl()
A.sort()
# print(N,K,A)

zeroleft=bisect.bisect_left(A,0)
zeroright=bisect.bisect_right(A,0)
( nminus,nzero,nplus ) = (zeroleft,zeroright-zeroleft,len(A)-zeroright)
# print(nminus,nzero,nplus)

cminus = nminus * nplus
czero = nzero * (nminus + nplus ) + nzero * (nzero-1) // 2 
cplus = (nplus * (nplus - 1) + nminus * (nminus -1 ))//2

if K <= cminus:
    group = "minus"
    k = K
elif K <= czero + cminus:
    print(0)
    exit(0)
else:
    group = "plus"
    k = K - (czero + cminus)

def is_number_of_multiple_LE_Z_is_ME_K(z,k):
    if z == -1:
        return (True if cminus >= k else False)
    elif z == 0 :
        return (True if cminus + czero >= k else False)
    if z > 0:
        count = cminus + czero
        if count >=k:
            return True
        for i in range(zeroright+1,N):
            x = A[i]
            limit = z // x
            j = max(min(bisect.bisect_right(A,limit,zeroright),i),zeroright)
            count += (j - zeroright)
            # print("A",i,k,"limit=",limit,j,zeroright,j-zeroright)
            if count >=k: 
                return True
        for i in range(1,zeroleft):
            x = A[i]
            limit = - (-z // x )
            j = min(bisect.bisect_left(A,limit,0,i),i)
            count += (i-j)
            if count >= k:
                return True
        # return False
    else: # z is negavite and smaller than -1
        count = 0
        for i in range(zeroright,N):
            x = A[i]
            limit = z // x
            j = min(bisect.bisect_right(A,limit,0,zeroleft),zeroleft)
            count += j
            if count >=k: 
                return True
    return False

#for i in range(0,17):
#    for j in range(-7,5):
#        print(i,j,is_number_of_multiple_LE_K_is_ME_Z(j,i))  
        
if nminus == 0: 
    nmax = A[N-2]* A[N-1]
    nmin = A[0] * A[1]
elif nplus == 0:
    nmin = A[N-2]* A[N-1]
    nmax = A[0] * A[1]
else:
    nmax = max(A[N-2]* A[N-1],A[0] * A[1])
    nmin = A[0]* A[N-1]
        
def F(x):
    global K
    # print("K=",K)
    return is_number_of_multiple_LE_Z_is_ME_K(x,K)

# for i in range(-7,5):
#    print(i,F(i))

print(bisectf_bool(F,nmin,nmax + 1))

Submission Info

Judge Result