Cod sursa(job #1017386)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 27 octombrie 2013 18:51:01
Problema Order Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <iostream>
#include <fstream>

using namespace std;

const int Nmax = 30005;

int N;
int Arb[2 * Nmax];

void build( int nod, int st, int dr )
{
    if ( st == dr )
    {
        Arb[nod] = 1;
        return;
    }

    int m = ( st + dr ) >> 1;

    build( 2 * nod, st, m );
    build( 2 * nod + 1, m + 1, dr );

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

void update( int nod, int st, int dr, int position )
{
    if ( st == dr )
    {
        Arb[nod] = 0;
        return;
    }

    int m = ( st + dr ) >> 1;

    if ( position <= Arb[2 * nod] )
            update( 2 * nod, st, m, position );
    else
            update( 2 * nod + 1, m + 1, dr, position - Arb[2 * nod] );

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

int query( int nod, int st, int dr, int position )
{
    if ( st == dr )
    {
        return st;
    }

    int m = ( st + dr ) >> 1;

    if ( position <= Arb[2 * nod] )
            return query( 2 * nod, st, m, position );
    else
            return query( 2 * nod + 1, m + 1, dr, position - Arb[2 * nod] );
}

int main()
{
    ifstream f("order.in");
    ofstream g("order.out");

    f >> N;

    build( 1, 1, N );

    int de_eliminat = 2;
    int poz;
    int ramase = N;

    for ( int i = 1; i <= N; ++i )
    {
        de_eliminat = ( de_eliminat + i - 1 ) % ramase;

        if ( de_eliminat == 0 )
                de_eliminat = ramase;

        poz = query( 1, 1, N, de_eliminat );

        g << poz  << " ";

        update( 1, 1, N, de_eliminat );

        ramase--;
    }

    return 0;
}