Участник:Ujify/freq fun

Материал из DISCOPAL
Перейти к: навигация, поиск

task: https://www.codechef.com/problems/FREQFUN sol: https://www.codechef.com/viewsolution/46706705

def lower(x,b):
 
    l=0
    h=len(b)-1
    d={}
 
    while l<=h:
        m=(l+h)//2
        if b[m]==x:
            return m
        elif b[m]<x:
            l=m+1
        elif b[m]>x:
            d[b[m]]=m
            h=m-1
    k=len(d)
    if k>0:    
        mi=list(d.keys())
        p=mi[k-1]
        return d[p]
    else:
        return None
 
for _ in range(int(input())):
 
    n=int(input())
    a=list(map(int,input().split()))
    g=list(map(int,input().split()))
    b1=[0]*n
 
    if sum(g)!=n:
        print("impossible")
        continue
    nocount=0
 
    for i in range(n):
        if a[i]==-1:
            nocount+=1
        else:
            b1[a[i]]+=1
 
    k=n+1
    b2=[]
 
    for i in range(k):
        b2.extend([i]*g[i])
 
    i=n-1
    flag=0
    key=[]
 
    while i>=0:
        l=lower(b1[i],b2)
        if l==None:
            flag=1
            break
        diff=b2[l]-b1[i]
        key.extend([i]*diff)
        i-=1
        b2.pop(l)
 
    k=len(key)
    if k!=nocount:
        flag=1
 
    if flag:
        print("impossible")
        continue
 
    else:
        temp=0
        key.reverse()
        for i in range(n):
            if a[i]==-1:
                a[i]=key[temp]
                temp+=1
            print(a[i],end=' ')
        print()        
 
"""
 
4
3
-1 0 -1
0 3 0 0
3
2 2 1
3 0 0 0
3
-1 2 -1
1 1 1 0
3
-1 2 2
0 1 1 0
 
"""