Cod sursa(job #829719)

Utilizator matei_cChristescu Matei matei_c Data 5 decembrie 2012 19:25:54
Problema Order Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

#define maxarb ( 1 << 15 )

int n ;
int arbore[maxarb] ;
 
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 poz, 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( poz <= mij )
		modifica( poz, fiust, st, mij ) ;
	else
		modifica( poz, 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( value > arbore[ fiust ] )
		return query( value - arbore[ fiust ], fiudr, mij + 1, dr ) ;
	
    return query( value, fiust, st, mij ) ;

}

int main()
{
	
	freopen("order.in", "r", stdin);
	freopen("order.out", "w", stdout);

    scanf("%d", &n);
 
    initializare_arbore( 1, 1, n ) ;
	
	int curent = 1 ;
	
    for(int i = 1; i <= n; ++i )
	{
        curent = (curent + i) % arbore[1] ;
         
		if( curent == 0 )
			curent = arbore[1] ;
		
        int sol = query( curent, 1, 1, n ) ;
		
        printf("%d ", sol);
         
        modifica( sol, 1, 1, n ) ;
         
        --curent ;
		
    }
	
    return 0 ;
 
}