Find the Kth value in ascending order ⇒ Find the minimum x such that there are K or more of x or less.
The content is quoted below. This post is a private note. ABC155 [Review of D problem] After reviewing the explanation video with the momentum of transcribing, the feeling of weakness in binary search has decreased
AtCoder Beginner Contest 155 (ABC155) A to E commentary
Sample code
n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr)
nc=0
zc=0
pc=0
#Negative number(nc), 0 number(zc), Negative number(pc)Count
for i in range(n):
if arr[i]<0:
nc+=1
elif arr[i]==0:
zc+=1
else:
pc+=1
#Find the number of pairs with a negative product
ncc=nc*pc
#Find the number of pairs whose product is 0
zcc=zc*(nc+pc)+(zc*(zc-1))//2
#Find the number of pairs whose product is positive
pcc=(nc*(nc-1))//2+(pc*(pc-1))//2
#If the Kth value is negative
if k <= ncc:
arr1=[]
arr2=[]
#Arrange negative and positive numbers in ascending order
for i in range(n):
if arr[i] < 0:
arr1.append(-arr[i])
elif arr[i] > 0:
arr2.append(arr[i])
arr1=arr1[::-1]
c1=len(arr1)
c2=len(arr2)
l = 0 # left
r = 10**18+1 #right is also the answer
#Since the calculation is performed by taking the minus of a negative number, the magnitude of the product is reversed, so the Kth from the largest
#From the smallest(Number of pairs with a negative product-K)Find the second value
k = ncc-k
while r-l != 1: #Repeat until r and l are one difference, that is, r is the answer
mid=(l+r)//2 #Updated interval median
cnt=0
pos=c2-1
#section[left, right)Shakutori method
#For each negative number, find and add the number of positive numbers whose product is smaller than the arbitrarily determined value mid.
for i in range(c1):
while pos!=-1:
if arr2[pos] > mid//arr1[i]:
pos-=1
else:
break
cnt+=pos+1
#The number of pieces less than or equal to the value mid decided arbitrarily(Number of pairs with a negative product-K)If more than one, the true value is less than or equal to mid
if cnt > k:
r = mid #Update right to mid and start over
#Otherwise the true value is greater than or equal to mid
else:
l = mid #Update left to mid and start counting again
#Since it was calculated by taking a minus of a negative number, it is output with a minus at the end.
print(-r)
#When the Kth value is 0
elif k <= (ncc+zcc):
print(0)
#If the Kth value is positive
else:
arr1=[]
arr2=[]
for i in range(n): #Arrange negative and positive numbers in ascending order
if arr[i] < 0:
arr1.append(-arr[i])
elif arr[i] > 0:
arr2.append(arr[i])
arr1=arr1[::-1]
c1=len(arr1)
c2=len(arr2)
l=0
r=10**18+1
k -= (ncc+zcc) #I want to check the Kth number in ascending order among positive numbers, so remove negative numbers and 0 numbers.
while r-l != 1:
mid=(l+r)//2
cnt1=0
pos1=c1-1
#For each negative number, find and add the number of negative numbers whose product is smaller than the arbitrarily determined value mid.(Shakutori method)
for i in range(c1):
tmp=0
while pos1 != -1:
if arr1[pos1] > mid//arr1[i]:
pos1-=1
else:
break
tmp+=pos1+1
#For each element, if the product when selecting itself twice is less than or equal to the arbitrarily determined value mid, the number of pairs that satisfy the condition is reduced by 1.
if arr1[i]**2 < mid:
tmp-=1
cnt1+=tmp
cnt1 = cnt1//2 #In the above process, the same pair is counted twice, so halve the number.
cnt2=0
pos2=c2-1
#For each positive number, find and add the number of positive numbers whose product is smaller than the arbitrarily determined value mid.(Shakutori method)
for i in range(c2):
tmp=0
while pos2!=-1:
if arr2[pos2] > mid//arr2[i]:
pos2-=1
else:
break
tmp+=pos2+1
if arr2[i]**2 < mid:
tmp-=1 #For each element, if the product when selecting itself twice is less than or equal to the arbitrarily determined value mid, the number of pairs that satisfy the condition is reduced by 1.
cnt2+=tmp
cnt2=cnt2//2 #In the above process, the same pair is counted twice, so halve the number.
cnt=cnt1+cnt2
if cnt >= k: #If the number of pieces below the arbitrarily determined value mid is K or more, the true value is below mid
r = mid
else: #Otherwise the true value is greater than or equal to mid
l = mid
print(r)
Recommended Posts