Cod sursa(job #1514223)

Utilizator gedicaAlpaca Gedit gedica Data 30 octombrie 2015 20:53:37
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>

using namespace std;

const int NMAX= 30000, PMAX= 15;

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

int ft[NMAX+1];
int N;

void upd( int p, int x )
{
    for ( int i= p; i<=N; i= 2*i-(i&(i-1)) )
    {
        ft[i]+= x;
    }
}

int query( int p )
{
    int sol= 0;
    for ( int i= p; i>0; i&= i-1 )
    {
        sol+= ft[i];
    }
    return sol;
}

int main(  )
{
   // int N;
    in >> N;

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

    for ( int i= 1, aux= N, pos= 2; i<=N; ++i )
    {
        int Ans= 0;

        for ( int step= (1 << PMAX); step>0; step/= 2 )
        {
            if ( Ans+step<=N && query( Ans+step )<pos )
            {
                Ans+= step;
            }
        }

        out << Ans+1 << ' ';
        upd( Ans+1, -1 );

        pos+= i;
        --aux;

        if( aux>0 )
        {
            pos= pos%aux;
            if ( pos==0 )
            {
                pos= aux;
            }
        }
    }

    out << '\n';

    return 0;
}