Cod sursa(job #420868)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 20 martie 2010 18:11:17
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<iostream>
#include<string>

using namespace std;

#define NM 100005
#define LL long long
#define max(a,b)((a)>(b)?(a):(b))

int N,a,b,ARB[3*NM],ans;
LL K;

void update(int nod,int st,int dr)
{
     if(st==dr)
     {
          ARB[nod]+=b;
          return ;     
     }
     
     int mij=(st+dr)/2;
     
     if(a<=mij) update(2*nod,st,mij);
     else update(2*nod+1,mij+1,dr);
     
     ARB[nod]=ARB[2*nod]+ARB[2*nod+1];
}

void getkth(int nod,int st,int dr,int k)
{
     if(st==dr)
     {
         ans=st;
         return ;      
     }
     
     int mij=(st+dr)/2;
     
     if(k<=ARB[2*nod]) getkth(2*nod,st,mij,k);
     else getkth(2*nod+1,mij+1,dr,k-ARB[2*nod]);
}

int main()
{
    int sol[NM];
    
    freopen("farfurii.in","r",stdin);
    freopen("farfurii.out","w",stdout);
    
    scanf("%d %lld",&N,&K);
    
    for(int i=1;i<=N;++i)
    {
       a=i,b=1;     
       update(1,1,N);
    }   
    
    LL cate=0;
    
    for(int i=1;i<=N;++i)
    {
        int ramase=N-i;    
        LL pos=((LL)(ramase-1)*ramase)/2;
        LL alc=max(0,K-pos-cate);
        cate+=alc;
        int de_scos=alc+1;
        
        getkth(1,1,N,de_scos);
        sol[i]=ans;
        a=ans,b=-1;
        update(1,1,N);
            
    }
    
    for(int i=1;i<=N;++i)
       printf("%d ",sol[i]);
    
    return 0;
}