We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
#!/bin/python3importmathimportosimportrandomimportreimportsysfromheapqimportheappop,heappush,heapify## Complete the 'airports' function below.## The function is expected to return an INTEGER_ARRAY.# The function accepts following parameters:# 1. INTEGER d# 2. INTEGER_ARRAY x#defairports(min_dist,airports):road=sorted(set(airports))len_road=len(road)answers=[]airport_indices=dict()fori,ainenumerate(road):airport_indices[a]=iqty=[0]*len_roadforainairports:qty[airport_indices[a]]+=1safe=[]near_left=[]near_right=[]near_both=[]foriinrange(len_road-1):gap=(i,i+1)safe.append(gap)heapify(near_left)heapify(near_right)heapify(near_both)left_airport=0right_airport=len_road-1second_left=1second_right=len_road-2next_airport=list(range(1,len_road))+['N']prev_airport=['N']+list(range(len_road-1))forapinreversed(airports):road_left_airport,road_right_airport=road[left_airport],road[right_airport]whilesafeand(road[safe[-1][1]]-road_left_airport<min_distorroad_right_airport-road[safe[-1][0]]<min_dist):gap=safe.pop()ifroad[gap[1]]-road_left_airport<min_dist:heappush(near_left,(0-road[gap[1]],gap))else:heappush(near_right,(road[gap[0]],gap))whilenear_leftandroad_right_airport-road[near_left[0][1][0]]<min_dist:gap=heappop(near_left)[1]heappush(near_both,(road[gap[0]]-road[gap[1]],gap))whilenear_rightandroad[near_right[0][1][1]]-road_left_airport<min_dist:gap=heappop(near_right)[1]heappush(near_both,(road[gap[0]]-road[gap[1]],gap))whilenear_bothand(near_both[0][1][0]<left_airportornear_both[0][1][1]>right_airport):heappop(near_both)ifsafe:answers.append(0)else:possible_answers=[min_dist]ifleft_airport!=right_airport:ifqty[left_airport]==1:possible_answers.append(min_dist+road_left_airport-road[second_left])ifqty[right_airport]==1:possible_answers.append(min_dist+road[second_right]-road_right_airport)ifnear_left:possible_answers.append(max(0,min_dist+road_left_airport-road[near_left[0][1][1]]))ifnear_right:possible_answers.append(max(0,min_dist+road[near_right[0][1][0]]-road_right_airport))ifnear_both:possible_answers.append(0)nb=near_both[0][1]possible_answers[-1]+=max(0,min_dist+road_left_airport-road[nb[1]])possible_answers[-1]+=max(0,min_dist+road[nb[0]]-road_right_airport)answers.append(min(possible_answers))ai=airport_indices[ap]qty[ai]-=1ifqty[ai]:continuewhilesecond_left<len_road-1andqty[second_left]==0:second_left+=1whilesecond_right>0andqty[second_right]==0:second_right-=1ifai==left_airportorai==right_airport:whileleft_airport<len_road-1andqty[left_airport]==0:left_airport+=1whileright_airport>0andqty[right_airport]==0:right_airport-=1second_left=max(second_left,left_airport+1)second_right=min(second_right,right_airport-1)whilesecond_left<len_road-1andqty[second_left]==0:second_left+=1whilesecond_right>0andqty[second_right]==0:second_right-=1else:l=prev_airport[ai]r=next_airport[ai]next_airport[l]=rprev_airport[r]=lgap=(l,r)safe.append(gap)answers.reverse()answers[0]=0returnanswersif__name__=='__main__':fptr=open(os.environ['OUTPUT_PATH'],'w')q=int(input().strip())forq_itrinrange(q):first_multiple_input=input().rstrip().split()n=int(first_multiple_input[0])d=int(first_multiple_input[1])x=list(map(int,input().rstrip().split()))result=airports(d,x)fptr.write(' '.join(map(str,result)))fptr.write('\n')fptr.close()
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Airports
You are viewing a single comment's thread. Return to all comments →
Python solution