Cod sursa(job #1601667)

Utilizator DysKodeTurturica Razvan DysKode Data 16 februarie 2016 09:57:49
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <fstream>

using namespace std;

ifstream fin("order.in");
ofstream fout("order.out");

int arb[ 120000 ],i,j,n,m,x;

void Update( int nod, int left, int right, int poz, int val )
{
    int middle = ( left + right ) / 2;

    if( left == right )
    {
        arb[ nod ] = val;
        return;
    }

    if( poz <= middle )
        Update( 2 * nod , left , middle , poz , val );
    else
        Update( 2 * nod + 1 , middle + 1 , right , poz , val );

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

void DeleteSpec( int nod, int left, int right )
{
    int middle = ( left + right ) / 2;

    if( left == right )
    {
        arb[ nod ] = 0;
        fout<<left<<' ';
        return;
    }

    if( arb[ 2 * nod + 1 ] == 0 )
        DeleteSpec( 2 * nod , left , middle );
    else
        DeleteSpec( 2 * nod + 1 , middle + 1 , right );

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

void DeleteElem( int nod, int left, int right , int nr )
{
    int middle = ( left + right ) / 2;

    if( left == right )
    {
        m = left;
        arb[ nod ] = 0;
        fout<<left<<' ';
        return;
    }

    if( arb[ 2 * nod ] == nr )
    {
        DeleteSpec( 2 * nod , left , middle );
        arb[ nod ] = arb[ 2 * nod ] + arb[ 2 * nod + 1 ];
    }
    else if( arb[ 2 * nod ] < nr )
    {
        nr -= arb[ 2 * nod ];
        DeleteElem( 2 * nod + 1 , middle + 1 , right , nr );
        arb[ nod ] = arb[ 2 * nod ] + arb[ 2 * nod + 1 ];
    }
    else
    {
        DeleteElem( 2 * nod , left , middle , nr );
        arb[ nod ] = arb[ 2 * nod ] + arb[ 2 * nod + 1 ];
    }
}

int main()
{
    fin>>n;
    x = 1;
    for( i = 1 ; i <= n ; i++ )
    {
        Update( 1 , 1 , n , i , 1 );
    }

    for( i = 1; i <= n ; i++ )
    {
        x = x + i;
        x = x % ( n - i + 1 );
        if( x == 0 )
            x = n - i + 1;
        DeleteElem( 1 , 1 , n , x );
        x--;
    }

return 0;
}