Cod sursa(job #839117)

Utilizator stoicatheoFlirk Navok stoicatheo Data 21 decembrie 2012 12:49:24
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define maxn ( 1 << 15 )
#define maxarb ( 1 << 16 )
 
int n ;
int v[maxn] ;
int arbore[maxarb] ;
int sol[maxn] ;
  
void initializare_arbore(int nod, int st, int dr)
{
    if( st == dr )
    {
        arbore[ nod ] = 1 ;
        return ;
    }
  
    int fiust = 2 * nod ;
    int fiudr = 2 * nod + 1 ;
    int mij = ( st + dr ) / 2 ;
     
    initializare_arbore( fiust, st, mij ) ;
    initializare_arbore( fiudr, mij+1, dr ) ;
  
    arbore[ nod ] = arbore[ fiust ] + arbore[ fiudr ] ;
 
}
  
void modifica(int value, int nod, int st, int dr)
{
    if( st == dr )
    {
        arbore[ nod ] = 0 ;
        return ;
    }
  
    int fiust = 2 * nod ;
    int fiudr = 2 * nod + 1 ;
    int mij = ( st + dr ) / 2 ;
     
    if( st <= value && value <= mij)
        modifica( value, fiust, st, mij ) ;
    else
        modifica( value, fiudr, mij + 1, dr ) ;
  
    arbore[ nod ] = arbore[ fiust ] + arbore[ fiudr ] ;
 
}
  
int query(int value, int nod, int st, int dr)
{
    if( st == dr )
        return st ;
  
    int fiust = 2 * nod ;
    int fiudr = 2 * nod + 1 ;
    int mij = ( st + dr ) / 2 ;
     
    if( arbore[ fiust ] >= value )
        return query( value, fiust, st, mij ) ;
    else
        return query( value - arbore[ fiust ], fiudr, mij + 1, dr ) ;
     
}
  
int main()
{
     
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
 
    scanf("%d", &n);
     
    for(int i = 1; i <= n; ++i )
        scanf("%d", &v[i]);
     
    initializare_arbore( 1, 1, n ) ;
  
    for(int i = n; i >= 1; --i )
    {
        int x = query( v[i], 1, 1, n ) ;
        sol[x] = i ;
        modifica( x, 1, 1, n ) ;
    }
     
    for(int i = 1; i <= n; ++i )
        printf("%d\n", sol[i]);
     
    return 0;
     
}