Cod sursa(job #211691)

Utilizator zombie_testertest test zombie_tester Data 3 octombrie 2008 13:09:29
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
# include <cstdio>

using namespace std;

# 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;
    }