Cod sursa(job #212795)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 6 octombrie 2008 21:14:01
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
# include <cstdio>

# define FIN "farfurii.in"
# define FOUT "farfurii.out"
# define ll long long
# define MAXN 100005

ll N,K,i;
ll A[3*MAXN];

    void update(ll nod,ll st,ll dr)
    {
        ll mij;
        if (st==dr)
          A[nod]=1;
        else
          {
             mij=(st+dr)>>1;
             update(nod<<1,st,mij);
             update(nod<<1|1,mij+1,dr);
             A[nod]=A[nod<<1]+A[nod<<1|1];
          }
    }
    
    void query(ll nod,ll st,ll dr,ll poz)
    {
        ll mij;
        if (st==dr)
          {
             A[nod]=0;
             printf("%lld ",st);
          }
        else
          {
             mij=(st+dr)>>1;
             if (poz<=A[nod<<1])
               query(nod<<1,st,mij,poz);
             else
               query(nod<<1|1,mij+1,dr,poz-A[nod<<1]);
             A[nod]=A[nod<<1]+A[nod<<1|1];
          }
    }

    int main()
    {
        freopen(FIN,"r",stdin);
        freopen(FOUT,"w",stdout);
        
        scanf("%lld%lld",&N,&K);
        
        update(1,1,N);
        for (i=1; i<=N; ++i)
          {
            if (K<=(N-i)*(N-i-1)/2)
              query(1,1,N,1);
            else
              {
                query(1,1,N,1+K-(N-i)*(N-i-1)/2);
                K=(N-i)*(N-i-1)/2;
              }
          }   
        return 0;
    }