Cod sursa(job #1216044)

Utilizator xtreme77Patrick Sava xtreme77 Data 3 august 2014 04:04:32
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <fstream>

const char IN [ ] = "order.in" ;
const char OUT [ ] = "order.out" ;
const int MAX = 30014 ;

using namespace std ;

ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;

int v [ MAX * 4 ];

void build ( int nod , int st , int dr )
{
    if ( st == dr )
    {
        v [ nod ] = 1 ;
        return ;
    }
    int mij = ( st + dr ) / 2 ;
    build( nod * 2 , st , mij ) ;
    build( nod * 2 + 1, mij + 1 , dr ) ;
    v [ nod ] = v [ nod * 2 ] + v [ nod * 2 + 1 ] ;
}
void update ( int nod , int st , int dr , int poz )
{
    if ( st == dr )
    {
        v [ nod ] = 0 ;
        return ;
    }
    int mij = ( st + dr ) / 2 ;
    if ( poz <= v [ nod * 2 ] )
        update( nod * 2 , st , mij , poz );
    else update ( nod * 2 + 1 , mij + 1 , dr , poz - v [ nod * 2 ] ) ;
    v [ nod ] = v [ nod * 2 ] + v [ nod * 2 + 1 ];
}
int Query ( int nod , int st , int dr , int poz )
{
    if ( st == dr )
    {
        return st ;
    }
    int mij = ( st + dr ) / 2 ;
    if ( poz <= v [ nod * 2 ] )
        return Query( nod * 2 , st , mij , poz );
    else return Query( nod * 2 + 1 , mij + 1 , dr , poz - v [ nod * 2 ] ) ;
}

int main ( )
{
    int n ;
    fin >> n ;
    build( 1 , 1 , n ) ;
    int elimin = 2 ;
    int ramas = n ;
    for ( int i = 1 ; i <= n ; ++ i , -- ramas )
    {
        elimin = ( elimin + i - 1 ) % ramas ;
        if ( ! elimin )
            elimin = ramas ;
        int poz = Query( 1 , 1 ,n , elimin );
        fout << poz << ' ' ;
        update( 1 , 1 , n , elimin ) ;
    }
    return 0 ;
}