Cod sursa(job #943513)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 25 aprilie 2013 17:37:03
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>

using namespace std;

int n, a[30005];

ifstream cin("order.in");
ofstream cout("order.out");
void update( int where, int value)
{
    while(where <= n )
    {
        a[where]+=value;
        where += (where ^ (where-1)) & where;
    }
}
int query( int where )
{
    int sum=0;
    while( where )
    {
        sum += a[where];
        where -= (where^(where-1)) & where;
    }
    return sum;
}
int binary_search(int value)
{
    int res=-1, mij, xx;
    int li = 1;
    int ls = n;
    while( li <= ls)
    {
        mij = li+(ls-li)>>1;
        xx = query ( mij );
        if(xx == value)
            res = mij;
        else if( xx > value )
            ls = mij - 1;
        else li = mij + 1 ;
    }
    return res;
}
int main()
{
    cin>>n;
    for(int i = 1 ; i <= n ; ++i )
        update(i, 1);
    int nr=n, child=1;
    for(int i = 1 ; i <= n ; ++ i)
    {
        child+=i;
        child%=nr;
        if(child == 0)
            child=nr;
        int solutie= binary_search(child);
        update(solutie, -1);
        --child;
        --nr;
    }

    return 0;
}