Cod sursa(job #1322055)

Utilizator gedicaAlpaca Gedit gedica Data 19 ianuarie 2015 19:10:21
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb

#include <algorithm>
#include <fstream>

using namespace std;

const int NMAX= 100000;

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

int aib[NMAX+1], N, poz= 1;

inline int lsb( int x )
{
    return x & -x;
}

void update( int pos, int val )
{
    for( int i= pos; i<=N; i+= lsb( i ) )
    {
        aib[i]+=val;
    }
}

int querry( int pos )
{
    int ans= 0;

    for( int i= pos; i>0; i-= lsb( i ) )
    {
        ans+=aib[i];
    }

    return ans;
}

int binary(int x, int y, int val)
{
    int last, ans= 0, sc= 0, t= querry( x-1 );

    for( int i= 1<<17; i>0; i>>=1 )
    {
        if( ans+i<=N )
        {
            if( sc + aib[ans+i] - t < val )
            {
                ans+= i;
                sc+= aib[ans];
            }
            else if( sc + aib[ ans+i ] - t==val )
                last= ans+i;
        }
    }

    return last;
}

int main()
{
    in >> N;

    for( int i= 1; i<=N; ++i )
    {
        update( i, 1 );
    }

    for( int i= 1; i<=N; ++i )
    {
        int lg=( i-1 )%( N-i+1 )+1, limit= querry( N ) - querry( poz );
        if(lg<=limit)
        {
            poz= binary( poz+1, N, lg );
        }
        else
        {
            poz= binary( 1, poz, lg-limit );
        }

        update( poz, -1 );
        out << poz << " ";
    }
    return 0;
}