Cod sursa(job #472381)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 24 iulie 2010 13:30:49
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include<stdio.h>

using namespace std;

#define NMAX 30003
#define FIN "schi.in"
#define FOUT "schi.out"

int N , aib[NMAX] , POZ[NMAX] , rez[NMAX] , lg;

void update(int poz , int val)
 {
        while( poz <= N )
        {
          aib[poz] += val;
          poz += (((poz) ^ (poz - 1)) & poz);   
            }
        }

int query(int poz)
{
   int schiori = 0;
   while( poz > 0 )
   {
        schiori += aib[poz];
        poz -= (((poz) ^ (poz - 1)) & poz);
        } 
      return schiori;  
    }

int main()
{
    freopen(FIN , "r" , stdin);
    freopen(FOUT , "w" , stdout);
    scanf("%d" , &N);
    for(int i = 1 ; i <= N ; ++i) scanf("%d" , &POZ[i]) , update(i , 1);
    for( lg = 1 ; lg <= N ; lg <<= 1 );
    lg >>= 1;
    for(int i = N ; i > 0 ; --i)
     {
            int pz = 0 ;
            for(int salt = lg ; salt ; salt >>= 1)
             if( pz + salt < N && query(pz + salt) < POZ[i])
              pz += salt;
            rez[pz + 1] = i;
            update(pz + 1 , -1);  
            }
     for(int i = 1 ;i <= N ; ++i)
      printf("%d\n",rez[i]);       
     return 0;       
    }