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.
#Python3 solution # Enter your code here. Read input from STDIN. Print output to STDOUTimportsysimportheapqn=int(input())a=list(map(int,input().split()))freq=dict()foriina:ifinotinfreq:freq[i]=0freq[i]+=1iflen(freq)<n:print("NO")sys.exit()exp_freq=1depth=1while2**(depth-1)<n:depth+=1prev=dict()ans=[0]*(n+n-1)whileexp_freq<=n:v=list()v1=list()forkeyinprev:v1.append((key,prev[key]))forkeyinfreq:iffreq[key]==depth:v.append(key)iflen(prev)==0:ans[0]=v[0]prev[v[0]]=0freq[v[0]]-=1exp_freq*=2depth-=1continuev.sort()v1.sort()cur=exp_freq// 2 - 1pq=list()j=0foriinv:ifiinprev:ans[prev[i]*2+1]=iprev[i]=prev[i]*2+1freq[i]-=1else:whilej<len(v1):ifv1[j][0]<i:heapq.heappush(pq,v1[j][1])j+=1else:breakiflen(pq)==0:print("NO")sys.exit()temp=heapq.heappop(pq)ans[temp*2+2]=iprev[i]=temp*2+2freq[i]-=1exp_freq*=2depth-=1print("YES")foriinans:print(i,end=" ")
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Inverse RMQ
You are viewing a single comment's thread. Return to all comments →