Cod sursa(job #849519)

Utilizator bogdan93Grigorescu Bogdan bogdan93 Data 7 ianuarie 2013 08:36:53
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <cstdio>
#include <cstdlib>

#define nmax 1000001

FILE *fin = fopen ( "order.in" , "rt" ) , *fout = fout = fopen ( "order.out" , "wt" ) ;

int arb[nmax] , a , b , N , s , p ;

void update ( int nod , int stanga , int dreapta )
{
    if ( stanga == dreapta  )
        {
            arb[nod] = 1 ;
        }
        else
            {
                int mid = ( stanga + dreapta  ) / 2 ;
                update ( 2 * nod , stanga , mid ) ;
                update ( 2 * nod + 1 , mid + 1 , dreapta ) ;

                arb[nod] = arb[2 * nod] + arb[2 * nod + 1] ;

            }
}

void query ( int nod , int stanga , int dreapta )
{
    if ( stanga == dreapta )
        {
            arb[nod] = 0 ;
            fprintf ( fout , "%d " , stanga ) ;
        }
        else
            {
                int mid = ( stanga + dreapta  ) / 2 ;
                if ( s <= arb[2 *nod] )
                    {
                       query ( 2 * nod , stanga , mid ) ;
                       arb[nod]-- ;
                    }
                    else
                        {
                            s -= arb[2 * nod] ;
                            query ( 2 * nod + 1 , mid + 1 , dreapta ) ;
                            p += arb[2 * nod] ;
                            arb[nod]--;
                        }
            }
}


int main ()
{

    fscanf ( fin , "%d" , &N ) ;


    update ( 1 , 1 , N ) ;

    p = 1 ;
    for ( int i = 1 ; arb[1] > 0 ; i++ )
    {
        s = ( p + i ) % arb[1] ;
        if ( !s ) s = arb[1] ;
        p = 0 ;
        query ( 1 , 1 , N ) ;


    }
    fclose ( fin ) ;
    fclose ( fout ) ;

    return 0 ;

}