Cod sursa(job #986593)

Utilizator misinozzz zzz misino Data 19 august 2013 10:53:07
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<fstream>
using namespace std;
ifstream f("order.in");
ofstream g("order.out");
int p,poz,i,n,aib[30100];
inline void update(int p,int v)
{
    for(;p<=n;p+=(p^(p-1))&p)
    {
        aib[p]+=v;
    }
}
inline int query(int p)
{
    int sol=0;
    for(;p;p-=(p^(p-1))&p)
    {
        sol+=aib[p];
    }
    return sol;
}
inline int cautbin(int v)
{
    int li=1,ls=n,mij,x;
    while(li<=ls)
    {
        if(li==ls)
        return li;
        mij=(li+ls)>>1;
        x=query(mij);
        if(x<v)
        {
            li=mij+1;
        }
        else
        {
            ls=mij;
        }
    }
}
int main()
{
    f>>n;
    for(i=1;i<=n;++i)
    update(i,1);
    p=1;
    for(i=1;i<=n;++i)
    {
        p+=i;
        p%=(n-i+1);
        if(!p)
        p=n-i+1;
        poz=cautbin(p);
        update(poz,-1);
        g<<poz<<' ';
        p=query(poz);
    }
}