Cod sursa(job #829776)

Utilizator matei_cChristescu Matei matei_c Data 5 decembrie 2012 20:35:29
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 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;
	
}